Forked from karlgluck/Hash Ladders for Shorter Lamport Signatures.md
Created
June 11, 2021 03:37
Revisions
-
karlgluck revised this gist
Feb 21, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -96,7 +96,7 @@ Specifically, if `n` is the bits of the hash function and `k` is the bit size of * `n/k * 2^k` is the number of hashes that must be computed to verify the key | Hash Bits | Chunk Bits | Public Key Size | Relative Size | Hashes to Verify | Time to Verify @ 100 kHps | | --------- | ---------- | --------------- | -------------:| ----------------:| ------------------------- | | 256 | Lamport | 4096 bytes | 100 % | 256 | 2 milliseconds | | 256 | 8 | 2048 bytes | 50 % | 8192 | 8 milliseconds | | 256 | 12 | ~1400 bytes | ~30 % | ~90000 | ~ 1 second | -
Feb 21, 2014 . 1 changed file with 13 additions and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -88,11 +88,23 @@ While this can be parameterized to use different ladder chunks and different has 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 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 | Hash Bits | Chunk Bits | Public Key Size | Relative Size | Hashes to Verify | Time to Verify @ 100 kHps | | --------- | ---------- | --------------- | -------------:| ---------------- | ------------------------- | | 256 | Lamport | 4096 bytes | 100 % | 256 | 2 milliseconds | | 256 | 8 | 2048 bytes | 50 % | 8192 | 8 milliseconds | | 256 | 12 | ~1400 bytes | ~30 % | ~90000 | ~ 1 second | | 256 | 16 | 2048 bytes | 25 % | 1048576 | ~ 10 seconds | | 512 | Lamport | 32768 bytes | 100 % | 512 | 4 milliseconds | | 256 | 8 | 8192 bytes | 25 % | 16348 | 160 milliseconds | | 256 | 12 | ~5500 bytes | ~17 % | ~176128 | ~ 1.8 seconds | | 256 | 16 | 4096 bytes | 13 % | 1048576 | ~ 21 seconds | 100 kHps (100,000 hashes per second) was chosen from [this list](https://en.bitcoin.it/wiki/Mining_hardware_comparison) as most CPUs are able to do SHA-256 at at least the megahash-per-second level. -
Feb 21, 2014 . 1 changed file with 4 additions and 4 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -4,7 +4,7 @@ What's this all about? Digital cryptography! This is a subject I've been interested in since taking a class with Prof. [Fred Schneider](http://www.cs.cornell.edu/fbs/) back in college. Articles pop up on [Hacker News](http://news.ycombinator.com) fairly often that pique my interest and this technique is the result of one of them. Specifically, this is about [Lamport signatures](http://en.wikipedia.org/wiki/Lamport_signature). There are many signature algorithms (ECDSA and RSA are the most commonly used) but Lamport signatures are unique because they are formed using a hash function. Many cryptographers believe that this makes them resistant to attacks made possible by [quantum computers](http://en.wikipedia.org/wiki/Shor%27s_algorithm). How does a Lamport Signature work? ================================== @@ -17,11 +17,11 @@ How does a Lamport Signature work? 4. For each bit `i` of the hash from `0..256`: If the bit is a `0`, publish the `i`th number from secret set A. If it is a `1`, publish the `i`th number from secret set B. 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 that define if the value of a bit is 0 or 1 for each bit of the signature). Because hashes are one-way functions, it is [computationally hard](http://en.wikipedia.org/wiki/Computational_hardness_assumption) 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 processing power for an adversary to produce verifiable proof that you signed something other than what you actually signed. There are two 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 reveals more of your secret numbers and would allow an attacker to forge your signature for other documents. Fortunately, this is easily solved with a hash tree that merges many public keys down to a single "root". This is called the [Merkle signature scheme](http://en.wikipedia.org/wiki/Merkle_signature_scheme). 2. The signatures are enormous compared to ECDSA or RSA. Signing an `N`-bit hash requires `N` hashes of `N` bits each. That's 8 kib for signing a 256-bit hash or 32 kib for a 512-bit hash, which is around 1000x the size of a comparable ECSDA signature. How to Shorten Lamport Signatures -
Feb 16, 2014 . 1 changed file with 21 additions and 21 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -4,65 +4,65 @@ What's this all about? Digital cryptography! This is a subject I've been interested in since taking a class with Prof. [Fred Schneider](http://www.cs.cornell.edu/fbs/) back in college. Articles pop up on [Hacker News](http://news.ycombinator.com) fairly often that pique my interest and this technique is the result of one of them. Specifically, this is about [Lamport signatures](http://en.wikipedia.org/wiki/Lamport_signature). There are many signature algorithms (ECDSA and RSA are popular) but Lamport signatures are unique because they are formed around a hash function. Many cryptographers believe that this makes them resistant to attacks made possible by [quantum computers](http://en.wikipedia.org/wiki/Shor%27s_algorithm). How does a Lamport Signature work? ================================== [Here's the long version](http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description). This is the short copy without all the parameterization: 1. Come up with 2 sets (set A and set B) each containing 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 the bit is a `0`, publish the `i`th number from secret set A. If it is a `1`, publish the `i`th number from secret set B. 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 that define if the value of a bit is 0 or 1 for each bit of the signature). Because hashes are one-way functions, it is [computationally hard](http://en.wikipedia.org/wiki/Computational_hardness_assumption) 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 reveals 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](http://en.wikipedia.org/wiki/Merkle_signature_scheme). 2. The signatures are enormous compared to ECDSA or RSA. Signing an `N`-bit hash requires `N` hashes of `N` bits each. That's 8 kib for signing a 256-bit hash or 32 kib for a 512-bit hash, which is 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 [cryptographically secure pseudorandom number generator](http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) and compress the public key with a [hash list](http://en.wikipedia.org/wiki/Hash_list). No solution for shortening the public signature itself is published. That's what I hope to contribute with this article! The Other End of the Spectrum: A Hash Ladder -------------------------------------------- First, I present an toy demonstration of the algorithm. It is impractical to implement 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, `H_3bit(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 `H_5bit`. Each possible value of your 3-bit hash has a corresponding index in these chains of 5-bit hashes: ``` hash ix: [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" metaphor, with pairs of hashes making the "rungs". The hash is 5 bits to accommodate at least 20 unique non-colliding hashes. In this 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+ 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 `(A=27, B=23)` can verify that the pair `(A=8, B=14)` corresponds to the value `6`: + Take the A part of the signature pair, `8`. Hash it until it equals `27`, the A part of the public key. This takes `2` hashes. + Take the B part of the signature pair, `14`. Hash it until it equals `23`, the B part of the public key. This takes `7` hashes. + The length of each hash chain when producing the public key is `8`. This is public knowledge as an algorithmic constant. + `8-2 = 6`, which is the claimed hash. `7-1 = 6`, which is also the claimed hash. These values equal each other, and are thus the value that was signed by the owner of the public key `(A=27, B=23)` 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 `H_5bit(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 `H_5bit(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 in practice without some modification. Real hashes are at least 256 bits. 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. 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** in implementation, we need to chop up the hash to be signed into chunks with not very many bits (8-16) and create a ladder for each. With between `2^8` and `2^16` positions on the ladder, the ladder is 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 actual algorithm using 8-bit chunks and 256-bit hashes. ### Signing -
Feb 16, 2014 . 1 changed file with 22 additions and 19 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -17,39 +17,43 @@ How does a Lamport Signature work? 4. For each bit `i` of the hash from 0..256: If it is a 0, publish the `i`th number from secret set 0. If it is a 1, publish the `i`th 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](http://en.wikipedia.org/wiki/Computational_hardness_assumption) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) and compress the public key with a [hash list](http://en.wikipedia.org/wiki/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. @@ -76,20 +80,19 @@ While this can be parameterized to use different ladder chunks and different has 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 -
Feb 15, 2014 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -32,7 +32,7 @@ The Wikipedia article outlines ways to shorten the private key using a [random n The Other End of the Spectrum: A Hash Ladder -------------------------------------------- First, I present an toy demonstration of the algorithm that cannot be implemented for a number of reasons but shows the functionality. Then, I 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^sigbits + 2 = 2^3 + 2 = 10` times with a perfect random 5-bit oracle called `H5bit`: @@ -41,7 +41,7 @@ Assume you have a 3-bit signature of a document, `H3bit(document) = 6`. Pick two 23 <-- 19 <-- 20 <-- 4 <-- 13 <-- 17 <-- 3 <-- 14 <-- 28 <-- 29 ``` The last values, `(27, 23)` are your public key. Each possible value of your 3-bit hash has a corresponding index in this chain: ``` [0] [1] [2] [3] [4] [5] [6] [7] -
Feb 15, 2014 . 1 changed file with 44 additions and 16 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -29,29 +29,57 @@ How to Shorten Lamport Signatures The Wikipedia article outlines ways to shorten the private key using a [random number generator](http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) and compress the public key with a [hash list](http://en.wikipedia.org/wiki/Hash_list), but no solution for shortening the public signature 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 algorithm that cannot be implemented for a number of reasons but demonstrates the security proposition. Then, I 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^sigbits + 2 = 2^3 + 2 = 10` times with a perfect random 5-bit oracle called `H5bit`: ``` 12 --> 5 --> 24 --> 9 --> 1 --> 15 --> 10 --> 8 --> 11 --> 27 23 <-- 19 <-- 20 <-- 4 <-- 13 <-- 17 <-- 3 <-- 14 <-- 28 <-- 29 ``` The last values, `(27, 23)` are your public key. Each possible value of your 3-bit signature has a corresponding index in this chain: ``` [0] [1] [2] [3] [4] [5] [6] [7] 12 --> 5 --> 24 --> 9 --> 1 --> 15 --> 10 --> 8 --> 11 --> 27 23 <-- 19 <-- 20 <-- 4 <-- 13 <-- 17 <-- 3 <-- 14 <-- 28 <-- 29 ``` Find the pair of values corresponding to your document: `[6] = (8, 14)`. By publishing these values, anyone with the public key can verify that `(8, 14)` corresponds to the `H3bit(x) = 6` since `8` hashed twice is `27` and `14` hashed 7 times is `23`. However, 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 `i_a != 256-i_b` or `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 ------- -
Feb 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -14,7 +14,7 @@ How does a Lamport Signature work? 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 `i`th number from secret set 0. If it is a 1, publish the `i`th 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 un-invertible, there is no way other than brute force to forge the secret, random numbers you created in step 1 that would allow an attacker to change your signature. -
Jan 15, 2014 . 1 changed file with 0 additions and 0 deletions.There are no files selected for viewing
File renamed without changes. -
Jan 15, 2014 . 1 changed file with 0 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,5 +1,3 @@ What's this all about? ====================== -
Jan 14, 2014 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -24,7 +24,7 @@ Because hashes are un-invertible, there is no way other than brute force to forg There are two snags with using this scheme in practice: 1. This is a one-time signature. You can't sign anything else with the same public key, because doing so would reveal more secret numbers and potentially compromise your signatures. This is easily solved with a hash tree, which is called the [Merkle signature scheme](http://en.wikipedia.org/wiki/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 8kb for signing a 256-bit hash. Fortunately, the security factor for hash functions is better than that for other signature schemes so we need fewer bits to achieve the same security, but the size of the signature itself is still comparatively enormous. Moreover, the fact that it is quadratic in the number of bits of the hash is less than desirable. How to Shorten Lamport Signatures ================================= @@ -41,7 +41,7 @@ The Algorithm 3. For each chunk, generate a pair of (secret) random 256-bit numbers. These are your private key. 4. Hash each of these numbers 257 times. This final set of 64 hashes are your public key. Use a hash chain and this public key becomes just 256 bits. 5. To create your signature, examine each chunk again. Each chunk has a range `[0, 255]`, so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers `152+1=153` times and publish it. Hash the second of these numbers `(256-(152)) = 105` times and publish it. These two numbers are your signature for this 8-bit chunk. 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 4x smaller than the usual Lamport signature. How it Works ------------ -
Jan 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -24,7 +24,7 @@ Because hashes are un-invertible, there is no way other than brute force to forg There are two snags with using this scheme in practice: 1. This is a one-time signature. You can't sign anything else with the same public key, because doing so would reveal more secret numbers and potentially compromise your signatures. This is easily solved with a hash tree, which is called the [Merkle signature scheme](http://en.wikipedia.org/wiki/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 16kb for signing a 256-bit hash. Fortunately, the security factor for hash functions is better than that for other signature schemes so we need fewer bits to achieve the same security, but the size of the signature itself is still comparatively enormous. Moreover, the fact that it is quadratic in the number of bits of the hash is less than desirable. How to Shorten Lamport Signatures ================================= -
Jan 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -13,7 +13,7 @@ How does a Lamport Signature work? [Here's the long version](http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description). 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 of the hash: If it is a 0, publish the corresponding number from secret set 0. If it is a 1, publish the corresponding bit from secret set 1. Destroy all unused numbers. -
Jan 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -51,7 +51,7 @@ The two hash chains for each chunk form what I call a **hash ladder**. An easy w SECRET 1A --> H_1(1A) --> H_2(1A) --> ... --> H_256(1A) --> PUBLIC 1A = H_256(1A) PUBLIC 1B <-- H_256(1B) <-- H_255(1B) <-- ... <-- H_1(1B) <-- SECRET 1B ``` If the chain is 256 hashes long, the pair `(H_2(1A),H_255(1B))` represents the number 1. For an attacker to forge this and represent the number 0 or 2, a hash function in either the first or second chain respectively must be inverted. Given that cryptographic hash inversion is considered computationally hard, I claim that this scheme offers comparable security to the large-form Lamport signature. It's easy to verify that the signature is valid. For each chunk, simply hash each part of the provided signature pair the expected number of times and see if the results match the public key. -
Jan 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -51,7 +51,7 @@ The two hash chains for each chunk form what I call a **hash ladder**. An easy w SECRET 1A --> H_1(1A) --> H_2(1A) --> ... --> H_256(1A) --> PUBLIC 1A = H_256(1A) PUBLIC 1B <-- H_256(1B) <-- H_255(1B) <-- ... <-- H_1(1B) <-- SECRET 1B ``` If the chain is 256 hashes long, the pair `(H_2(1A),H_255(1B))` represents the number 1. For an attacker to forge this and represent the number 0 or 2, a hash function in either the first or second chain respectively must be inverted. Given that this is considered computationally hard, I claim that this scheme offers comparable security to the large-form Lamport signature. It's easy to verify that the signature is valid. For each chunk, simply hash each part of the provided signature pair the expected number of times and see if the results match the public key. -
Jan 14, 2014 . 1 changed file with 2 additions and 3 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -62,9 +62,8 @@ We trade off storage size for computation. Rather than having to compute 256 has 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 The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 6 additions and 8 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -60,13 +60,11 @@ 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 much faster than access to main memory, this is likely to be a good tradeoff for moderate 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 The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 7 additions and 6 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -61,11 +61,12 @@ 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 much faster than access to main memory, this is likely to be a good tradeoff for moderate 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 ``` The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 5 additions and 5 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -62,10 +62,10 @@ We trade off storage size for computation. Rather than having to compute 256 has 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 The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 8 additions and 8 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -39,33 +39,33 @@ The Algorithm 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 are your private key. 4. Hash each of these numbers 257 times. This final set of 64 hashes are your public key. Use a hash chain and this public key becomes just 256 bits. 5. To create your signature, examine each chunk again. Each chunk has a range `[0, 255]`, so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers `152+1=153` times and publish it. Hash the second of these numbers `(256-(152)) = 105` times and publish it. These two numbers are your signature for this 8-bit chunk. 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 8x smaller than the usual Lamport signature. How it Works ------------ The two hash chains for each chunk form what I call a **hash ladder**. An easy way to visualize it is the following. In this notation, `H_1(x) = H(x)` , `H_2(x) = H(H(x))`, `H_3(x) = H(H(H(x)))` and so on. ``` SECRET 1A --> H_1(1A) --> H_2(1A) --> ... --> H_256(1A) --> PUBLIC 1A = H_256(1A) PUBLIC 1B <-- H_256(1B) <-- H_255(1B) <-- ... <-- H_1(1B) <-- SECRET 1B ``` If the chain is 256 hashes long, the pair `(H_2(1A),H_255(1B))` represents the number 1. For an attacker to forge this and represent the number 1 or 3, a hash function in either the first or second chain repsectively must be inverted. Given that this is considered computationally hard, I claim that this scheme offers comparable security to the large-form Lamport signature. It's easy to verify that the signature is valid. For each chunk, simply hash each part of the provided signature pair the expected number of times and see if the results match the public key. 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 much faster than access to main memory, this is likely to be a good tradeoff for moderate 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 The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 13 additions and 8 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -39,28 +39,33 @@ The Algorithm 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 are your private key. 4. Hash each of these numbers 257 times. These hashes are your public key. Use a hash chain and this public key becomes just 256 bits. 5. To create your signature, examine each chunk again. Each chunk has a range `[0, 255]`, so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers 152 times and publish it. Hash the second of these numbers `(256-152) = 104` times and publish it. These two numbers are your signature for this 8-bit chunk. 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 8x smaller than the usual Lamport signature. How it Works ------------ This works because the two hash chains for each chunk form what I call a *hash ladder*. An easy way to visualize it is the following. In this notation, `H_0(x) = H(x)` , `H_1(x) = H(H(x))`, `H_2(x) = H(H(H(x)))` and so on. ``` SECRET 1A --> H_0(1A) --> H_1(1A) --> ... --> H_255(1A) --> PUBLIC 1A = H_256(1A) PUBLIC 1B <-- H_255(1B) <-- H_254(1B) <-- ... <-- H_0(1B) <-- SECRET 1B ``` If the chain is 256 hashes long, the pair `(H_1(1A),H_254(1B))` represents the number 1. For an attacker to forge this and represent the number 1 or 3, a hash function in either the first or second chain repsectively must be inverted. Given that this is not tractable, I claim that this is as secure as the large-form Lamport signature. It's easy to verify that the signature is valid. For each chunk, simply hash each part of the provided signature pair the expected number of times and see if the results match the public key. 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 much faster than access to main memory, this is likely to be a good tradeoff. 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 * n` is the number of hashes that must be computed to verify the key The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and the second part of each pair is implied since there is only 1 option. -
Jan 14, 2014 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -43,7 +43,7 @@ The Algorithm 5. To create your signature, examine each chunk again. Each chunk has a range `[0, 255]`, so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers 152 times and publish it. Hash the second of these numbers `(256-152) = 104` times and publish it. These two numbers are your signature for this 8-bit chunk. 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 8x smaller than the usual Lamport signature. This works because the two hash chains for each chunk form what I call a *hash ladder*. An easy way to visualize it is the following: ``` SECRET 1A --> H(1) --> H(2) --> ... --> H(255) --> PUBLIC 1A PUBLIC 1B <-- H(255) <-- H(254) <-- ... <-- H(1) <-- SECRET 1B -
Jan 14, 2014 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -44,10 +44,10 @@ The Algorithm 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 8x smaller than the usual Lamport signature. This works because the two hash chains for each chunk form what I call a "hash ladder". An easy way to visualize it is the following: ``` SECRET 1A --> H(1) --> H(2) --> ... --> H(255) --> PUBLIC 1A PUBLIC 1B <-- H(255) <-- H(254) <-- ... <-- H(1) <-- SECRET 1B ``` If the chain is 256 hashes long, the pair (H(2),H(254)) represents the number 2. For an attacker to forge this and represent the number 1 or 3, a hash function in either the first or second chain repsectively must be inverted. Given that this is not tractable, I claim that this is as secure as the large-form Lamport signature. Details -
Jan 14, 2014 . 1 changed file with 0 additions and 0 deletions.There are no files selected for viewing
File renamed without changes. -
Jan 14, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,66 @@ **work in progress** What's this all about? ====================== Digital cryptography! This is a subject I've been interested in since taking a class with Prof. [Fred Schneider](http://www.cs.cornell.edu/fbs/) back in college. Articles pop up on [Hacker News](http://news.ycombinator.com) fairly often that pique my interest and this technique is the result of one of them. Specifically, this is about [Lamport signatures](http://en.wikipedia.org/wiki/Lamport_signature). 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](http://en.wikipedia.org/wiki/Shor%27s_algorithm). How does a Lamport Signature work? ================================== [Here's the long version](http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description). 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! 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 of the hash: If it is a 0, publish the corresponding number from secret set 0. If it is a 1, publish the corresponding bit 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 un-invertible, there is no way other than brute force to forge the secret, random numbers you created in step 1 that would allow an attacker to change your signature. There are two snags with using this scheme in practice: 1. This is a one-time signature. You can't sign anything else with the same public key, because doing so would reveal more secret numbers and potentially compromise your signatures. This is easily solved with a hash tree, which is called the [Merkle signature scheme](http://en.wikipedia.org/wiki/Merkle_signature_scheme). 2. The signatures are huge compared to ECDSA or RSA. Signing an N-bit hash requires 2N hashes of N bits each... that's around 16kb for signing a 256-bit hash. Fortunately, the security factor for hash functions is better than that for other signature schemes so we need fewer bits to achieve the same security, but the size of the signature itself is still comparatively enormous. Moreover, the fact that it is quadratic in the number of bits of the hash is less than desirable. How to Shorten Lamport Signatures ================================= The Wikipedia article outlines ways to shorten the private key using a [random number generator](http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) and compress the public key with a [hash list](http://en.wikipedia.org/wiki/Hash_list), but no solution for shortening the public signature is published. That's where this article comes in! (cue trumpets) Let's jump right into how it works first, then I'll give a description of its properties and how I came up with it. This whole thing can be parameterized, but I am going to use real numbers for clarity. The Algorithm ------------- 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 are your private key. 4. Hash each of these numbers 256 times. These hashes are your public key. Use a hash chain and this public key becomes just 256 bits. 5. To create your signature, examine each chunk again. Each chunk has a range `[0, 255]`, so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers 152 times and publish it. Hash the second of these numbers `(256-152) = 104` times and publish it. These two numbers are your signature for this 8-bit chunk. 6. Collect up the `32*2` signatures from each chunk, and you have a `32*2*(256/8) = 2kb` signature! This is 8x smaller than the usual Lamport signature. This works because the two hash chains for each chunk form what I call a "hash ladder". An easy way to visualize it is the following: SECRET 1A --> H(1) --> H(2) --> ... --> H(255) --> PUBLIC 1A PUBLIC 1B <-- H(255) <-- H(254) <-- ... <-- H(1) <-- SECRET 1B If the chain is 256 hashes long, the pair (H(2),H(254)) represents the number 2. For an attacker to forge this and represent the number 1 or 3, a hash function in either the first or second chain repsectively must be inverted. Given that this is not tractable, I claim that this is as secure as the large-form Lamport signature. 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 `256/8 * 256 = 8192` hashes. Specifically: if `n` is the bits of the hash function and `k` is the bit size of each chunk (higher saves more space): `(n/8)*2*(n/k)` bytes is the size of the public key `n/k * n` is the number of hashes that must be computed to verify the key The usual Lamport algorithm is essentially a special case of `k=1`: every group is 1 bit, and we don't want to reveal the secret key.