An example of bad code that always stuck with me was the flawed CDDB disc id hash algorithm.[0]
I was reminded of that short-sighted decision every time I ripped a bunch of CDs and saw how importing song titles was not automatic because a dozen different discs had the same hash ids which resulted in collisions[1]. It ended up creating needless friction for millions that depended on that discid.
What's sad is I'm not even sure if one can extract any useful "lessons learned" from it! The programmer that wrote it was not an amateur script kiddie; he had a computer science degree from Uni California. Apparently, he didn't realize he was writing a flawed hash algorithm as he wrote it.
One could say that hash algorithms should be "peer reviewed". Well, he got unsolicited peer review that pointed how his homegrown hashing computation was flawed but he ignored the suggestion to improve it.
[0] >Ti Kan wanted to use a hash. He could have chosen something like CRC32, which would have given him a 32 bit number, yielding 4 billion unique IDs. Instead he wrote his own hash.
[...]
Ti Kan was made aware (not by me) of this problem back in 1994, and given a script to convert this format into a CRC32-based format, but he rejected it because the deployed base was too big. At that point it was probably in the high dozens. -- excerpt from http://quimby.gnus.org/circus/notes/cddb.html
I don't think any reasonable person would expect zero collisions. The weakness of CRC32 for even distribution of hash values was well-known. (CRC32's goal was a fast "checksum" instead of strong cryptographic hash.)
The point was CDDB's non-invented-here home-grown hash algorithm was worse than CRC32. He didn't extract the maximum entropy from the discs' metadata of song times to minimize future collisions.
Comments
An example of bad code that always stuck with me was the flawed CDDB disc id hash algorithm.[0]
I was reminded of that short-sighted decision every time I ripped a bunch of CDs and saw how importing song titles was not automatic because a dozen different discs had the same hash ids which resulted in collisions[1]. It ended up creating needless friction for millions that depended on that discid.
What's sad is I'm not even sure if one can extract any useful "lessons learned" from it! The programmer that wrote it was not an amateur script kiddie; he had a computer science degree from Uni California. Apparently, he didn't realize he was writing a flawed hash algorithm as he wrote it.
One could say that hash algorithms should be "peer reviewed". Well, he got unsolicited peer review that pointed how his homegrown hashing computation was flawed but he ignored the suggestion to improve it.
[0] >Ti Kan wanted to use a hash. He could have chosen something like CRC32, which would have given him a 32 bit number, yielding 4 billion unique IDs. Instead he wrote his own hash. [...] Ti Kan was made aware (not by me) of this problem back in 1994, and given a script to convert this format into a CRC32-based format, but he rejected it because the deployed base was too big. At that point it was probably in the high dozens. -- excerpt from http://quimby.gnus.org/circus/notes/cddb.html
[1] https://forums.macrumors.com/attachments/multiple-matches-jp...
[2] wiki: https://en.wikipedia.org/wiki/CDDB#How_CDDB_works
That advice is wrong too, a 32bit number would have been insufficient due to the birthday problem.
I don't think any reasonable person would expect zero collisions. The weakness of CRC32 for even distribution of hash values was well-known. (CRC32's goal was a fast "checksum" instead of strong cryptographic hash.)
The point was CDDB's non-invented-here home-grown hash algorithm was worse than CRC32. He didn't extract the maximum entropy from the discs' metadata of song times to minimize future collisions.
Exactly. Assuming 10 songs per CD, you should see your first collision after around 6500 CDs. If he did CRC64, it would be after 400 million CDs.
Why not use a SHA256 (or SHA512) then?
Because CDDB pre-dated the publication of SHA-* (2001) by at least 6 years.