5 ms·

I still don't understand how 4-byte CRCs are sufficient. Can someone explain?

billforsternz 10y ago
It's a statistical thing I suppose. 2^32 is 4 billion. So the chances of a garbled packet happening to have the same CRC as your original packet are 1 in 4 billion. Ultimately no system is completely impervious to unlikely freak collisions. For example even if you duplicated each packet there is still a chance your original and duplicated packet could freakishly be corrupted in exactly the same way. Having said all that I suppose a 64 bit CRC would get you a lot closer to monkeys typing Shakespeare territory.
- foota 10y ago
  After looking this up, this does not seem to be correct. I'll quote from Noway2 here http://www.eng-tips.com/viewthread.cfm?qid=263494 http://www.eng-tips.com/viewthread.cfm?qid=263494. "There are problems in trying to compute an error rate for which the CRC will fail to detect a bad communication. First, whether or not the error gets through will be highly dependent on the message. Second, CRC was designedto catch short bursts of contiguous bit errors. If the number of error bits is greater than this, there is a chance that CRC will fail. Here is an example: Consider these two hex strings: 1) 4B04B6F9BF002F002C002E002CD12E 2) 00260010BF002F002C002E002CD12E This is from an actual application and uses a 16 bit CRC algorithm to calculate a check value. In both cases the check value is 0x2ED1 (byte swapped). The CRC is the standard CRC used in Modbus, CCITT believe. Mathematically speaking, an X bit CRC will detect all consecutive bit errors less than X bits. When the error burst is bigger than X, the an X bit CRC will detect at a rate of 1-2^-X . For example,a 16 bit CRC has a 99.99847412109375% chance of catching the error burst. As you can see from my example above with the two strings, in reality, error bursts longer than X bits DO HAPPEN AND DO GET THROUGH!"
- deleted 10y ago
  [deleted]
- noselasd 10y ago
  Note that CRCs are designed to cover a certain message length, and are designed to catch bit errors within that message. The probability of a single bit error getting through is much much greater than a simple probability of 1 in 4 billion, the probability of catching 2 bit errors is somewhat less than catching 1 bit error (but still greater than 1 in 4 billion), and so on. (e.g. https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koop... argues CRC32 will detect all 1, 2 and 3 bit errors in an ethernet frame)
- hueving 10y ago
  Consider the volume of traffic going over big backbones though (e. g. 100gbps per second). Let's say one of the devices terminating this backbone has a piece of memory go bad that mangles IP payloads. At 8.3 Mpps (1500byte mtu line rate), a 1 in 4 billion chance would trigger on average every 9 minutes or so. That only assumes random probably with checksum collisions, but its interesting to see how the volumes of traffic moved around the Internet now have brought 'rare' events into much more frequency.
  - phicoh 10y ago
    The ethernet CRC is designed for packets on the wire. On the wire you have a bit error rate and sometimes burst errors. For bit errors, as long as no packet has 32 bit errors the CRC will always catch them. For burst errors, if the error sets all bits to zero (or to one) then the CRC will catch it. This is different from random memory corruption. Note that while a packet is the memory of a router you typically only have to TCP checksum to protect the packet, which is a rather weak 16-bit sum. So it is safe to assume that TCP will fail to detect many failures and if you care add a sha2 hash. Why sha2, because while md5 is perfectly fine for random errors, we should should make sure to kill all use of insecure hash functions. Otherwise they keep popping up in contexts where errors are not random.
  - kingosticks 10y ago
    Current generation Cisco and Nokia core routers seem to be around 400Gbps per slot. Juniper is claiming something wildly higher (up to ~1.5Tbps) so I guess they are ahead but double counting like some of these guys do. But yes, at these speeds, definitely more common, and getting more frequent all the time. http://www.juniper.net/techpubs/en_US/release-independent/junos/topics/reference/general/fpc-ptx5000-supported.html http://www.juniper.net/techpubs/en_US/release-independent/ju... EDIT: changed 3Tbps to 1.5Tbps.
  - wang_li 10y ago
    >Consider the volume of traffic going over big backbones though (e. g. 100gbps per second). Let's say one of the devices terminating this backbone has a piece of memory go bad that mangles IP payloads. At 8.3 Mpps (1500byte mtu line rate), a 1 in 4 billion chance would trigger on average every 9 minutes or so. I think someone would notice when only one packet per nine minutes successfully traverses their 100 Gbps core switch. So mission accomplished. :)
- acdha 10y ago
  One problem with simple CRC calculations is the question of whether it's correct to assume a random distribution of errors: if hardware failures produce clustered failures you might find that a particular device or model produces errors at much higher rates. ftp://ftp.cis.upenn.edu/pub/mbgreen/papers/ton98.pdf “First, a non-uniform distribution of data makes failure of the TCP checksum far more likely than one would naively expect. The undetected splice rate in our data for the 16-bit TCP checksum over real data is comparable to uniform data with a 10-bit checksum. Second, checksum distributions on modest amounts of real data are substantially different from the distributions one would anticipate for uniformly distributed data. This skewed distribution does result in significantly higher failure rates of the TCP checksum. In particular, if a router or host has a buffering problem that causes adjacent packets to be merged, the TCP checksum might fail .1% of the time rather than the 0.0015% of the time that purely random data distribution would suggest.” https://users.ece.cmu.edu/~koopman/pubs/paultisch05_dsn_crc_ultradependable.pdf https://users.ece.cmu.edu/~koopman/pubs/paultisch05_dsn_crc_... http://conferences.sigcomm.org/sigcomm/2000/conf/paper/sigcomm2000-9-1.pdf http://conferences.sigcomm.org/sigcomm/2000/conf/paper/sigco...

It's a statistical thing I suppose. 2^32 is 4 billion. So the chances of a garbled packet happening to have the same CRC as your original packet are 1 in 4 billion. Ultimately no system is completely impervious to unlikely freak collisions. For example even if you duplicated each packet there is still a chance your original and duplicated packet could freakishly be corrupted in exactly the same way. Having said all that I suppose a 64 bit CRC would get you a lot closer to monkeys typing Shakespeare territory.

foota 10y ago
After looking this up, this does not seem to be correct. I'll quote from Noway2 here http://www.eng-tips.com/viewthread.cfm?qid=263494 http://www.eng-tips.com/viewthread.cfm?qid=263494. "There are problems in trying to compute an error rate for which the CRC will fail to detect a bad communication. First, whether or not the error gets through will be highly dependent on the message. Second, CRC was designedto catch short bursts of contiguous bit errors. If the number of error bits is greater than this, there is a chance that CRC will fail. Here is an example: Consider these two hex strings: 1) 4B04B6F9BF002F002C002E002CD12E 2) 00260010BF002F002C002E002CD12E This is from an actual application and uses a 16 bit CRC algorithm to calculate a check value. In both cases the check value is 0x2ED1 (byte swapped). The CRC is the standard CRC used in Modbus, CCITT believe. Mathematically speaking, an X bit CRC will detect all consecutive bit errors less than X bits. When the error burst is bigger than X, the an X bit CRC will detect at a rate of 1-2^-X . For example,a 16 bit CRC has a 99.99847412109375% chance of catching the error burst. As you can see from my example above with the two strings, in reality, error bursts longer than X bits DO HAPPEN AND DO GET THROUGH!"
deleted 10y ago
[deleted]
noselasd 10y ago
Note that CRCs are designed to cover a certain message length, and are designed to catch bit errors within that message. The probability of a single bit error getting through is much much greater than a simple probability of 1 in 4 billion, the probability of catching 2 bit errors is somewhat less than catching 1 bit error (but still greater than 1 in 4 billion), and so on. (e.g. https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koop... argues CRC32 will detect all 1, 2 and 3 bit errors in an ethernet frame)
hueving 10y ago
Consider the volume of traffic going over big backbones though (e. g. 100gbps per second). Let's say one of the devices terminating this backbone has a piece of memory go bad that mangles IP payloads. At 8.3 Mpps (1500byte mtu line rate), a 1 in 4 billion chance would trigger on average every 9 minutes or so. That only assumes random probably with checksum collisions, but its interesting to see how the volumes of traffic moved around the Internet now have brought 'rare' events into much more frequency.
- phicoh 10y ago
  The ethernet CRC is designed for packets on the wire. On the wire you have a bit error rate and sometimes burst errors. For bit errors, as long as no packet has 32 bit errors the CRC will always catch them. For burst errors, if the error sets all bits to zero (or to one) then the CRC will catch it. This is different from random memory corruption. Note that while a packet is the memory of a router you typically only have to TCP checksum to protect the packet, which is a rather weak 16-bit sum. So it is safe to assume that TCP will fail to detect many failures and if you care add a sha2 hash. Why sha2, because while md5 is perfectly fine for random errors, we should should make sure to kill all use of insecure hash functions. Otherwise they keep popping up in contexts where errors are not random.
- kingosticks 10y ago
  Current generation Cisco and Nokia core routers seem to be around 400Gbps per slot. Juniper is claiming something wildly higher (up to ~1.5Tbps) so I guess they are ahead but double counting like some of these guys do. But yes, at these speeds, definitely more common, and getting more frequent all the time. http://www.juniper.net/techpubs/en_US/release-independent/junos/topics/reference/general/fpc-ptx5000-supported.html http://www.juniper.net/techpubs/en_US/release-independent/ju... EDIT: changed 3Tbps to 1.5Tbps.
- wang_li 10y ago
  >Consider the volume of traffic going over big backbones though (e. g. 100gbps per second). Let's say one of the devices terminating this backbone has a piece of memory go bad that mangles IP payloads. At 8.3 Mpps (1500byte mtu line rate), a 1 in 4 billion chance would trigger on average every 9 minutes or so. I think someone would notice when only one packet per nine minutes successfully traverses their 100 Gbps core switch. So mission accomplished. :)
acdha 10y ago
One problem with simple CRC calculations is the question of whether it's correct to assume a random distribution of errors: if hardware failures produce clustered failures you might find that a particular device or model produces errors at much higher rates. ftp://ftp.cis.upenn.edu/pub/mbgreen/papers/ton98.pdf “First, a non-uniform distribution of data makes failure of the TCP checksum far more likely than one would naively expect. The undetected splice rate in our data for the 16-bit TCP checksum over real data is comparable to uniform data with a 10-bit checksum. Second, checksum distributions on modest amounts of real data are substantially different from the distributions one would anticipate for uniformly distributed data. This skewed distribution does result in significantly higher failure rates of the TCP checksum. In particular, if a router or host has a buffering problem that causes adjacent packets to be merged, the TCP checksum might fail .1% of the time rather than the 0.0015% of the time that purely random data distribution would suggest.” https://users.ece.cmu.edu/~koopman/pubs/paultisch05_dsn_crc_ultradependable.pdf https://users.ece.cmu.edu/~koopman/pubs/paultisch05_dsn_crc_... http://conferences.sigcomm.org/sigcomm/2000/conf/paper/sigcomm2000-9-1.pdf http://conferences.sigcomm.org/sigcomm/2000/conf/paper/sigco...