Expected collisions for perfect 32bit crc

Tristan picture Tristan · Sep 9, 2010 · Viewed 15.4k times · Source

I'm trying to determine how my crc compares to an "ideal" 32bit crc.

So I ran my crc over 1 million completely random samples of data and collected the amount of collisions, I want to compare this number to the number of collisions I could expect from the "ideal" crc.

Does anyone know how to calculate the expected collision for an "ideal" 32bit crc?

Answer

srking picture srking · Oct 27, 2010

Compare your own CRC with 0x1EDC6F41 as your "ideal" reference.

Having said that, there is no ideal 32-bit CRC. Different polynomials have different collision characteristics depending on the length of data hashed. However, a paper by Castagnoli in 1993 found what is considered the best 32-bit CRC value over the broadest range of data lengths, which is 0x1EDC6F41. This polynomial is used by some network protocols like iSCSI and also the x86 CRC32 instruction.