Official LimeWire 4.1 requests thread

[verdyp]

Originally posted by rkapsi
I've made a short test if it's worth to truncate the SHA1 URNs to 6 digits.

I vote against it: do you know the "birthday paradox" and is effect on strong hashes? (The birthday paradox is born from the fact that any classroom of only 24 children will have at least 1 pair of children with the same date of birthday; this is a proven mathematical effect).

It says that a cryptographically strong hash algorithm that can produce 2^n distinct values will happen to produce two identical hashes with a 50% chance by only hashing 2^(n/2) distinct files.

With 6 hex-digits, such hash would generate only 2^24 possible values, with a 50% chance of collision when hashing only 2^12 files (and provided that the hash algorithm is really cryptographically strong). That would mean hashing only... 4096 files before getting a collision.

If we say that there are about 200,000 hosts reachable at one time, and that each share a very modest average of 40 files, this means that we will need 200,000*40 possible distinct values, i.e. 4 millions (or 23 bits) with at most one pair of colliding files.

Add the connection time and the fact that there are millions of users of Gnutella which can introduce new files at any time, the need of distinct values goes over 2^32 possible hash values, and the hash must be twice larger (so at least 64 bits).

The cryptographic strength of SHA-1 is not 128 bits as you think but just above 64 bits (2 years ago it was estimated at about 96 bits, but cryptanalysis has shown that the strength was a bit lower). SHA-1 has still no been cracked, but it's one good reason why the European Union launched the NESSIE evaluation project and as well as the US government. An agreement was found with SHA-256 and Whirlpool... whose estimated cryptographic strength for now is at 192 bits. Tiger-160 was eliminated due to the evaluation time and implementation delay (its estimated 128 bits strength is not enough for the ten years that are coming). 128+160 bits "Bitprints" have a strength of about 192 bits, roughly identical to SHA-256.

Conclusion: we must not reduce the size of SHA-1 hashes to less than 128 bits...