6
$\begingroup$

I am studying Merkle Tree Construction for digital signature. I don't quite understand why we need collision resistant hash function for Merkle tree construction.

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask. However, does it implies longer public key, more works need to be done on verifier side?

is there a known attack on traditional Merkle tree that only uses second preimage resistant hash function?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask.

Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a preimage or a second preimage (depending on where in the hash scheme we're talking about) for one of a number of hashes.

Rather, it has to do with proof technique. As mephisto points out, if you're happy with the random oracle model (and its proof method), it's straightforward to design a simple HBS method that is secure (that is, you have to find a preimage or second preimage to break).

However, what XMSS tries to do is be secure in the concrete model; that is, they try to argue that, because the bitmasks randomize the input, that what you need to do is find a (second) preimage of an effectively random string.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's what I didn't figure out yesterday.... In the standard Merkle tree, you don't get a proof from 2nd preimage resistance because the inputs to the hash function are not random which in turn might allow easier attacks than true 2nd preimage attacks because the image of the function kind of shrinks on iteration. $\endgroup$
    – mephisto
    Commented May 4, 2017 at 8:04
  • $\begingroup$ Thank both memphiso and poncho. So if I understand it correctly, they are willing to increase public key size for better proof technique in concrete model? and require more works on verifiers as he has to $\oplus$ the concatenation before computing the hash? sorry i'm new... $\endgroup$
    – DiamondDuck
    Commented May 5, 2017 at 2:35
  • $\begingroup$ @DiamondDuck: actually, in the most recent version of XMSS, the public key doesn't grow that much; in (say) SHA-256 is the hash function, the seed adds only 32 bytes to the key. What it does cost you is time, What costs you is the time to compute all those random masks; that increases the time by a factor of 3 to 5 (depending on the operation you're performing; for the verification operation, it's a factor of 5) $\endgroup$
    – poncho
    Commented May 5, 2017 at 3:11
  • $\begingroup$ @poncho: you are right. I forget that we can use a seed to generate those bitmask. Thanks a lot. $\endgroup$
    – DiamondDuck
    Commented May 5, 2017 at 4:55
3
$\begingroup$

There is no known attack that an adversary can mount when he knows a collision for the hash function used in the tree. The reason is that the adversary cannot control the inputs to the hash function as these are selected by the user. So, mainly this is a proof issue and the bitmasks are artifacts of the proof-technique used. If you are happy with a random oracle model proof, then you can achieve some kind of bounds close to those that follow from second-preimage resistance.

Improve this answer
$\endgroup$
1
$\begingroup$

I was still confused about the bitmasks even after reading this discussion but found an explanation in https://eprint.iacr.org/2017/349.pdf:

These are situations where the attacker has a number of hash targets (such a values from the Merkle tree of valid signatures it has seen), and ’wins’ if he is able to find a preimage for any one of them. The idea is that the attacker selects an image, hashes it, and checks to see if the hash value happens to be any of the values he’s looking for. However, such a preimage would actually allow the attacker to generate a forgery only if it is a plausible image in the context of the signature scheme. By ensuring that an image would be a plausible image only in one place in one signature tree (by assigning different prefixes and suffixes for each use), this means that any image he generates could be a plausible preimage for only one place in the signature scheme; hence any such attack is effectively limited to only one hash target.

So if I understand this correctly the bitmasks are in fact used to lower the collision-resistance requirement.

Improve this answer
$\endgroup$

Your Answer

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

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