Hacker News new | ask | show | jobs
by sbarker 2924 days ago
Collisions in modern, properly implemented algorithms are rare. http://everydayinternetstuff.com/2015/04/hash-collision-prob... https://www.google.com/amp/s/www.theregister.co.uk/AMP/2017/...
2 comments

Collisions for the entire hash are rare, but this is just a prefix of the hash. I imagine it is significantly more common for a collision in the prefix.
I maintain a library that talks to the Have I Been Pwned password database, which uses a 5-hexadecimal-digit prefix of the SHA1 hash.

Someone filed a PR asking to add a cache for HIBP's responses, and I did some quick math and came up with ~1200 as a birthday-paradox number for the first five digits of a SHA1 hex digest (assuming uniform/random distribution of hex digits).

If the bloom filter returns positive you check the HIBO DB by getting all the hashes with that prefix and check the returned list for the full hash.
The average number of hashes returned is 478

The smallest is 381 (hash prefixes "E0812" and "E613D")

The largest is 584 (hash prefixes "00000" and "4A4E8")

https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...

Little code running in the real world any given moment is modern or properly implemented.