The QRL XMSS - Demystified
(This blog is under construction. Expect incomplete explanation.)
In the future, QRL might be moving to a different more smaller but quantum resistant signature scheme but nevertheless, I believe reverse engineering this piece of fascinating signature scheme might be worth a try.
A brief history of hash based one time signatures
The Leslie Lamport signature scheme
In 1979, Leslie Lamport (yes, that same guy who created \( \LaTeX{} \))
published a paper titled, "Constructing Digital Signatures from a One Way Function" where given a one way hash function \( F() \), a message \( m \), and a digest function \( G: M \rightarrow (1,\ldots,40)^{20} \), which generates a sequence
containing exactly 20 elements of values ranging from 1 to 40, a signature
can be constructed.
As an example, let's assume that our arbitrary message produces this digest
containing 20 elements:
\[ i = G(m) = (14,24,20,28,39,22,36,35,26,4,1,11,38,40,9,15,16,29,8,27)
\].
Given our keys is \( k = (k_0,\ldots,k_{39})\), our signature is \( \sigma
= (k_{i_0},\ldots,k_{i_{19}})\), which is:
\[ \sigma =
(k_{14},k_{24},k_{20},k_{28},k_{39},k_{22},k_{36},k_{35},k_{26},k_{4},k_{1},k_{11},k_{38},k_{40},k_{9},k_{15},k_{16},k_{29},k_{8},k_{27})
\]
Where \( k_n \) is used to denote the nth element in the sequence \( k
\).
Here, given the publicly available, \( \alpha = (F(k_0),\ldots,F(k_{39}))
\) the receiver can verify the signature is valid if \( F(\sigma_j) =
\alpha_{i_j} \) for \( j = 0,\ldots,19 \). Breaking down the notation "\(
\alpha_{i_j} \)", \( i_j \) is used to access the jth element in the
sequence \(i\) which is then used to access the element in the sequence
\(\alpha\), so that when \( j=5 \), \(i_j = 22 \) and the 22th element
in \( \alpha \) is \( F(k_{22}) \), thus \(a_{i_5} = F(k_{22}) \).
The Lamport-Diffie One Time Signature
On that same year, Ralph Merkle published a paper titled "A certified digital signature" where it discusses the Lamport-Diffie One Time Signature and
expanded the previous paper on bits. The idea is if \( y=F(x) \) is
the result of applying the hash function \( F \) on \( x \), then only the
originator of \( y \) can only know \(x\). If everyone knows \( y \) is from
the originator \( O \), then \( O \) revealing \( x \) must propagate some
information since only \( O \) must knows \( x \). Given \( x \),
everyone can verify this comes from \( O \) by computing \(F(x)\) and
comparing it with the publicly available \( y \) which comes from \( O \),
thus is the basis of this system.
Here, for Alice to sign a 4-bit message to Bob, Alice generates exactly 4
random secret keys.\((k_0, k_1, k_2, k_3) \) and publishes \( (F(k_0),
F(k_1), F(k_2), F(k_3)) \). To sign the message \(1101\), Alice reveals \(
(k_0, k_1, k_3) \) to sign the 1's bit. Here, we do not reveal \( k_2 \) and thus whatever key not revealed is automatically understood as
a 0 bit. So far so good but this suffers from the defect that Bob (the
receiver) can choose to disregard all hashes and it would still be a valid
signature. Bob can deny ever receiving all k's (turning 1's into 0's) even though he did.
This defect was foresaw and on that same paper, a solution was proposed,
quoting (emphasis mine):
Lamport and Diffie overcame this problem by signing a new message \( m' \),
which is exactly twice as long as \( m \) and is computed by concatenating
\( m \) with the bitwise complement of \( M \). That is, each bit \( M \) in
the original message is represented by two bits, \( m_i \) and the
complement of \( m_i \) in the new message \( m' \). Clearly, one or the
other bit must be a 0. To alter the message, Bob would have to turn a 0 into
a 1, something he cannot do.
So we would have to double our keys. Instead of signing a message \( 1101 \), we would have to create a new message with its bitwise complement appended like so \( 1101,0010 \) (where the comma is used to clarify the division of the message and its complement). And for each 1's bit in this new message, I reveal \( ( k_0, k_1, k_3, k_6 )\).
The above algorithm would be the same as what's normally demonstrated in the examples from the internet. That's generating 4 secret keys \( S_{0,0}\ , \ldots , S_{0,3} \) to sign the 0's bits and another 4 secret keys, \( S_{1,0}\ , \ldots , S_{1,3} \) to sign the 1's bits .
\[ S_0 = ( S_{0,0}, S_{0,1}, S_{0,2}, S_{0,3} ) \]
\[ S_1 = ( S_{1,0}, S_{1,1}, S_{1,2}, S_{1,3} ) \]
Each of those secret keys is then hashed individually with \( F \) (a one
way hash function) to produce \( P_{0,0}, \ldots , P_{0,3} \) and \(
P_{1,0}, \ldots , P_{1,3} \) such that \( P_{n,m} = F(S_{n,m}) \) which I publish.
\[ P_0 = ( F(s) \, | \, s \in S_0 ) \]
\[ P_1 = ( F(s) \, | \, s \in S_1 ) \]
Then depending on the bit \( m_i \) (the ith bit in message \( m\
\)), I choose to reveal \( S_{0,i} \) if \( m_i \) is 0, or \( S_{1,i} \) if
\( M_i \) is 1.
\[ \sigma = ( S_{n,i} \, | \, n = m_i \land i=0,1,2,3)\]
The Winternitz Improvement
Shortly before publication, Robert Winternitz of Stanford Mathematics
Department suggested a substantial improvement that trades space for time,
reducing the size of the signed message ultimately. Instead of publishing \(
F(x) \), we publish \( F^k(x) \) where the notation \( F^k(x)\) is used to
apply the function \( F \) on \( x \), \( k \) times:
\[ x \xrightarrow{F} F(x) \xrightarrow{F} F^2(x) \xrightarrow{F}
F^3(x)\]
is the same as:
\[ x \xrightarrow{F} F(x) \xrightarrow{F} F(F(x)) \xrightarrow{F}
F(F(F(x))) \].
Instead of publishing \( y=F(x) \), we publish \( y=F^{16}(x) \). This
gives us an ability to sign 4 more bits of data. To sign the message
\(0000\) we reveal \(x\). To sign the message \(1111\) (decimal 15), we
reveal \( F^{15}(x)\). In theory, we can pick to publish \(y=F^{256}(x)\) to
sign a total of 8-bits instead of \(F^{16}(x)\), thus trading more space for
time, but we'll stick to signing 16 values (0-15) in the next proceeding
sections. This 16 is called the Winternitz parameter (\(
w=16\)).
Notice that if \( F^6(x) \) is revealed, anyone can claim \( F^7() \) so we
would have to add a checksum at the end which we would have to also
sign.
A Toy Merkle Signature Scheme
We're pretty much ready to create our own simplest Merkle Tree Signature Scheme, a "toy" that is, but its simplicity stills captures the essence of the original XMSS without going through hell of prerequisites.The tree we'll be building has a height of 1, giving us the ability to sign 2 distinct messages.
And down the bottom again of this \( p_0,\ldots,p_{63} \), are the actual
secret keys, such that \( p_n = F^{16}(s_n) \), where \(s_n\) is a random
256-bit secret key.
Since we're currently at \( l0 \), our ots index is 0. How many secret keys
we'll need is explained below:
Since we'll be signing each 4 bits in the 256 bit message digest, we'll have
to generate \( 256/4 = 64 \) secret keys, each are also 32 bytes long. If
you recall from the previous section, I claimed that we'll need to add a
checksum at the end to prevent an attacker from claiming \( F^{k+1}(x) \)
given \( F^k(x) \), but it turns out if the hash of message is instead
signed, it should still be computationally hard to find a new message hash
that is legible for this kind of attack. I might be wrong, so if you want to
be extra carefull, double the keys and sign the bitwise complement of the
message digest.
Signing
Our signature is a 3 tuple, the ots_index, xmss_auths and wots_keys.
We'll keep it simple and sign the message "hello". This message has a sha256
sum of 0x2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824.
We'll append 0x00 (decimal 0), the current ots index and hash it again
giving 0x586f7f160c29d493245b6ffad87d7a1b2654a6ed95d7cd665ea27056b18e1298.
The base 16 of this hash has 64 elements and is just:
\[ b = (5, 8, 6, 15, \ldots , 8) \] and so on.
The checksum is just the sum of all elements in b which is jdjdjsj and the
base 16 of this checksum is:
\[ c = ( ) \]
The message we'll be signing in the end is:
\[ b' =
For \( i = 0,\ldots,63 \),
Comments
Post a Comment