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$ Somewhat relevant crypto.stackexchange.com/questions/48946 $\endgroup$ – Rukako Jul 10 '17 at 16:24
  • $\begingroup$ Yes that was one of questions I was refering to in my question. $\endgroup$ – Meir Maor Jul 10 '17 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 Ammon Jul 10 '17 at 20:12
  • $\begingroup$ I think you're mixing up PRFs and random functions. $\endgroup$ – Luis Casillas Jul 10 '17 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 Maor Jul 11 '17 at 3:51

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.


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.