0
$\begingroup$

Let's suppose I take 3 different types of hash functions and concatenate them for future safety so that: digest = Hash3( Hash2( Hash1( text )))

Does the birthday attack mean in this case that I must double the input data set size of every hash function starting from the end?

If so, does it mean that if the output hash function had to have a 128 bits digest, the middle one must have a 256 bits long digest, and the first one 512 bits in order to gain a collision resistance that takes 2^64 trials?

$\endgroup$
  • 1
    $\begingroup$ You may want to note that this is not what "concatenate" usually means. $\endgroup$ – SEJPM Aug 6 at 7:16
1
$\begingroup$

Hash3( Hash2( Hash1( text )))

The collision resistance of $H'(x):=H_3(H_2(H_1(x)))$ is most likely $\operatorname{CR}(H')=\min(\operatorname{CR}(H_3),\operatorname{CR}(H_2),\operatorname{CR}(H_1))$, that is the combined scheme is at most as collision resistant as any individual scheme. Of course it has to be admitted that for most choices of the three hash functions, you don't have enough control over the input of $H_2,H_3$ to exploit structural collisions.

So the two main strategies to find collisions in this construction are:

  • Find a structural collision for Hash1, i.e. something like what was found for SHA-1 or MD5, or
  • Find a generic collision against any of the three hash functions, i.e. run through $2^{n/2}$ messages for $n$ being the minimum of the hash function output lengths in bits. Note that if an intermediary has a small output, e.g. 128-bit then finding a collision there will propagate the collision to the end.

Does the birthday attack mean in this case that I must double the input data set size of every hash function starting from the end?

No, see above.

If so, does it mean that if the output hash function had to have a 128 bits digest, the middle one must have a 256 bits long digest, and the first one 512 bits in order to gain a collision resistance that takes 2^64 trials?

No, see above. Also note that we usually model hash functions as outputting random values and no matter what you do with that output, you can't deterministically make more messages than could have been generated. That is, if you have $2^{128}$ possible hash outputs, you can't magically, deterministically make $2^{256}$ possible inputs to the next hash function out of that.

$\endgroup$

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.