How does second pre-image attack on Merkle Signature Scheme work?

Question

I understand that a second pre-image attack on the Merkle tree works by creating another Merkle tree using the intermediate nodes as the leaf nodes, and this will lead to the same root hash (public key) being constructed 1. However, I thought that there are two steps to verifying the signature.
Assuming, Winternitz is used as the one-time signature, the one-time signature is first being verified and then following the authentication path to get the root node. Assuming the attacker used the intermediate nodes as the leaf nodes, would this mean that he would have to use that intermediate node (hash of 2 child nodes) as the public key of the OTS.

I am confused as to how the OTS verification would work, does this mean that the attacker has to find a pre-image $x$ so that $H(x) = y$ where $y$ is the intermediate node?
Are there any reference papers talking about this attack on the Merkle signature scheme?

I understand the portion on the merkle tree attack, but for the merkle signature scheme, there is the portion of verifying the OTS first before traversing the tree to construct the root node. My question is on how the attacker can get past the OTS verification given that it seems he has to find a pre image

poncho · Answer

Hoes does second pre-image attack on Merkle Signature Scheme work?

Lets take a simple example; suppose the attacker sees a valid Merkle signature; in that signature, he sees the bottom-most Merkle tree node of the form:
$$A = H( B, C )$$
where $H$ is the Merkle tree combination function, $B$ and $C$ are the left and right child nodes, and $A$ is the node value.  He also obtains from that signature the authentication path from node $A$ to the root.
The attacker's goal is the generate a forgery; to do that, what he does is generate his own OTS private key, and the corresponding value $X$.  Then, the second pre-image attack is to find a value $Y$ with:
$$A = H( X, Y )$$
If he succeeds, then he can generate a forgery with any message he wants.
What he does is generate the OTS for that message with the public key $X$ (which he can do; he has the private key).
Then, to form the authentication path, the first node of the path is the value $Y$; the rest of the path is copied from the valid authentication path he has seen.
When the validator examines the forgery, he'll compute the OTS public key, which will result in the value $X$.  He will then walk up the authentication path; the first step will be computing $A = H(X, Y)$ (as $Y$ is the value he sees in the authentication path; the rest of the path will proceed precisely as the valid signature, resulting in the expected public key value, and so the signature validates.

How does second pre-image attack on Merkle Signature Scheme work?

One Answer

Add your own answers!

Ask a Question