We are pleased to (belatedly) announce the implementation of hash-based signatures for the CrypTech project. This work was discussed in the Internet Research Task Force (IRTF) Crypto Forum research group (cfrg) last year and announced in July 2018 on the technical mailing list for the CrypTech community (tech@cryptech.is). 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 one time signature (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 Leighton-Micali signature (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 test log posted to the tech mailing list shows the signature and key sizes, keygen and signing times, and the RPC transport error (see https://lists.cryptech.is/archives/tech/2018-July/003002.html).
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 Selkirk