7 ms·

How both TCP and Ethernet checksums fail (2015)

107 points by mmastrac 10y ago

aftbit 10y ago
Can we somehow strengthen the TCP checksum? Asking all application-layer protocols to implement something that the lower layer is supposed to give for free seems unwise in the long run.
- greglindahl 10y ago
  It's written into the standard, so it's hard to change. If you strengthen it, you run the risk of vendors offloading it and getting it wrong some tiny fraction of the time. The lower layer is always offloaded so it's actually the enemy: it's not an end-to-end checksum!
- fidget 10y ago
  The end to end principle says no, you need application level checksums anyway
wfunction 10y ago
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.
rwg 10y ago
At ${PREVIOUS_JOB}, I changed offices and discovered my window wasn't the only thing I lost in the move: SSH sessions kept dying with MAC errors. It happened with multiple computers with different NICs and running different OSes, so it wasn't computer-related. I tried swapping the patch cable, but that didn't change anything. On a whim, I took the faceplate off the box containing my (100 Mbps) Ethernet and phone jacks and discovered both drops were provided over a single four pair cable originally installed in the late 1980s. More alarmingly, the outer jacket of the cable had been cut off about a foot from the punchdowns on the backs of the keystone jacks, and the entire foot of conductors emerging from the jacket were all untwisted and balled up in the box. Cutting off about 10 inches of each wire, twisting the pairs back together, and punching the wires back down onto the backs of the jacks fixed the SSH problem...
- adrianN 10y ago
  You should have used Mosh /s
  - throwawayish 10y ago
    > Mosh /s Is also a unit of measurement - how many times per second the mosh session would've been broken if it were SSH /s
  - js2 10y ago
    While getting my degree I worked as a sys admin assistant for the CS dept. This was back in the 10BASE2 days. It wasn't unheard of find a professor who had re-arranged his or her office and needed a longer patch cable to connect their workstation, so he or she found some 75 ohm coax and used that and then wondered why the networking wasn't so good.
throwawayish 10y ago
I develop backup software among other things and I can tell you, that a CRC is neat but I've gotten many many reports where a CRC did not catch data corruption (but SHA-2 did). Much fewer reports indicated that the CRC caught it first. My conclusion: A CRC32 over a couple megs of data is only good enough to likely catch "gross" corruption, like truncating the data, not finer corruption like memory and disks tend to do it, especially when we're talking about bit rot. Also, unless you're using an optimized implementation -- and zlib is not optimized -- using eg. PCLMUL or at least a slice-by-4/8 variant it's a waste of time, because eg. BLAKE2b isn't much slower than zlib CRC, but will catch All The Corruption!1 [1] (Also, Python 3.6 added the full might of BLAKE2 to the stdlib, although it's the reference implementation and not some fancy SSE4/AVX(2) impl.) [1] A technical note: There is a tradeoff between checksum length and data length; with a good checksum increasing it's length eventually increases the error rate over the same medium (aka false positives [the checksum is corrupted instead of the data]). However, it's usually more important these days to be certain about correctness and not to minimize total indicated BER over a certain channel.
- beagle3 10y ago
  I think it's an apple to orange comparison; sha1 needs to be compared to a proper crc160, and sha2 to a proper crc256. (Proper means one nontrivial cycle e.g. An irreducible generating polynomial of a proper size) I would be surprised if there's material difference in error detection between sha2 and crc255 (other than the 1 bit difference). However, crc is useless against an adversary - preimage attacks are trivial. at the same size, it becomes an apple to apple comparison, and whether you choose depends on a speed/preimage requirements.
  - throwawayish 10y ago
    Of course it's a bit of an apples to oranges comparison. An interesting question about CRCs is whether you can implement them efficiently. CRC32 is possible with some help from the CPU (CLMUL as mentioned, or complete instructions for specific polynomials, like crc32c); eg. on Haswell you get to 14-16 GB/s with a CLMUL approach on CRC32. That's obviously much faster than the hashes I mentioned. With the zlib implementation, on the other hand, you only get about one GB/s and there it's really close to B2b already. Table-based approaches (classic zlib implementation, or slice-by-n, which needs n-times as many tables) would not work well with longer polynomials; the tables would outgrow L1/L2 cache sizes rather quickly. I'd have to think a bit about the tableless CLMUL approach.
kozak 10y ago
This is what worries me about the HTTP "Cache-Control: immutable" proposal. Immmutable caching should come with a reliable way to be sure that the content that is going to become immutable is not corrupted in the first place.
- fivesigma 10y ago
  Not if it's over HTTPS, since it guarantees data integrity. Corrupted network bits will cause the connection to fail. If the file is corrupted at the edge server an SRI attribute [1] can detect it, although it's not supported on IE and Safari yet. [1] https://developer.mozilla.org/en-US/docs/Web/Security/Subresource_Integrity https://developer.mozilla.org/en-US/docs/Web/Security/Subres...
  - m_eiman 10y ago
    Better hope the file isn't corrupted while it's being written to disk (or while read, or in place, or…). IMHO, anything immutable should be identified with its SHA2+ hash.
- NKCSS 10y ago
  Doesn't a CTRL-F5 force a refresh of all resources? That's always an option (although not one non-technical users will know).
  - kozak 10y ago
    Yep, a non-technical user will rather go buy a new computer than press Ctrl+F5.
avian 10y ago
Another case I've seen where TCP checksum failed was in old Eee PCs. There, the TCP checksum check on incoming packets was offloaded to the network interface. Unfortunately, some Linux driver and/or hardware bug occasionally corrupted the packet payload after the check passed. The workaround was to disable the hardware check. https://www.tablix.org/~avian/blog/archives/2010/10/eeepc_notworking/ https://www.tablix.org/~avian/blog/archives/2010/10/eeepc_no...
evanj 10y ago
See the previous Hacker News discussion from October 2015: https://news.ycombinator.com/item?id=10360108 https://news.ycombinator.com/item?id=10360108 I'm glad people are still interested in this subject. :)
woliveirajr 10y ago
Interesting that it took 4 months to get the kernel bug too.
gwern 10y ago
The end to end principle strikes again.

107 points by mmastrac 10y ago

Can we somehow strengthen the TCP checksum? Asking all application-layer protocols to implement something that the lower layer is supposed to give for free seems unwise in the long run.

greglindahl 10y ago
It's written into the standard, so it's hard to change. If you strengthen it, you run the risk of vendors offloading it and getting it wrong some tiny fraction of the time. The lower layer is always offloaded so it's actually the enemy: it's not an end-to-end checksum!
fidget 10y ago
The end to end principle says no, you need application level checksums anyway

wfunction 10y ago

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.

rwg 10y ago

At ${PREVIOUS_JOB}, I changed offices and discovered my window wasn't the only thing I lost in the move: SSH sessions kept dying with MAC errors. It happened with multiple computers with different NICs and running different OSes, so it wasn't computer-related. I tried swapping the patch cable, but that didn't change anything. On a whim, I took the faceplate off the box containing my (100 Mbps) Ethernet and phone jacks and discovered both drops were provided over a single four pair cable originally installed in the late 1980s. More alarmingly, the outer jacket of the cable had been cut off about a foot from the punchdowns on the backs of the keystone jacks, and the entire foot of conductors emerging from the jacket were all untwisted and balled up in the box. Cutting off about 10 inches of each wire, twisting the pairs back together, and punching the wires back down onto the backs of the jacks fixed the SSH problem...

adrianN 10y ago
You should have used Mosh /s
- throwawayish 10y ago
  > Mosh /s Is also a unit of measurement - how many times per second the mosh session would've been broken if it were SSH /s
- js2 10y ago
  While getting my degree I worked as a sys admin assistant for the CS dept. This was back in the 10BASE2 days. It wasn't unheard of find a professor who had re-arranged his or her office and needed a longer patch cable to connect their workstation, so he or she found some 75 ohm coax and used that and then wondered why the networking wasn't so good.

throwawayish 10y ago

I develop backup software among other things and I can tell you, that a CRC is neat but I've gotten many many reports where a CRC did not catch data corruption (but SHA-2 did). Much fewer reports indicated that the CRC caught it first. My conclusion: A CRC32 over a couple megs of data is only good enough to likely catch "gross" corruption, like truncating the data, not finer corruption like memory and disks tend to do it, especially when we're talking about bit rot. Also, unless you're using an optimized implementation -- and zlib is not optimized -- using eg. PCLMUL or at least a slice-by-4/8 variant it's a waste of time, because eg. BLAKE2b isn't much slower than zlib CRC, but will catch All The Corruption!1 [1] (Also, Python 3.6 added the full might of BLAKE2 to the stdlib, although it's the reference implementation and not some fancy SSE4/AVX(2) impl.) [1] A technical note: There is a tradeoff between checksum length and data length; with a good checksum increasing it's length eventually increases the error rate over the same medium (aka false positives [the checksum is corrupted instead of the data]). However, it's usually more important these days to be certain about correctness and not to minimize total indicated BER over a certain channel.

beagle3 10y ago
I think it's an apple to orange comparison; sha1 needs to be compared to a proper crc160, and sha2 to a proper crc256. (Proper means one nontrivial cycle e.g. An irreducible generating polynomial of a proper size) I would be surprised if there's material difference in error detection between sha2 and crc255 (other than the 1 bit difference). However, crc is useless against an adversary - preimage attacks are trivial. at the same size, it becomes an apple to apple comparison, and whether you choose depends on a speed/preimage requirements.
- throwawayish 10y ago
  Of course it's a bit of an apples to oranges comparison. An interesting question about CRCs is whether you can implement them efficiently. CRC32 is possible with some help from the CPU (CLMUL as mentioned, or complete instructions for specific polynomials, like crc32c); eg. on Haswell you get to 14-16 GB/s with a CLMUL approach on CRC32. That's obviously much faster than the hashes I mentioned. With the zlib implementation, on the other hand, you only get about one GB/s and there it's really close to B2b already. Table-based approaches (classic zlib implementation, or slice-by-n, which needs n-times as many tables) would not work well with longer polynomials; the tables would outgrow L1/L2 cache sizes rather quickly. I'd have to think a bit about the tableless CLMUL approach.

kozak 10y ago

This is what worries me about the HTTP "Cache-Control: immutable" proposal. Immmutable caching should come with a reliable way to be sure that the content that is going to become immutable is not corrupted in the first place.

fivesigma 10y ago
Not if it's over HTTPS, since it guarantees data integrity. Corrupted network bits will cause the connection to fail. If the file is corrupted at the edge server an SRI attribute [1] can detect it, although it's not supported on IE and Safari yet. [1] https://developer.mozilla.org/en-US/docs/Web/Security/Subresource_Integrity https://developer.mozilla.org/en-US/docs/Web/Security/Subres...
- m_eiman 10y ago
  Better hope the file isn't corrupted while it's being written to disk (or while read, or in place, or…). IMHO, anything immutable should be identified with its SHA2+ hash.
NKCSS 10y ago
Doesn't a CTRL-F5 force a refresh of all resources? That's always an option (although not one non-technical users will know).
- kozak 10y ago
  Yep, a non-technical user will rather go buy a new computer than press Ctrl+F5.

avian 10y ago

Another case I've seen where TCP checksum failed was in old Eee PCs. There, the TCP checksum check on incoming packets was offloaded to the network interface. Unfortunately, some Linux driver and/or hardware bug occasionally corrupted the packet payload after the check passed. The workaround was to disable the hardware check. https://www.tablix.org/~avian/blog/archives/2010/10/eeepc_notworking/ https://www.tablix.org/~avian/blog/archives/2010/10/eeepc_no...

evanj 10y ago

See the previous Hacker News discussion from October 2015: https://news.ycombinator.com/item?id=10360108 https://news.ycombinator.com/item?id=10360108 I'm glad people are still interested in this subject. :)

woliveirajr 10y ago

Interesting that it took 4 months to get the kernel bug too.

gwern 10y ago

The end to end principle strikes again.