# Hash-Based Signatures From First Principles \---- Philipp Muens - [muens.io](https://muens.io) X - [@pm**m**uens](https://x.com/pmmuens) TG - [@pmuens](https://t.me/pmuens) GH - [@pmuens](https://github.com/pmuens) --- ## 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 1. Public Key $pk$ 2. Private Key $sk$ 3. Relationship between $sk$ and $pk$ 4. Given $sk$, it's _easy_ to compute $pk$ 5. Given $pk$, it's _hard_* to compute $sk$ $$ sk \rightarrow pk $$ $$ sk \not\leftarrow pk $$ --- ## Digital Signatures Recap 1. Create signature $\sigma$ over message $m$ using Private Key $sk$ 2. 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$. 1. Generate Private Key $sk$ by sampling random bits 2. 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 --- 1. Generate two Private Keys $sk_0$ and $sk_1$ 2. Derive two Public Keys $pk_0 = H(sk_0)$ and $pk_1 = H(sk_1)$ 3. To sign bit $0$, reveal $sk_0$ 4. To sign bit $1$, reveal $sk_1$ 5. To verify that bit $0$ was signed, check if $H(sk_0) \overset{?}{=} pk_0$ 6. 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 --- 1. Large $sk$, $pk$ and $\sigma$ 2. 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 1. Generate Private Key $sk$ by randomly sampling bits 2. Pick Hash function that produces outputs of lenthg $n \text{ bits}$ 3. Hash Private Key $2^n - 1$ times to generate public key $pk$ --- ### Signing 1. Hash message $m$ to compute $h = H(m)$ 2. Interpret $h$ as a number $x$ 3. Hash Private Key $sk$ $x$-times to generate $pk_x$ which is the signature $\sigma$ --- ### Verification 1. Compute number of missing iterations to reach $pk$ as $j = (2^n - 1) - x$ 2. 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 --- 1. Computationally Expensive 2. 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](https://www.cryptography-textbook.com) - [Real-World Cryptography - Chapter 14.2](https://www.manning.com/books/real-world-cryptography) - [SPHINCS+ - Step by Step](https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/) - [An Overview of Hash Based Signatures](https://eprint.iacr.org/2023/411.pdf) - [Wikipedia - Lamport Signature](https://en.wikipedia.org/wiki/Lamport_signature) - [Post-quantum cryptography: Hash-based signatures](https://www.redhat.com/en/blog/post-quantum-cryptography-hash-based-signatures) - [Hash-based Signatures: An illustrated Primer](https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/) - [RFC 8391 - XMSS: eXtended Merkle Signature Scheme](https://www.rfc-editor.org/rfc/rfc8391.html) --- ## Thank You! \---- Philipp Muens - [muens.io](https://muens.io) X - [@pm**m**uens](https://x.com/pmmuens) TG - [@pmuens](https://t.me/pmuens) GH - [@pmuens](https://github.com/pmuens)