[Cryptech Tech] hash-based signatures

[Paul Selkirk]

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
-------------- next part --------------
tin-man:~/cryptech/sw/libhal$ tests/test-rpc_hashsig -i -L1..2 -l5..6 -o1..4 -n100
Starting hashsig key test: L 1, lms type 5 (h=5), lmots type 1 (w=1)
Info: signature length 8688, lmots private key length 8504
Could not generate hashsig private key: Unsupported key type or key length
Starting hashsig key test: L 1, lms type 5 (h=5), lmots type 2 (w=2)
Info: signature length 4464, lmots private key length 4280
Info: 0m8.927s to generate key (0.278s per lmots key)
Info: 0m10.602s to generate 32 signatures (0.331s per signature)
Info: 0m0.128s to verify 1 signature
OK
Starting hashsig key test: L 1, lms type 5 (h=5), lmots type 3 (w=4)
Info: signature length 2352, lmots private key length 2168
Info: 0m10.463s to generate key (0.326s per lmots key)
Info: 0m10.189s to generate 32 signatures (0.318s per signature)
Info: 0m0.143s to verify 1 signature
OK
Starting hashsig key test: L 1, lms type 5 (h=5), lmots type 4 (w=8)
Info: signature length 1296, lmots private key length 1112
Info: 0m42.796s to generate key (1.337s per lmots key)
Info: 0m24.336s to generate 32 signatures (0.760s per signature)
Info: 0m0.528s to verify 1 signature
OK
Starting hashsig key test: L 1, lms type 6 (h=10), lmots type 1 (w=1)
Info: signature length 8848, lmots private key length 8504
Could not generate hashsig private key: Unsupported key type or key length
Starting hashsig key test: L 1, lms type 6 (h=10), lmots type 2 (w=2)
Info: signature length 4624, lmots private key length 4280
Info: 4m35.210s to generate key (0.268s per lmots key)
Info: 0m33.828s to generate 100 signatures (0.338s per signature)
Info: 0m0.122s to verify 1 signature
OK
Starting hashsig key test: L 1, lms type 6 (h=10), lmots type 3 (w=4)
Info: signature length 2512, lmots private key length 2168
Info: 5m26.294s to generate key (0.318s per lmots key)
Info: 0m32.174s to generate 100 signatures (0.321s per signature)
Info: 0m0.141s to verify 1 signature
OK
Starting hashsig key test: L 1, lms type 6 (h=10), lmots type 4 (w=8)
Info: signature length 1456, lmots private key length 1112
Info: 22m39.923s to generate key (1.328s per lmots key)
Info: 1m14.950s to generate 100 signatures (0.749s per signature)
Info: 0m0.590s to verify 1 signature
OK
Starting hashsig key test: L 2, lms type 5 (h=5), lmots type 1 (w=1)
Info: signature length 17428, lmots private key length 8504
Could not generate hashsig private key: Unsupported key type or key length
Starting hashsig key test: L 2, lms type 5 (h=5), lmots type 2 (w=2)
Info: signature length 8980, lmots private key length 4280
Info: 0m12.830s to generate key (0.200s per lmots key)
Info: 0m35.239s to generate 100 signatures (0.352s per signature)
Info: 0m0.214s to verify 1 signature
OK
Starting hashsig key test: L 2, lms type 5 (h=5), lmots type 3 (w=4)
Info: signature length 4756, lmots private key length 2168
Info: 0m15.998s to generate key (0.249s per lmots key)
Info: 0m35.224s to generate 100 signatures (0.352s per signature)
Info: 0m0.235s to verify 1 signature
OK
Starting hashsig key test: L 2, lms type 5 (h=5), lmots type 4 (w=8)
Info: signature length 2644, lmots private key length 1112
Info: 1m21.161s to generate key (1.268s per lmots key)
Info: 2m53.243s to generate 100 signatures (1.732s per signature)
Info: 0m1.325s to verify 1 signature
OK
Starting hashsig key test: L 2, lms type 6 (h=10), lmots type 1 (w=1)
Info: signature length 17748, lmots private key length 8504
Could not generate hashsig private key: Unsupported key type or key length
Starting hashsig key test: L 2, lms type 6 (h=10), lmots type 2 (w=2)
Info: signature length 9300, lmots private key length 4280
Info: 6m35.809s to generate key (0.193s per lmots key)
Info: 0m24.495s to generate 100 signatures (0.244s per signature)
read: Success
Could not verify: RPC transport error

tin-man:~/cryptech/sw/libhal$ tests/test-rpc_hashsig -i -L2 -l6 -o3 -n100
Starting hashsig key test: L 2, lms type 6 (h=10), lmots type 3 (w=4)
Info: signature length 5076, lmots private key length 2168
Info: 6m15.090s to generate key (0.183s per lmots key)
Info: 0m19.737s to generate 100 signatures (0.197s per signature)
Info: 0m0.218s to verify 1 signature
OK