1
$\begingroup$

A 2nd preimage attack is possible on the standard Merkle tree as pictured below.

Merkle Tree

I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link. If then using a good hash function, it should be resistant to any kind of attacks.

However it would be preferable to have a tree structure where a change in L1 (even if it hashed to Hash0-0) would affect Hash0.

If such a tree structure is viable, it seems we could use it to reduce the digest size used, without necessarily reducing security to the same degree.

That is, if it is difficult to find a pre-image collision in a secure 256 bit digest with a 256 bit input, is it just as difficult to find a pre-image collision in a 128 bit digest when the 256 bit input is constrained by being used further up the tree?

To use a rubbish hash as an example. For MD5, it may be possible to find a pre-image collision for X. Is it harder if I ask you to find an input that hashes to X, where the input must also be used to create another pre-image collision at the parent/grandparent of X?

To illustrate my idea, see a simple example of what I imagine below. Everything except the red blocks would be 128 bit. 'Split & XOR' is splitting the 256 bit DATA block into two 128bit blocks and XORing them together.

Example idea

The aim being that the attacker (after seeing DATA0 and relevant auth path) cannot simply provide an alternative DATA1, as it will also need to 'Split & XOR' to create the correct parent block. The idea is the attacker is left to find the real 256 bits of DATA1, not just a pre-image for the 128 bits of HASH1.

Questions

  1. Is this a viable idea?
  2. Is such an idea (obviously not as rudimentary as mines) employed anywhere?
$\endgroup$
2
$\begingroup$

The problem is that your construction (the whole second picture) still constitutes a compressing function with 128bit output. Hence, we can find collisions at complexity about $t\cdot2^{64}$, where t is the runtime of your construction.

Indeed, it seems that a little misconception motivates your work: You sound as if it was harder to find a collision than a second-preimage. However, it is the other way around; finding a second-preimage is (generically) a lot harder than collision-finding. The complexity of a generic second-preimage attack is equal to that of a generic preimage attack. The complexity of a generic collision attack is only the square root of the complexity of a second-preimage or preimage attack.

$\endgroup$
2
  • $\begingroup$ Thank you for the response. I'm not being very clear (per usual) but the aim is to make 2nd/pre-image attacks more difficult. I.e. An attacker can find a pre-image, but the data making the correct hash also needs to "SPLIT&XOR" into the parent. I'm not sure if it adds much, but it can't be as simple as finding an unconstrained pre-image. On your 2nd point, I'm using "collision" when I should use "pre-image" in the question, I think. I'll try and edit. Obviously finding generic collisions doesn't attack a Merkle tree anyway. $\endgroup$
    – Modal Nest
    Dec 15 '20 at 9:58
  • $\begingroup$ You can try to analyze this, but you should note that the adversary is not forced to keep DATA0 in your example. In any case, you can think about the new hash function that is obtained from your construction by fixing DATA0. Assuming that your starting hash function has good random behavior, this behaves like a 128 to 128 bit hash and you did not really win much (except the constant factor overhead of making a call to the new hash cost 2 calls to the initial hash). $\endgroup$
    – mephisto
    Dec 16 '20 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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