Subject: Re: The TCP and UDP checksum algorithm may soon need updating

From: Craig Partridge <[email-masked]>
Date: Tue, 9 Jun 2020 13:31:58 -0600

Following up on notes from various folks, most notably John K. and
Christian H., about checksums and encryption-based integrity protection, I
wanted to make a couple of clarifying points.

* If you are not worried about an adversary who seeks to alter your data in
transit, then integrity protection is a lousy method for ensuring the
received data is correct.  The reality is that a checksum of width X bits
can potentially catch 10x as many errors as an integrity check of X bits
and will likely require 1/X computational power to compute.  The
requirement to make an integrity check proof against an adversary makes it
less good. [Happy to explain more -- just trying to keep this note short].

* Some folks have assumed the TCP checksum, at 16 bits, misses an error
about 1 in 2^16 times.  That's not correct.  There are classes of errors
that TCP catches 100% of the time (e.g. single-bit errors).  There are also
classes of errors that the TCP checksum misses about 1 in 2^10 times.  This
latter is because the TCP checksum is not terribly good -- a better
designed checksum would miss only about 1 in 2^16.

Thanks!

Craig

-- 
*****
Craig Partridge's email account for professional society activities and
mailing lists.

---

From: Nico Williams <[email-masked]>
Date: Tue, 9 Jun 2020 14:39:34 -0500

> less good. [Happy to explain more -- just trying to keep this note short].

While this is true, application developers who are affected by weak TCP
checksums don't really have a better option, since TLS is basically all
they really have off the shelf, they will get a) [many] more bits of
MAC, b) therefore more protection than a 16-bit checksum could provide,
c) more compute cost.

> designed checksum would miss only about 1 in 2^16.

2-bit errors do happen.

Nico
--

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 9 Jun 2020 12:48:03 -0700

On Tue, Jun 9, 2020 at 12:32 PM Craig Partridge <[email-masked]> wrote:

> * If you are not worried about an adversary who seeks to alter your data
> in transit, then integrity protection is a lousy method for ensuring the
> received data is correct.
>

I agree with this statement.

However, with that said, we *should* generally be worried about such an
adversary and so in general our protocols should have integrity protection
at some layer in the stack, and while inefficient, the adversarial
requirements also mean that the chance of detecting non-adversarial error
is also very high. As you note in your original email, the issue arises
when integrity check failures occur at a layer which cannot recover from
them (as has been noted, TLS over TCP but not QUIC). Faced with this, we
can do one of three things:

- Create higher layer recovery mechanisms which can recover from lower
layer failures (as Richard alluded to with TCP)
- Move to protocols which can recover from errors (e.g., QUIC)
- Improve the non-adversarial checksum (in this case the TCP checksum) so
that the chance of undetected non-adversarial error is very low (the topic
that kicked off this thread).

It's worth noting that the first two are already happening and will most
likely continue regardless of what happens at the lower layers (in part
because they need to take the lower layers as they are now).

-Ekr

---

From: Craig Partridge <[email-masked]>
Date: Tue, 9 Jun 2020 14:25:12 -0600

> > designed checksum would miss only about 1 in 2^16.
I'm not sure what the 2-bit errors happen point is.  Lest someone imagine
that bit errors are the issue...

Lots of errors happen.  1 bit, 2-bit, byte, entire packet buffers trashed,
bytes/words/sequences forced to all 0s and all 1s, chunks of packets erased
or duplicated....  Essentially anything that can go wrong in a
middlebox/router showed up -- data line timing errors, bad memory (in
varying sizes), pointers getting trashed such that other random data gets
added/deleted, etc.

Table 3 my 2000 paper with Jonathan Stone lists a huge range of errors in
that error and few of them were bit errors.

Craig

Craig