Lamport signature: How many signatures are needed to forge a signature?

Question

Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never publish or use. Preferably she should delete them; otherwise, others gaining access to them would later be able to create false signatures.

If Lamport's signature scheme would be used incorrectly, say you would use it more than once. How many signatures of distinct messages would you need to forge a signature?

I'm thinking if you have one signature and then the "opposite" message (not really message but the message's hash sum) so every 0 in the first message is a 1 and 1 is 0. If you had those two signatures you would have everything you needed from Alice's private key.

But that's probably not realistic to think that you get exactly those two messages. Is there some general formula for how many signatures you would need?

Thanks!

Answer 1

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break.

A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer.

So if you use 256 pairs, which is a reasonable level, since it offers 256 bit security against second-preimage attacks, and 128 bits against collisions, practical attacks are possible once you use the same key three times, and it's trivial to find messages-signature pairs once you use it four times.

Note that at this point the attacker can't fully determine the message he wants to sign, he needs to try $2^{64}$ (after three sigs) or $2^{32}$ (after four sigs) different messages to find one that he can sign. This usually isn't a problem for the attacker, since many things he might want to sign have parts the attacker can choose freely.

Why does it halve after every signature?

When you observe a single signature, you know one hash from each pair. So to create a signature you need to have a message hash that matches every single bit of the signature.

When you observe two signatures, you know both hashes from half of the pairs, and only one hash from the other half. So the message hash only needs to match the half where you only know one.

When you observe three signatures, you know both hashes from 3/4 of the pairs, and only one hash from the remaining 1/4. Now you only need to match 1/4th of the original bits.

etc.

Answer 2

Given a set of (unhashed) Lamport signatures using the same key, an attacker can trivially forge a signature for any message whose $k$-th bit, for each $k$, is equal to the $k$-th bit of at least one of the signed messages.

For example, let's say I know the Lamport signatures for the following 16-bit messages using the same key:

$$ m_1 = 0001111101110001 \\ m_2 = 0111110000111111 $$

Now I can easily forge a signature for the message $$m^* = 0101111000110101$$ just by picking the appropriate numbers from the signatures for $m_1$ and $m_2$. In fact, I can do the same for any message of the form $0ab111cd0e11fgh1$, where the letters $a$ to $h$ denote arbitrary bits.

However, I have no way (short of breaking the hash used to derive the public key) to forge a signature for, say, the message $1001111101110001$ (which differs from $m_1$ only in the first bit), since I don't know the number corresponding to the bit $1$ in the first pair of the private key.

This means that, if I can choose the forged message $m^*$ freely, I can easily choose it differ from $m_1$ and $m_2$ only at bits where they differ from each other (at least as long as they differ in more than one bit). Similarly, if I can freely choose at least one of the messages $m_1$ and $m_2$ to be signed (while knowing the other), I can just choose it to be the binary complement of the other, thereby revealing the whole private key.

---

However, that only works if the messages are signed directly. If the Lamport signature scheme is instead used in the usual way, where the messages are first hashed, and the hash then signed, the attacker faces a much trickier problem: given the hashes $h_1 = H(m_1)$ and $h_2 = H(m_2)$, they need to find a message $m^*$ such that $h^* = H(m^*)$ shares each of its bits with at least one of $h_1$ and $h_2$.

On average, $h_1$ and $h_2$ will have about half of their bits in common, so $h^*$ will also need to match those bits. Thus, if the hashes are, say, 256 bits long, a brute force attacker will need to try about $2^{128}$ (give or take a few orders of magnitude, depending on how similar $h_1$ and $h_2$ happen to be) messages before they find one that they can forge a signature for.

If the attacker gets their hands on a third signature, for the hash $h_3 = H(m_3)$, that will cut their workload down to around $2^{64}$, since, on average, $h_3$ will differ from $h_1$ and $h_2$ at about half the bits where $h_1$ and $h_2$ match. A fourth signature will cut the attacker's workload down to $2^{32}$, a fifth to $2^{16}$, and so on.

Of course, this is assuming that the attacker cannot choose the signed messages. If they can, they can do some precomputation to try and find messages whose hashes differ at as many bits as possible. I'm finding it surprisingly difficult to calculate just much this would help, but a quick numerical test suggests that the rewards diminish quickly: for a 256-bit hash and one chosen message, naïvely testing about $2^{14}$ messages will easily increase the expected number of differing bits from 128 bits to about 160 bits, but any further gains come slower and slower. If the attacker gets to choose more than one of the signed messages, a birthday-style attack should help some, but it's hard to say how much.

---

In summary:

• If the messages are not hashed before signing, even two signatures with the same key will allow existential forgery with overwhelming probability. If the attacker can choose at least one signed message, they can recover the whole private key.

• If the messages are hashed, and not chosen deliberately based on their hash, each additional signature using the same key effectively halves the security of the signature scheme (= the logarithm of the expected number of hash evaluations require for existential forgery).

• If the messages are hashed, and at least some of them chosen by the attacker, this will reduce the security somewhat further; alas, I currently have no precise numbers to give for this case.

Answer 3

What do you mean by forge? If you are asking about (the common) existential forgery, then two message, signature pairs are enough, given that the messages differ in at least two bits.

As an example consider that you have the signatures for $m_1 = 1111$ and $m_2 = 1100$. Considering the preimages you now have, you can forge signatures for $m_3=1101$ and $m_4=1110$.