Skip to content

Instantly share code, notes, and snippets.

@patchthecode

patchthecode/Hash Ladders for Shorter Lamport Signatures.md

Forked from karlgluck/Hash Ladders for Shorter Lamport Signatures.md
Created June 11, 2021 03:37
Show Gist options
  • Save patchthecode/7e169fb7d57decfb7fcd2da8e2abaf54 to your computer and use it in GitHub Desktop.
Save patchthecode/7e169fb7d57decfb7fcd2da8e2abaf54 to your computer and use it in GitHub Desktop.
Download ZIP
I describe a method for making Lamport signatures take up less space. I haven't seen anyone use hash chains this way before, so I think it's pretty cool.
Raw
Hash Ladders for Shorter Lamport Signatures.md

What's this all about?

Digital cryptography! This is a subject I've been interested in since taking a class with Prof. Fred Schneider back in college. Articles pop up on Hacker News fairly often that pique my interest and this technique is the result of one of them.

Specifically, this is about Lamport signatures. There are many signature algorithms (ECDSA and RSA come to mind as popular choices) but Lamport signatures are unique because they are formed around a hash function. Many cryptographers believe that, as such, they are immune to attacks made possible by quantum computers.

How does a Lamport Signature work?

Here's the long version. I'll give you the short copy without all the parameterization:

  1. Come up with 2 sets (set 0 and set 1) of 256 random 256-bit numbers. Keep these secret! They're your private key.
  2. Take the SHA-256 hash of each of your secret numbers. These 512 hashes are your public key.
  3. Get the SHA-256 hash of whatever document you want to sign
  4. For each bit i of the hash from 0..256: If it is a 0, publish the ith number from secret set 0. If it is a 1, publish the ith number from secret set 1. Destroy all unused numbers.
  5. You now have a signature (the 256 random numbers from step 4 corresponding to the bits of the hash from step 3) and a public key (the 512 hashes from step 2).

Because hashes are one-way functions, it is computationally hard to forge the secret, random numbers you created in step 1 that would allow an attacker to change your signature. In other words, it takes an impractically huge amount of computational power for an adversary to produce verifiable proof that you signed something other than what you actually signed.

There are two big snags with using Lamport signatures in practice:

  1. This is a one-time signature. You can't sign anything else with the same public key. Doing so would reveal more of your secret numbers and would allow an attacker to forge your signature for other documents. This is easily solved with a hash tree, creating what is called the Merkle signature scheme.
  2. The signatures are huge compared to ECDSA or RSA. Signing an N-bit hash requires N hashes of N bits each. That's around 8 kib for signing a 256-bit hash or 32 kib for a 512-bit hash. That's around 1000x the size of a comparable ECSDA signature.

How to Shorten Lamport Signatures

The Wikipedia article outlines ways to shorten the private key using a random number generator and compress the public key with a hash list. No solution for shortening the public signature itself is published. That's where this article comes in! (cue trumpets)

The Other End of the Spectrum: A Hash Ladder

First, I present an toy demonstration of the algorithm. It cannot be implemented for a number of reasons, but it shows the functionality. After we go through this, I'll modify it to make it usable in practice.

Assume you have a 3-bit signature of a document, H3bit(document) = 6. Pick two random 5-bit values, 12 and 29, as your private key. Hash each value 2^signed_hash_bits + 2 = 2^3 + 2 = 10 times with a perfect random 5-bit oracle called H5bit. Each possible value of your 3-bit hash has a corresponding index in this chain:

         [0]     [1]    [2]    [3]    [4]    [5]    [6]    [7]
A: 12 -->  5 --> 24 -->  9 -->  1 --> 15 --> 10 -->  8 --> 11 --> 27
B: 23 <-- 19 <-- 20 <--  4 <-- 13 <-- 17 <--  3 <-- 14 <-- 28 <-- 29
                                                     ^

A starts on the left and repeated hashes are listed to the right. B starts on the right and repeated hashes are listed to the left. This forms the "ladder" analogy, with pairs of hashes making the "rungs". The hash is 5 bits to accommodate at least 20 unique non-colliding hashes. In this toy example, I made up a perfect random oracle hash function with no collisions. In practice, the hash values are incredibly unlikely to collide because their range is 256 or 512 bits rather than 5.

The values at the end of each chain (A=27, B=23) are your public key.

To sign your document with hash 6, find the pair of values at that index: [6] = (A=8, B=14). By publishing these values, anyone with the public key can verify that the pair (A=8, B=14) corresponds to the H3bit(x) = 6:

  • Take the A part of the pair, 8, and hash it until it equals 27, the A part of the public key. This takes 2 hashes.
  • Take the B part of the pair, 14, and hash it until it equals 23, the B part of the public key. This takes 7 hashes.
  • The total hash operations to produce the public key is 8, which is public knowledge as an algorithmic constant. 8-2 = 6, which is the claimed hash. 7-1 = 6, which is also the claimed hash.
  • Producing any other pair on the hash ladder requires hash inversion on one chain or the other, so this is the only valid signature.

An adversary cannot create a valid signature for another value without inverting one of the hashes. For example, to change the pair to sign the value 7, the adversary must be able to solve H5bit(x) = 14 for x in order to produce the pair (11, 28). Similarly, to change the pair and sign the value 5, the adversary must be able to invert H5bit(x) = 8 and produce the pair (10, 3). I call this construct a hash ladder because every pair of hash values in the two rows locks each other in place and defines a distinct location on the number line.

Now, we can't actually use this without some modification. Creating a signature in this way for a 256-bit value would require a 257-bit hash function to be executed 2*2^256+2 times just to make the public signature. Not only would one signature take longer to compute than the age of the universe, it isn't secure without a hash function that is a perfect perfect random oracle, and any machine that could actually compute this function would be able to invert hashes by brute force anyway.

To use shorten Lamport signatures with a hash ladder, we need to chop up the hash to be signed into manageable chunks and create a ladder for each. Each ladder needs to be short enough to be both computable and to have a very low probability of having hash collisions anywhere in the ladder itself.

The Implementable Algorithm

While this can be parameterized to use different ladder chunks and different hash sizes, I present this using 8-bit chunks and 256-bit hashes.

Signing

  1. Take the SHA-256 hash of the document you want to sign
  2. Split the 256-bit hash of your document into 32 8-bit chunks
  3. For each chunk, generate a pair of secret random 256-bit numbers. These 64 numbers are your private key.
  4. Hash each of these numbers 258 times. This final set of 32 pairs of 2 hashes each are your public key. (Note: Use a hash chain and this public key becomes just 256 bits)
  5. To create your signature, examine each chunk again. Let the value of this chunk be n with the range [0, 255]. There are 2 256-bit numbers of the private key associated with that chunk. Let a equal the first of these numbers hashed n+1 times. Let b equal the second of these numbers hashed 256-n times. Publish the result (a,b). This pair is your signature for this 8-bit chunk.
  6. Collect up the 32 signatures from each chunk, and you have a 32*2*(256/8) = 2kb signature! This is 4x smaller than the usual Lamport signature.

Verifying

  1. Take the SHA-256 hash of the document you want to verify
  2. Split the 256-bit hash of the document into 32 8-bit chunks
  3. For each chunk, let the chunk's value from the hash be V, the signature pair of numbers be (a, b) and the corresponding public key pair be (Pa, Pb)
  4. Hash a and count the iterations until it equals Pa or it has been hashed 256 times. If it was hashed 256 times without reaching Pa, the signature is invalid. Save the number of iterations it took to reach Pa from a as i_a.
  5. Repeat step (4) for b, saving the number of iterations to reach Pb from b as i_b.
  6. If 256-i_a != i_b-1 or 256-i_a != V, this signature is invalid.
  7. If there are more chunks, check the next chunk starting with step (3)
  8. The signature is valid if all chunks are signed correctly.

Details

We trade off storage size for computation. Rather than having to compute 256 hashes to verify a 256-bit signature, we now must compute at least 256/8 * 256 = 8192 hashes. However, given that hash functions are intended to be fast and also don't require access to main memory, this is likely to be a good tradeoff for cachable chunk sizes.

Specifically, if n is the bits of the hash function and k is the bit size of each chunk:

  • (n/8)*2*(n/k) bytes is the size of the public key
  • n/k * 2^k is the number of hashes that must be computed to verify the key
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment