Subject: CRCs, Checksums and Error Detection

From: Phil Karn <[email-masked]>
Date: Thu, 9 Mar 2000 23:28:59 -0800

I just added this section in the "Reliability and Error Control" section.
I will keep editing the LINK document, adding new text and comments as
I get them, until tomorrow when I will send a snapshot to the ID editor
with enough time to make the deadline... --Phil

The TCP, UDP and IP protocols all use a simple 16-bit 1's complement
checksum algorithm to detect corrupted packets. The IP checksum
protects only the IP header, while the TCP and UDP checksums protect
both the TCP/UDP header and any user data. In TCP the checksum is
mandatory while it is optional in UDP.

These checksums are not very strong from a coding theory standpoint.
But they are easy to compute in software, and various proposals to
replace them with stronger checksums have failed. Experience has shown
that nearly all subnetworks that carry the Internet protocols have a
very low undetected error rate, so the existing Internet checksums are
rarely called upon to catch an error. Most of the errors caught by the
Internet checksum are generally the result of hardware or software
failure than of a subnetwork transmission error. This lowers the
motivation to overcome the performance and especially the backward
compatibility problems of a new, stronger Internet checksum.

The typical IP subnetwork implements an internal error detection code that
discards packets failing this check instead of delivering them to
the IP layer. A 16-bit cyclic redundancy check (CRC) is usually the
minimum, and this is known to be considerably stronger than the 16-bit
standard Internet checksum. The Point-to-Point Protocol (PPP) uses a
16-bit CRC, often in conjunction with the V.42bis error control
provided in a typical dialup modem. 802.3/Ethernet uses a 32-bit CRC
that is considerably stronger, and many subnetworks (notably dialup
modem, mobile radio and satellite) also incorporate forward error
correction, often in hardware.

Any new subnetwork designed to carry IP should therefore provide error
detection at least as strong as a 16-bit CRC and preferably stronger.
Note that while this will achieve a very low undetected packet error
rate, this will not (and need not) achieve a very low packet loss rate
as the Internet protocols are better suited to dealing with lost
packets than with corrupted packets.

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 10 Mar 2000 14:20:04 +0000 (GMT)

> mandatory while it is optional in UDP.

Fine for v4, but needs something about IPv6's different behaviour - no
IP checksum, and the UDP checksum is no longer optional (UDP Lite
proposals aside).

L.

<[email-masked]>PGP<http://www.ee.surrey.ac.uk/Personal/L.Wood/>

---

From: Dan Grossman <[email-masked]>
Date: Fri, 10 Mar 2000 12:03:09 -0500

> compatibility problems of a new, stronger Internet checksum.
Aside:  wouldn't strict application of the end-to-end principle indicate that
strong end-to-end mechanisms are needed to provide assurance of accurate data 
transfer? (Don't bother to answer this until after the deadline :-)

> 16-bit CRC, often in conjunction with the V.42bis error control
The correct reference is to PPP over HDLC Framing, RFC 1622.  The 16 bit CRC
is the default, and a 32 bit CRC is an LCP option.  

> provided in a typical dialup modem. 802.3/Ethernet uses a 32-bit CRC
Ethernet is but one example.  Others that come to mind include AAL5/ATM, 
FDDI, Token Ring, PPP over SONET/SDH.

> detection at least as strong as a 16-bit CRC and preferably stronger.
I think we should make a stronger statement, and say 'at least as strong as
as the CRC-32 specified in ISO/IEC 3309:1991(E), "Information Technology -
         Telecommunications and information exchange between systems -
         High-level data link control (HDLC) procedures - Frame
         structure", International Organization For Standardization,
         Fourth edition 1991-06-01.
The reason for being specific is that other 32-bit CRCs exist (but are not 
widely implemented) which do not have as good error detection properties.

You might also want to mention something to the effect that if the subnet 
designer chooses to invent their own error detecting codes, they need to be 
very careful about their coding theory, and it's probably wiser to just reuse 
the CRC-32 defined for HDLC.

You can also mention that CRCs do not have very good error detection 
properties in the presence of error bursts or deletions longer than the 
generator polynomial (or is it the generator polynomial - 1?).  Use a CRC to 
match and/or include other ways (such as a length field) to detect deletions 
if they are possible in the subnet.

---

From: Joe Touch <[email-masked]>
Date: Fri, 10 Mar 2000 09:15:44 -0800

> compatibility problems of a new, stronger Internet checksum.

My understanding is that these checksums either "are intended to"
or "in practice usually catch only" software errors, not link errors.
On the original nodes, they were for memory corruption, etc. Does 
anyone recall whether they were ever intended to find link errors too?

(if not, the wording in paragraph 1 might be softened)

> packets than with corrupted packets.

This appears to assert false positives are better than false negatives,
e.g., that turning the "drop" knob lower is bad when it lets through
bad packets. If so, it may be useful to state it directly.

Joe

---

From: Phil Karn <[email-masked]>
Date: Fri, 10 Mar 2000 09:51:41 -0800

>The correct reference is to PPP over HDLC Framing, RFC 1622.  The 16 bit CRC

That's 1662, not 1622.

Phil

---

From: Phil Karn <[email-masked]>
Date: Fri, 10 Mar 2000 09:45:22 -0800

>transfer? (Don't bother to answer this until after the deadline :-)

I'll answer it anyway. Yes, they do. But this doesn't really argue for
changing TCP. 

For some time I've thought it would be a good idea for application
layer protocols like FTP, SMTP and HTTP to exchange MD5 (or similar)
hashes of their transferred files as a final end-to-end integrity
check. (I implemented a XMD5 command in my own FTP server many years
ago).  TCP is often not implemented in a sufficiently end-to-end
fashion, as in some OSes you can have truncated files that aren't
indicated as such to the user.

Phil

---

From: Phil Karn <[email-masked]>
Date: Fri, 10 Mar 2000 10:04:19 -0800

>the CRC-32 defined for HDLC.

There are even stronger alternatives, so I don't want to specifically
mandate the 32-bit CRC. E.g., in concatenated coding systems with a
Reed-Solomon outer code, the usual number of parity bytes chosen for
the RS code will provide an extremely low undetected error rate, much
lower than for a 32-bit CRC. These codes are frequently used on
satellite channels.

>generator polynomial (or is it the generator polynomial - 1?).  Use a CRC to 

Well, the worst-case failure rate of a CRC is generally on the order
of 1/2^N, where N is the number of bits in the remainder. As I recall,
they do better when the number of errors is less than N, i.e., they
detect them all. So yeah, CRCs don't do as well on long error bursts,
but that's relative to the short bursts where they're 100% effective.

I think 1/2^32 (worst case) is small enough to suit us, don't you
think?

Phil

---

From: Dan Grossman <[email-masked]>
Date: Fri, 10 Mar 2000 13:23:01 -0500

> lower than for a 32-bit CRC. These codes are frequently used on
Point taken.  On the other hand, I vividly recollect an ancient war where the 
CRC in question was so poorly designed that it could not detect any odd-length 
error burst.  So, yeah, wiser to just reuse an existing error detecting code.
> but that's relative to the short bursts where they're 100% effective.
I didn't intend to get to that level of detail, but now that you've written it 
down, maybe it would be better to put it in the draft.
> I think 1/2^32 (worst case) is small enough to suit us, don't you
Sure.  1/2^16 probably isn't, though.  At least if it's my financial data 
that's being protected.

Dan