[Cryptech Tech] hash-based signatures

[Russ Housley]

Thanks.  I hope the muxd problem is easy to sort.

Russ



> On Jul 31, 2018, at 3:38 PM, Paul Selkirk <paul at psgd.org> wrote:
> 
> Russ and other interested parties -
> 
> After considerable delay, the hashsig branch has been merged to master.
> I see that Rob has picked it up for releng, so it should be in the
> binary package.
> 
> To review, this hashsig code is a clean-room implementation of
> draft-mcgrew-hash-sigs.  It has been shown to interoperate with the
> Cisco reference code (each can verify the other's signatures).
> 
> Following the recommendations of the draft, we only store the topmost
> hash tree (the "root tree") in the token keystore; lower-level trees are
> stored in the volatile keystore, and are regenerated upon a system restart.
> 
> This implementation has limitations on the number of keys, size of OTS
> keys, and size of signatures, because of the design of the keystore and
> of the RPC mechanism:
> 
> 1. The token keystore is a fairly small flash, partitioned into 2048
> 8096-byte blocks. Therefore, we can't support LMS algorithm types >
> lms_sha256_n32_h10 (a.k.a. h=10, or 1024 keys per tree). In this case,
> keygen will return HAL_ERROR_NO_KEY_INDEX_SLOTS.
> 
> Additionally, the 8KB key storage size means that we can't support
> LM-OTS algorithm type lmots_sha256_n32_w1, which has an OTS key size of
> 8504 bytes. In this case, keygen will return HAL_ERROR_UNSUPPORTED_KEY.
> 
> 2. The volatile keystore is currently limited to 1280 keys, so only 2
> levels at h=10, but more levels at h=5. One could easily increase the
> size of the volatile keystore, but L=2/h=10 gives us a key that can sign
> 1M messages, which is sufficient for development and testing purposes.
> 
> 3. The RPC mechanism currently limits request and response messages to
> 16KB, so we can't generate or verify signatures greater than that size.
> In this case, keygen will return HAL_ERROR_UNSUPPORTED_KEY.
> 
> Because the hashsig private key consists of a large number of one-time
> signing keys, and because only the root tree is stored in flash, it can
> take several minutes to reconstruct the full tree on system restart.
> During this time, attempts to generate a hashsig key, delete a hashsig
> key, or sign with a hashsig key will return HAL_ERROR_NOT_READY.
> 
> A hashsig private key can sign at most 2^(L*h) messages. (System
> restarts will cause the lower-level trees to be regenerated, which will
> need to be signed with by the root tree, so frequent restarts will
> rapidly exhaust the root tree.) When a hashsig key is exhausted, any
> attempt to use it for signing will return HAL_ERROR_HASHSIG_KEY_EXHAUSTED.
> 
> There are some trade-offs between keygen/signing time and key/signature
> size. As noted, w=1 produces keys that don't fit in the keystore, while
> w=8 produces the smallest keys but excruciating keygen and signing
> times. The sweet spot seems to be w=4, where keys and signatures are
> about half the size of w=2, keygen is a bit slower, and signing is
> actually a wee bit faster (for reasons I haven't fully explored).
> 
> Performance is not great at the moment. The keystore is slow, AES
> keywrap/unwrap is slow (although we're working on it), and hashing is
> not super fast.
> 
> Also, there seems to be a bug in cryptech_muxd, where writing a
> signature of more than about 9000 bytes (for verification) causes a
> Tornado write timeout and exception in the RPC side of the muxd.
> (Reading the signature is fine.) This propagates back to the caller as
> HAL_ERROR_RPC_TRANSPORT. We're looking into it, but didn't want to hold
> up the hashsig code, since the error doesn't seem to be in the hashsig
> code itself, hashsig is just the only thing the produces signatures long
> enough to trigger this behavior.
> 
> The attached test log shows the signature and key sizes, keygen and
> signing times, and the RPC transport error.
> 
> There is one new RPC function: hal_rpc_pkey_generate_hashsig(), and
> functions to translate public keys between the SPKI format that we use
> and the XDR format specified in the draft:
> hal_hashsig_key_load_public_xdr() and
> hal_hashsig_public_key_der_to_xdr(). Other than that, signing and
> verification are the same as with RSA and ECDSA keys. There's no example
> code per se, but libhal/tests/test-rpc_hashsig.c should contain enough
> clues to get you started.
> 
> 				paul
> <test-rpc_hashsig.txt>_______________________________________________
> Tech mailing list
> Tech at cryptech.is
> https://lists.cryptech.is/listinfo/tech