`On Sun, 2014-12-07 at 15:06 +0100, Hannes Frederic Sowa wrote:> In case of openvswitch it shows a performance improvment. The seed> parameter could be used as an initial biasing of the crc32 function, but> in case of openvswitch it is only set to 0.NACK.This is the Fatal Error in thinking that Herbert was warning about.The seed parameter doesn't affect CRC32 collisions *at all* if the inputsare the same size.For fixed-size inputs, a non-zero seed is equivalent to XORing aconstant into the output of the CRC computation.for *different* sized inputs, a non-zero seed detects zero-paddingbetter than a zero one, but *which* non-zero value is also irrelevant;all-ones is the traditional choice because it's simplest in hardware.A CRC is inherently linear.  CRC(a^b) = CRC(a) ^ CRC(b).  This makesthem easy to analyze mathematically and gives them a number of niceproperties for detecting hardware corruption.But that same simplicity makes it *ridiculously* easy to generatecollisions if you try.One way of looking at a CRC is to say that each bit in the inputhas a CRC.  The CRC of a message string is just the XOR of the CRCsof the individual bits that are set in the message.Now, a CRC polynomial is chosen so that all of the bits of amessage have different CRCs.  Obviously, there's a limit: when themessage is 2^n bits long, it's not possible for all the bits tohave different, non-zero n-bit CRCs.But a CRC is a really efficient way of assigning different bit patternsto different input bits up to that limit.(Something like CRC32c is also chosen so that, for messages up to areasonable length, no 3-bit, 4-bit, etc. combinations have CRCs thatXOR to zero.)But, and this might be what Herbert was trying to say and I wasmisunderstanding, if you then *truncate* that CRC, the CRCs of themessage bits lose that uniqueness guarantee.  They're just pseudorandomnumbers, and a CRC loses its special collision-resistance properties.It's just an ordinary random hash, and thanks to the birthday paradox,you're likely to find two bits whose CRCs agree in any particular 8 bitswithin roughly sqrt(2*256) or 22 bits.Here are a few such collisions for the least significant 8 bits of CRC32c:Msg1	CRC32c		Msg2	CRC32c		Match1<<11	3fc5f181	1<<30	bf672381	811<<12	9d14c3b8	1<<31	dd45aab8	b81<<5	c79a971f	1<<44	6006181f	1f1<<15	13a29877	1<<45	b2f53777	77There's nothing special about the lsbits of the CRC.Within 64 bits, the most significant 8 bits have it worse:1<<5	c79a971f	1<<17	c76580d9	c71<<6	e13b70f7	1<<18	e144fb14	e11<<19	70a27d8a	1<<38	7022df58	701<<20	38513ec5	1<<39	38116fac	381<<13	4e8a61dc	1<<52	4e2dfd53	4e1<<23	a541927e	1<<53	a5e0c5d1	a5Now, I'd like to stress that this collision rate is no worse than any*other* hash function.  A truncated CRC loses its special resistance tothe birthday paradox (you'd have been much smarter to use 8-bit CRC),but it doesn't become especially bad.  A truncated SHA-1 will havecoillisions just as often.The concern with a CRC is that, once you've found one collision, you'vefound a huge number of them.  Just XOR the bit pattern of your choiceinto both of the colliding messages, and you have a new collision.For another example, if you consider the CRC32c of all possible 1-bytemessages *and then take only the low byte*, there are only 128 possiblevalues.It turns out that the byte 0x5d has a CRC32c of 0xee0d9600.  This endsin 00, so if I XOR 0x5d into anything, the low 8 bits of the CRCdon't change.Likewise, the message "23 00" has a CRC32c of 0x00ee0d96.  So you canXOR 0x23 into the second-last byte of anything, and the high 8 bits ofthe CRC don't change.`