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?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ In theory both of these have collisions. In practice, they do not have any collisions. $\endgroup$– hanshenrikCommented Jun 11, 2021 at 13:45
-
$\begingroup$ Your question is not clear, are you looking for the case that if the hash function used in the HMAC has a collision attack then HMAC is secure? Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken? $\endgroup$– kelalakaCommented Jun 11, 2021 at 17:20
-
$\begingroup$ duplicate of Can there be two hash functions without common collisions? and What is the probability to produce a collision under two different hash functions? $\endgroup$– kelalakaCommented Jun 11, 2021 at 18:21
-
$\begingroup$ kelalaka, SHA512 and SHA3-512 do not have a collision attack, specific is not general nor a broken hash MD5/SHA1 function as in the three links. $\endgroup$– user91960Commented Jun 11, 2021 at 22:13
-
$\begingroup$ @Quesha It is not really about existing attacks, rather the generic attacks as in the first link. The second one uses the existing attacks that can be rather easy to convert. $\endgroup$– kelalakaCommented Jun 11, 2021 at 22:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
5
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...
-
$\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$– JohnEyeCommented Jun 11, 2021 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$– ponchoCommented Jun 11, 2021 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$– JohnEyeCommented Jun 11, 2021 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$– ponchoCommented Jun 11, 2021 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$– user91960Commented Jun 11, 2021 at 22:02