Is SHA-1 collision free on data up to 20 bytes long (lenght of hash / internal state)? That means that every input produce unique output, but you surely know that, i just write it in order my question to be accepted by the site :)

If yes - which other hash functions does it apply to and what is the corresponding maximal length?

  • 3
    $\begingroup$ Most likely not. See Is SHA-512 bijective when hashing a single 512-bit block?. The same arguments apply to SHA-1. $\endgroup$ – CodesInChaos Feb 28 '13 at 15:42
  • $\begingroup$ I don't see any answer there, only assumtions, that it is most likely not true, e.g. there is no proof either for it or for the opposite. Unfortunately, i can't comment there. $\endgroup$ – Smit Johnth Feb 28 '13 at 16:04
  • $\begingroup$ With the way we typically construct symmetric primitives the fastest way to prove it, is finding a collision with these properties, and that requires $2^{80}$ work. What's clear is that an ideal 160 bit hashfunction does have collisions with length 20 (with overwhelming probability), and we have not the tiniest amount of evidence suggesting that SHA-1 so broken that it doesn't have this property. $\endgroup$ – CodesInChaos Feb 28 '13 at 16:13
  • 1
    $\begingroup$ @mikeazo 1) I used exist in the mathematical sense, where you can show that something exists, without being able to actually construct it. (If the claim that there are collisions is actually true, then there exists a short proof for their existance) 2) Not with probability 1. You need $2^{160}+1$ in the worst case. But it's quite unlikely it will need more than $2^{90}$ operations. $\endgroup$ – CodesInChaos Feb 28 '13 at 20:23
  • 1
    $\begingroup$ @SmitJohnth That is because there is no mathematical proof. Modern hash functions have structures that aren't very exploitable mathematically, by design. The best we can do is either brute-force it and try to find a collision, but this is expensive (it's supposed to be infeasible, actually) or assume that SHA-1 is a perfect random function and use that to calculate the likelihood of bijection, and the duplicate's answers address both these approaches. There simply is no other known way on a non-broken hash function. $\endgroup$ – Thomas Feb 28 '13 at 22:05