1
$\begingroup$

Does combining those two different cryptographic hash functions in HMAC, when each hashes the same data separately, then saved together, guarantee zero possibily of a collision simultaneously or is the assumption false and the possibility is not equal zero even in theory?

$\endgroup$
5
12
$\begingroup$

There is no way to guarantee a hash function (or combination of hash functions) is free of collisions. This is due to the pigeonhole principle. As long as the input is larger than the output hash, some inputs will need to result in the same hash. There's no way to get around this.

Note that both SHA-512 and SHA3-512 are secure hash functions and there is no known way to generate collisions for them more efficiently than provided by the birthday paradox.

$\endgroup$
1
  • $\begingroup$ Will pick this as an answer. Thanks. $\endgroup$
    – user91960
    Jun 12 at 3:09
7
$\begingroup$

is the assumption false and the possibility is not equal zero even in theory?

It is known to be false; it is easy to show that there must exist two different images that both hash to a common value $X$ for SHA-512 and and both hash to a common value $Y$ for SHA-3-512, for some 512 bit values $X, Y$. In fact, we can show that there exists such a pair both with lengths no more than 1024 bits (128 bytes).

Now, finding such a pair, that's a bit trickier...

$\endgroup$
5
  • $\begingroup$ @jcaron I think it's due to the pigeonhole principle again, but it probably does not apply to all hash functions and it might not be possible to rigorously prove it. $\endgroup$
    – JohnEye
    Jun 11 at 10:16
  • 6
    $\begingroup$ @JohnEye: yes, it's the pigeonhole principle, and it can be applied to all hash function. It's easy to prove - one way is to look at the concatination of SHA-2-512(M) and SHA-3-512(M) as a single function with a 1024 bit output; if we consider $2^{1024}+1$ distinct inputs, there must be a pair with same 1024 bit output, which implies that the pair collides for both SHA-2-512 and for SHA-3-512 $\endgroup$
    – poncho
    Jun 11 at 12:50
  • $\begingroup$ Ah, I got confused a bit there and thought that you meant to say that a single input must have the same output for both hash functions at the same time, which is obviously not true. Makes sense now, thanks! $\endgroup$
    – JohnEye
    Jun 11 at 13:10
  • $\begingroup$ @JohnEye: actually, I tried to word things to try to avoid that possible confusion; obviously, that attempt was not successful - I'll reword it to try to be even more clear $\endgroup$
    – poncho
    Jun 11 at 13:29
  • $\begingroup$ I got confused too, now it's clearly not appicable to the case ("simultaniously," not solo) since "Not applying to the same output to both at the same time." $\endgroup$
    – user91960
    Jun 11 at 22:02

Your Answer

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