There were several questions here regarding how surjective SHA-1/2 is, how many values don't have a pre-image from a fixed size input. I and others answered when modelling the relevant hash function as a random function. The question is can we venture if common hash functions are likely to collide more or less often than a ideal random function. Are there other cryptographic hash functions where we know exactly which direction such a weakness lies?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Somewhat relevant crypto.stackexchange.com/questions/48946 $\endgroup$– RukakoCommented Jul 10, 2017 at 16:24
-
$\begingroup$ Yes that was one of questions I was refering to in my question. $\endgroup$– Meir MaorCommented Jul 10, 2017 at 18:13
-
$\begingroup$ Your wording makes this difficult to answer. There's two topics here. one is hashes and pre-images. The other is PRFs and probabilities. I think you may need to specify an exact formulation for what you want the answer to be. We can be quite confident that the difference between the output of a PRF and a sequence of related hashes is quite small (well below 0.0000000001%), so the answers are likely to depend on the exact formulation you wish to use for comparing the two. $\endgroup$– Cort AmmonCommented Jul 10, 2017 at 20:12
-
$\begingroup$ I think you're mixing up PRFs and random functions. $\endgroup$– Luis CasillasCommented Jul 10, 2017 at 21:51
-
$\begingroup$ I guess i'm asking if we take a common cryptographic hash function which produces n bits, and hash all values 0..N-1 when N=2^n are we likely to get more or less thebln (1-1/e) N different values as in idealized hash. $\endgroup$– Meir MaorCommented Jul 11, 2017 at 3:51
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
If we could prove anything one way or another about this, it would be a remarkable result worthy of publication in a cryptography journal, since—except for length extension issues in MD hashes—we usually expect these collision-resistant hash functions to behave like good little random oracles.
Of course, there are other families of functions which are not collision-resistant but from which random choices of function have bounded collision probability, namely universal hashes like Poly1305 and GHASH. We can use these as building blocks for fast authenticators or PRFs. But I don't think you were asking about those.
answered Mar 10, 2019 at 21:31