5
$\begingroup$

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

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What is the probability of success? Same as the second pre-image attack of the hash function $H$? $\endgroup$
    – kelalaka
    Jul 19, 2020 at 17:33
  • 1
    $\begingroup$ @kelalaka: well, the only computationally difficult part of the attack is, in fact, finding a second preimage in $H$ to the value $A$; only with the restriction that the attacker has to chose either the $X$ or $Y$ inputs. Against the generic attack (which is brute force searching across the possible inputs), this is the same expected effort as the second preimage attack with no preconditions on the input. For cryptographical attacks against $H$, well, that'd depend on the details of the attack $\endgroup$
    – poncho
    Jul 20, 2020 at 2:26
  • $\begingroup$ Thanks, so nothing more than what I consider. $\endgroup$
    – kelalaka
    Jul 20, 2020 at 6:37
  • $\begingroup$ Does this mean that the second pre-image attack on the merkle signature is scheme is different from that of the merkle tree? what about using the intermediate nodes as the leaf nodes to create a new merkle tree with the same hash root? $\endgroup$
    – evernal
    Jul 20, 2020 at 6:46
  • $\begingroup$ @poncho Is this what you meant by the attacker has to find a Y given X and A such that A=H(X,Y) ? With reference to this crypto.stackexchange.com/questions/6441/… , are there any hash functions where this is possible? MD5 or any? $\endgroup$
    – evernal
    Jul 20, 2020 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.