Post-quantum cryptography: Hash-based signatures

Last quarter, I introduced the issue where our existing public key cryptography algorithms are vulnerable to a potentially new form of computers called quantum computers. In this article I introduce one of the better understood potential replacements: Hash-based signatures.

The basics

The general idea of hash-based signatures is pretty simple. You determine ahead of time what values you want to sign, and then you generate long random strings for each. You then hash your random strings and  publish them as your public key. To sign an object, you expose the random value associated with that object. That random value is the signature. A verifier can verify the signature by hashing the signature and comparing it to the entry for the object in the public key.

For example, I want to be able to sign four values, then I generate four random values (sk0-sk3) and hash them (pk0-pk3):

Value to sign    Private key                Public key
0                sk0 (randomly generate)    pk0(=HASH(sk0))
1                sk1 (randomly generate)    pk1(=HASH(sk1))
2                sk2 (randomly generate)    pk2(=HASH(sk2))
3                sk3 (randomly generate)    pk3(=HASH(sk3))

This is secure as long as the hash you use has the property of "preimage resistance." Preimage resistance means that it is not possible to figure out the value that generated the hash in reasonable time.

Lamport signatures

This is fine if you only want to sign two bit objects, if you want to sign something larger, like 2⁶⁴ bit objects, You would need to provide 2⁶⁴ hashes, which is difficult to do in a reasonable amount of time, and will take a large amount of space to store and send the public key and the private key (2⁶⁴*sizeof (HASH)). You can get around this, though by generating 128 random values and their hashes representing 0 or 1 of each bit in the hash you want to sign:

Bit   Private Key 0  Private Key 1      Public Key 0          Public Key 1
0     sk0.0          sk0.1              pk0.0=HASH(sk.0.0)    pk0.1=HASH(sk.0.1)
1     sk1.0          sk1.1              pk1.0=HASH(sk.1.0)    pk0.1=HASH(sk.1.1)
2     sk2.0          sk2.1              pk2.0=HASH(sk.2.0)    pk0.1=HASH(sk.2.1)
.     .              .                  .                     .
.     .              .                  .                     .
62    sk62.0         sk62.1             pk62.0=HASH(sk.62.0)  pk62.1=HASH(sk.0.1)
63    sk63.0         sk63.1             pk63.0=HASH(sk.63.0)  pk63.1=HASH(sk.0.1)

Now you take your 64 bit value to sign and reveal just the private keys that match with the bit values of the object you want to sign. The verify checks to see if your values hash to the corresponding public key value. So if you want to sign:

1000100011000011101100001111010101110111001111100010011110001010

You’d publish:

sk63.1,  sk62.0, sk61.0, sk60.0, sk59.1 ……sk3.1, sk2.0, sk1.1, sk0.0

To verify, the verify would check that:

HASH(sk63.1) = pk63.1
HASH(sk63.0) = pk62.0
.
.
HASH(sk1.1) = pk1.1
HASH(sk0.0) = pk0.0

Now your private key is only 64*sizeof(HASH) and our public key is 2*64*sizeof(HASH). The down side is you can only sign one object with each key. As soon as you sign another object, you will reveal more of your private key and attackers could now forge signatures for about half of the 64 bits. These types of signatures are called Lamport signatures, named after the inventor Leslie Lamport in 1979.

Winternitz

Lamport keys, besides being one off, are still quite large. The signature size is n*sizeof(HASH) where n is the number of bits you want to sign. Typical signature schemes sign between 128 and 512 bits with hash sizes between 128 and 512 bits (16 and 64 bytes), so a 256 bit signature with a SHA-256 hash would be 8k bytes, and the public key is 16k bytes. 

Remember the initial description to sign four different values by having four private keys and four public keys. What if there was a way to allow a single private and public key to sign more values. Then instead of signing each bit, we could sign two or four bits at a time. Robert Winternitz proposed a solution: we create a hash chain, but applying the hash multiple times. For our case of four values:

pk=HASH

⁴(sk) = HASH(HASH(HASH(HASH(sk))))

To sign a value v, you hash our secret key v times. So:

v=0 sig=sk
v=1 sig=HASH(sk)
v=2 sig=HASH(HASH(sk))
v=3 sig=HASH(HASH(HASH(sk)))

To verify you hash 4-v times and compare with the public key:

v=0, HASH(HASH(HASH(HASH(sig)))) = pk
v=1, HASH(HASH(HASH(sig))) = pk
v=2, HASH(HASH(sig))) = pk
v=3, HASH(sig) = pk

To sign a larger number, you split the number up base 4 (split up every 2 bits), and have sig_size/2 private keys (sk0,sk1….) and  sig_size/2 public keys (pk0=HASH4(sk0), pk1=HASH4(sk0)...).

You don’t have to use four, though you can set the number of hashes in the hash chain to any arbitrary value w (usually a power of 2). The larger w is the smaller the keys and signatures are, but the longer it takes to validate them. Using w = 16, you can sign the example 64 bit value as follows:

1000100011000011101100001111010101110111001111100010011110001010

Split into groups of four:

1000 1000 1100 0011 1011 0000 1111 0101 0111 0111 0011 1110 0010 0111 1000 1010
   8    8   12    3   11    0   15    5    7    7    3   14    2    7    8   10

Signature is the hash chain of each private key:

HASH⁸(sk15) HASH⁸(sk14) HASH¹²(sk23) HASH³(sk12) HASH¹¹(sk11) sk10 HASH¹⁵(sk9) HASH⁵(sk8) HASH⁷(SK7) HASH⁷(sk6) HASH³(sk5) HASH¹⁴(sk4) HASH²(sk3) HASH⁷(sk2) HASH⁸(sk1) HASH¹⁰(sk0)

This isn’t sufficient though because an attacker can now sign any number which is the strict increase of the number you signed. If you signed zero, the attacker can forge any signature. To prevent this we also sign a checksum. The checksum is designed so if you increase any of the values, the checksum would decrease. An easy way of doing this is to calculate the checksum by subtracting each of our values from w-1 and summing them together:

Value to sign

   8    8   12    3   11    0   15    5    7    7    3   14    2    7    8   10

Subtract from 15

   7    7    3   12    4   15    0   10    8    8   12    1   13    8    7    5

​Add them together to get the checksum:

120 = 0111 1000 = 7 8

You would now include the signature of the checksum HASH⁷(sk.ck.1) HASH⁸(sk.ck.0) in the full signature. If the attacker increases the value of any of the components, he would decrease the checksum, and thus not be able to forge a proper checksum.

These are called Winternitz One Time Signatures, or WOTS for short. A WOTS 64 bit signature with w equal to 16 has a private key size of 18*sizeof(HASH) (16 + 2 for the checksum), a public key size of 18*sizeof(HASH) and a signature size of 18*sizeof(HASH). This is significantly smaller than the key sizes for Lamport above.

Merkle trees

If you can only sign one signature with a single key, for a practical system, you want the ability to have a single public key which can validate a whole lot of keys. You can then sign each object with a different key that is validated with your single public key. You can do this with Merkle trees.

First you pre-generate all the keys you are going to use, then you hash all your pubX.x values for a single key together to create a single hash value for each key. Next you hash pairs of values together to create a hash value for a node that links the two keys together. Next you hash pairs of nodes together to create a hash that links the nodes together and covers four keys. You continue this process until you have a single hash covering all the keys. This hash value is your public key. Figure 1 shows the resulting structure which is called a Merkle tree.

To sign, you pick the next unused key and create your WOTS signature. Next you include the hash of the second key from the node that shares keys with the key you are signing with. Then, from the next node up, you include the hash node next to it. You do this until you reach the top node. You can verify the signature by first using the WOTS signature to recreate the public key. Then you verify the WOTS public key by hashing it, then taking that key hash and hashing it with the next hash in the signature, then hashing that with the next hash in the signature, etc. At the end the final hash should match the public key.

Merkle trees were invented by Ralph Merkle in 1979. They give you a way of reducing the public key size to a single hash at the cost of increasing the signature size. Since the signature size only grows as the log base 2 of the number of keys, Merkle trees can be used to hold a large number of private keys.

Extended Merkle Signature System (XMSS) and LMS

NIST and the IETF have specified signature schemes based on this combination of Merkle trees and WOTS signatures in different systems: Extended Merkle Signature System (XMSS) and Leighton-Micali Signatures (LMS) . They specify predefined sets of parameters, as well as how to implement the chaining and node hashing in a way to provide compatibility.

Multi Merkle trees

One major limit to the base Merkle tree is the need to generate and store all the keys you are going to sign in order to create your public key. One way to reduce the storage cost of the private key is to generate a single random value, then use that as a seed to a pseudo-random function (PRF) to generate all the remaining keys. If you define the PRF to index the desired element by a key number and WOTS subkey or checksum, you can arbitrarily generate any individual key on the fly, and only need to store the single random value for the private key.

You still have to generate all the keys you want to sign with initially to create your public key and Merkle tree. If you want to sign with something large, like 2⁶⁰ keys, this can be prohibitively expensive, time wise. The solution is to generate multiple smaller Merkle trees. You use the keys in the top level Merkle trees to sign multiple next level Merkle trees. These trees can sign another level, etc. The bottom level Merkle trees would have the general purpose keys you would use to sign your object. You could then include a Merkle tree number in the PRF, so that each Merkle tree is different. Since you are generating everything from a single seed, a given Merkle tree will always be the same, so you can generate the lower level trees as you need them. If you regenerate a key you previously had, you can still safely sign that tree with the same key because the public key for that subtree won’t change. Since each Merkle tree is smaller, you can generate that Merkle tree on the fly as needed, so you never need to generate all the keys at once.

This allows you to tune your scheme to trade off the number of signatures, the signature size and the time it takes to create a signature. Larger Merkle trees and fewer levels create smaller signatures, but are more expensive to sign because you have to generate these larger Merkle trees at signature time. Reducing the size of the Merkle trees creates more levels to get the same number of signatures, which increases the signature size since you need to include multiple WOTS signatures in your hash chain.

Both NIST and the IETF  have standardized on a set of parameters for Extended Merkle Signature System/Multi Tree (XMSS^MT) and Hierarchical Signature System (HSS) trees, which are ready to use today.

Stateful hash-based signatures

Both the single Merkle tree and multi Merkle trees are called stateful hash-based signatures. That is because you have to remember which lower level private keys you have used and never reuse those keys. Properly maintaining this state is difficult. It means you can’t really backup these kinds of keys because you can only keep one version of the counter for the next key to use. If you ever lose that counter, then you cannot trust that you won’t reuse a key. If you ever reuse any key, that key can be used to compromise the entire system. In normal software, backups and cloning are outside the control of the application. The application could be running on a virtual machine which gets cloned.The data for the application could be backed up to the web and restored on multiple machines. For this reason, XMSS, LMS and HSS are highly recommended (sometimes required) to be implemented in hardware without the ability to clone the key. This requirement, as well as the large signature sizes, means that this scheme is not a good general purpose signature scheme. The current uses include things like code and firmware signing.

Stateless hash-based signatures

The statefulness of XMSS makes using the scheme securely highly dependent on the deployment controls. Deployment mistakes that lead to a complete compromise can happen relatively easily. There is a way to turn these stateful hash systems into stateless. Going back to the toy 64 bit signing system. If we use XMSS^MT or HSS to create a tree that can sign 2⁶⁴ values, you can use the object we want to sign to select the key to sign it with. So you use a multi Merkle tree of depth 4 and 2¹⁶ elements each. The first 16 bits of the object you want to sign will select which of the 2¹⁶ trees on level 1. The next 16 bits select which of the 2¹⁶ trees under the current one to use. You continue until you can use the last 16 bits to select which signature in the tree to use. Now there is no reason to keep track of the current state. You will never sign a different object with the same key because the object itself selects the key. Unfortunately 64 bit signing systems are not considered secure in modern cryptography, 128 is the minimum and still considered weak. The smallest XMSS system specified is 256, and NIST’s smallest variants are 192 bits. Merkle trees deeper than 25 levels can take hours to generate, so 2¹⁶ keys (16 levels) is the largest practical parameter for our Merkle trees if we need to generate them on the fly. This means multi-tree depths of 8 for 128 and 16 for 256 signatures. This leads to long signature times and large signatures.

There are another class of hash-based signature primitives which allow for a "few time use" of a specific key rather than just one time use like WOTS and Lamport signatures. These allow construction of trees of 2⁶⁴ signatures, and like our 2⁶⁴ signature case, the actual message to sign helps select which key to use.  SPHINCS and SPHINCS+ are signature schemes which use this idea. SPHINCS+ has been selected by NIST for standardization, and the standard spec should be available in the next couple of years. Signature sizes for SPHINCS+ vary between about 8k Bytes and 49k Bytes depending on security level and performance.

Conclusions

Hash-based signatures provide a mechanism for signing that is well studied, and resistant to attacks by quantum computers (as long as our hash functions are safe). They are relatively easy to understand. There are standards available today, but only for the stateful versions of these signatures, which have tricky deployment issues. Multi-tree versions allow for new stateful signatures and allow us to make size versus speed tradeoffs. SPHINCS+, a stateless hash-based signature scheme, has been accepted by NIST, and should be standardized "soon" as a general purpose signature algorithm, albeit with very large signatures.