# 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)
{"description":"Understanding Cryptography - 2nd Edition","title":"Hash-Based Signatures","contributors":"[{\"id\":\"900fe4b9-b2b6-4420-bc5a-13b14392e4f1\",\"add\":31787,\"del\":20096}]"}