Disclaimer
This presentation tries to convey the big ideas in an easy-to-understand manner.
To keep things simple I'll be a little less formal when it comes to definitions and mathematical notation.
Why?
The Challenge
Create a digital signature for a single bit (\(0\) or \(1\)) using only a Cryptographic Hash function
Asymmetric Cryptography Recap
- Public Key \(pk\)
- Private Key \(sk\)
- Relationship between \(sk\) and \(pk\)
- Given \(sk\), it's easy to compute \(pk\)
- Given \(pk\), it's hard* to compute \(sk\)
\[ sk \rightarrow pk \]
\[ sk \not\leftarrow pk \]
Digital Signatures Recap
- Create signature \(\sigma\) over message \(m\) using Private Key \(sk\)
- Verify signature \(\sigma\) over message \(m\) via Public Key \(pk\)
\[ sign_{sk}(m) = \sigma \]
\[ verify_{pk}(m, \sigma) \overset{?}{=} \text{true} \]
Cryptographic Hash Function Recap
- Any output of \(H\) looks random
- \(H\) maps an arbitrary-length input \(m\) to a fixed-length output \(h\)
- An \(m\) always maps to the same \(h\)
- Given \(m\), it's easy to compute \(h\)
- Given \(h\), it's hard* to find \(m\)
\[ H(m) \rightarrow h \]
\[ m \not\leftarrow h \]
Given \(m\), it's easy to compute \(h\)
Given \(h\), it's hard to find \(m\)
-–-
Given \(sk\), it's easy to compute \(pk\)
Given \(pk\), it's hard to compute \(sk\)
Key Observation #1
Use one-wayness of Cryptographic Hash function to derive \(pk\) from \(sk\).
- Generate Private Key \(sk\) by sampling random bits
- Use Hash function to derive \(pk\) from \(sk\)
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H(sk) \]
Key Observation #2
We can hand out the public key \(pk\) and later on prove that we knew its corresponding private key \(sk\) by sharing it publicly.
\[ H(sk) \overset{?}{=} pk \]
(Like a Hash-Based Commitment Scheme)
Key Observation #3
A Private- and Public Key can be interpreted as a concatenation of multiple instances.
\[ sk_i \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ sk = sk_0 \mathbin\Vert sk_1 \mathbin\Vert \ldots \mathbin\Vert sk_n \]
\[ pk_i = H(sk_i) \]
\[ pk = pk_0 \mathbin\Vert pk_1 \mathbin\Vert \ldots \mathbin\Vert pk_n \]
Create a digital signature for a single bit (\(0\) or \(1\)) using only a Cryptographic Hash function
Simple Hash-Based Signature Scheme
- Generate two Private Keys \(sk_0\) and \(sk_1\)
- Derive two Public Keys \(pk_0 = H(sk_0)\) and \(pk_1 = H(sk_1)\)
- To sign bit \(0\), reveal \(sk_0\)
- To sign bit \(1\), reveal \(sk_1\)
- To verify that bit \(0\) was signed, check if \(H(sk_0) \overset{?}{=} pk_0\)
- To verify that bit \(1\) was signed, check if \(H(sk_1) \overset{?}{=} pk_1\)
Key Generation
\[ sk_0 \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ sk_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk_0 = H(sk_0) \]
\[ pk_1 = H(sk_1) \]
Signing
\[ m = \{0, 1\} \]
\[ sk_i = \begin{cases} sk_0 & \text{if } m = 0\\ sk_1 & \text{if } m = 1 \end{cases} \]
\[ \sigma = sk_i \]
Verification
\[ \sigma = sk_i \]
\[ pk_i = \begin{cases} pk_0 & \text{if } m = 0\\ pk_1 & \text{if } m = 1 \end{cases} \]
\[ H(\sigma) = H(sk_i) \overset{?}{=} pk_i \]
How do we sign messages with more than \(1 \text{ bit}\)?
Split message \(m\) into individual bits and repeat process for every single bit.
There's just one problem…
The longer the message, the more keys we have to generate!
The more keys there are, the longer the signature!
Rather than iterating over bits of message \(m\), we hash it first and iterate over the bits of the hash \(h = H(m)\).
Lamport-Diffie OTS (LD-OTS)
Analysis
Assuming \(H\) produces hashes of length \(256 \text{ bits}\)
- \(h = H(m) = 256 \text{ bits}\)
- \(sk = (2 \times 256) \times 256 \text{ bits} = 131.072 \text{ bits}\)
- \(pk = (2 \times 256) \times 256 \text{ bits} = 131.072 \text{ bits}\)
- \(\sigma = 256 \times 256 \text{ bits} = 65.536 \text{ bits}\)
\[ \begin{aligned} len_{\text{payload}} &= pk + \sigma \text{ bits} \\ &= 131.072 + 65.536 \text{ bits} \\ &= 196.608 \text{ bits} \\ &\approx 192 \text{ kb} \end{aligned} \]
Downsides
- Large \(sk\), \(pk\) and \(\sigma\)
- For every \(\sigma\), a new keypair needs to be generated and the \(pk\) shared
Why is it a One-Time Signature (OTS) Scheme?
\(\sigma_1 = 0001\)
\(\sigma_2 = 1000\)
-–-
\(\sigma' = 1001\)
How could we make it more efficient?
Cryptographic Hash Function Recap
- Any output of \(H\) looks random
- \(H\) maps an arbitrary-length input \(m\) to a fixed-length output \(h\)
- …
Main Idea #1
Given that for any input \(m\), the Hash function \(H\) produces a fixed-length random value \(h\), we could call it again-and-again (\(i\) times) to iteratively derive new values.
\[ H^i(m) = H(H(...H(m))) \]
If we have a hash \(h = H^i(m)\) in the middle of this "hash-chain", we can hash it again to derive its subsequent hash value \(H^{i+1}\).
\[ H^{i+1} = H(h) = H(H^i(m)) \]
Main Idea #2
We could use these hash-chains to derive multiple Public Keys \(pk_i\) from one Private Key \(sk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk_0 = sk \]
\[ pk_1 = H(sk) \]
…
\[ pk_i = H(...H(H(sk))) \]
If we have message values ranging from \(0\) to \(n\), then we can generate "interim" Public Keys \(pk_i\) for each potential message value \(m_i\).
\[ m_0 = 0 \rightarrow pk_0 = sk \]
\[ m_1 = 1 \rightarrow pk_1 = H(sk) \]
…
\[ m_{n} = n \rightarrow pk_{n} = H(...H(sk)) \]
If we know that our message can be represented as a value from \(0\) to \(n\), then we can chain \(n\) Hash function calls to generate a final public key \(pk\).
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H^n(sk) = H(...H(H(sk))) \]
Main Idea #3
If one gets \(pk_i\) and knows \(n\), then they can hash \(pk_i\) again \(n-i\) times to see if they end up with \(pk\).
Simple Winternitz-OTS
Key Generation
- Generate Private Key \(sk\) by randomly sampling bits
- Pick Hash function that produces outputs of lenthg \(n \text{ bits}\)
- Hash Private Key \(2^n - 1\) times to generate public key \(pk\)
Signing
- Hash message \(m\) to compute \(h = H(m)\)
- Interpret \(h\) as a number \(x\)
- Hash Private Key \(sk\) \(x\)-times to generate \(pk_x\) which is the signature \(\sigma\)
Verification
- Compute number of missing iterations to reach \(pk\) as \(j = (2^n - 1) - x\)
- Hash signature \(\sigma\) \(j\)-times and check if the result is equal to \(pk\)
Key Generation
\[ sk \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}^{n} \]
\[ pk = H^{2^n-1}(sk) = H(...H(H(sk))) \]
Signing
\[ h = H(m) \]
\[ x = h_{\text{10}} \]
\[ \sigma = H^x(sk) \]
Verification
\[ j = (2^n - 1) - x \]
\[ H^j(\sigma) \overset{?}{=} pk \]
Analysis
Assuming \(H\) produces hashes of length \(256 \text{ bits}\)
- \(h = H(m) = 256 \text{ bits}\)
- \(sk = 256 \text{ bits}\)
- \(pk = 256 \text{ bits}\)
- \(\sigma = 256 \text{ bits}\)
\[ \begin{aligned} len_{\text{payload}} &= pk + \sigma \text{ bits} \\ &= 256 + 256 \text{ bits} \\ &= 512 \text{ bits} \end{aligned} \]
\(512 \text{ bits}\) vs. \(196.608 \text{ bits}\)!
Problems
- Computationally Expensive
- Signature Forgeries
1. Computationally Expensive
Computing hashes over-and-over again is a computationally intensive task that can be slow.
Hash-chain computations are sequential and can't be parallelized.
Have multiple hash-chains rather than just one!
Make number of hash-chains configurable to trade-off on message size vs. work.
- Split message into \(l\) chunks of \(w \text{ bits}\) each
- Have one hash-chain for each chunk \(l_i\) that has max-length \(2^w\)
- Each hash-chain starts from a dedicated Private Key \(sk_i\)
- Each hash-chain ends with a dedicated Public Key \(pk_i\)
- Signing and verifying is done per hash-chain
2. Signature Forgeries
Given \(\sigma\), one can easily compute \(\sigma' = H(\sigma)\).
Compute a checksum and append it to the data that will be signed.
Checksum changes whenever any \(\sigma_i\) is changed.
\[ c = \sum_{i=0}^{l-1} ((2^w - 1) - x_i) \]
Sum of all the missing hash iterations necessary to reach \(pk_i\) for each individual chunk \(l_i\).
Whenever we forge a signature \(\sigma' = H(\sigma)\) for a chunk \(l\), \(c\) will be reduced by \(1\).
As \(c\) is also signed as \(\sigma_c = H^c(sk_c)\), we'd need to undo one hash iteration.
This isn't possible due to the one-wayness of Cryptographic Hash functions.
Winternitz-OTS
Full Example
To Be Continued…
This was just an introduction to the main ideas behind Hash-Based Signature Schemes, LD-OTS and Winternitz-OTS.
If this piqued your interested, then you can use the resources I used to make this presentation to dive deeper into the specifics.
Additional Resources
- Understanding Cryptography (2nd Edition) - Chapter 12.4
- Real-World Cryptography - Chapter 14.2
- SPHINCS+ - Step by Step
- An Overview of Hash Based Signatures
- Wikipedia - Lamport Signature
- Post-quantum cryptography: Hash-based signatures
- Hash-based Signatures: An illustrated Primer
- RFC 8391 - XMSS: eXtended Merkle Signature Scheme