Subject: TCP Checksum Interoperability

From: Chris Trobridge <[email-masked]>
Date: Fri, 5 Apr 2002 11:52:33 +0100

I writing to this list because the TCP workgroup was shutdown a while ago.
 
We have a compatibility problem between two third party implementations of
the TCP checksum.
 
The problem concerns the representation of zero, which has two 1-s
complement representations (0000 and ffff).
 
We don't have source to either stack but I managed to deduce the problem
from looking at a packet trace.  The receiver drops all datagrams containing
a TCP with a TCP checksum of ffff.
 
The receiver appears to be following the checksum procedure in the RFC
literally - ie zero checksum, recalculate and check that the result is the
complement of what the sender sent.  The problem is that the sender and
receiver don't agree about zero and hence the datagram is dropped silently.
 
My view is that the receiver is in error; it should be checking the special
case of 0.
 
All the receiver code I have seen doesn't work this way.  The normal
approach is to calculate the1-s complement sum with checksum in place and
check that this is zero.  The methods I konw always return just one
representation for zero, hence there is no special case.
 
Any thoughts?
 
Thanks,
Chris

-----------------------------------------------------------------------------------------------------------------
The information contained in this message is confidential and is intended 
for the addressee(s) only.  If you have received this message in error or 
there are any problems please notify the originator immediately.  The 
unauthorized use, disclosure, copying or alteration of this message is 
strictly forbidden. Baltimore Technologies plc will not be liable for direct, 
special, indirect or consequential damages arising from alteration of the 
contents of this message by a third party or as a result of any virus being 
passed on.

In addition, certain Marketing collateral may be added from time to time to 
promote Baltimore Technologies products, services, Global e-Security or 
appearance at trade shows and conferences.
 
This footnote confirms that this email message has been swept by 
Baltimore MIMEsweeper for Content Security threats, including
computer viruses.

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 5 Apr 2002 15:42:53 +0100 (BST)

See sections 3-5 of RFC1624 for discussion of the one's complement
problem for the IP header checksum. I presume similar applies for TCP,
although I don't know offhand if it's written down anywhere.

L.

> representation for zero, hence there is no special case.

stupid autoappended signatures below.

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

---

From: Rob Austein <[email-masked]>
Date: Fri, 05 Apr 2002 14:29:44 -0500

The last time this came up for a TCP implementation I used to
maintain, our interpretation of Robustness Principle applied to this
problem dictated that we shouldn't send segments with checksum fields
set to all ones (that is, we shouldn't send ~(+0)), but that we had to
accept either ~(+0) or ~(-0) in received segments.

Strictly speaking, either zero state is completely legal, but one is
(apparently) more surprising to most implementors than the other, due
to the implementation techniques that suggest themselves on most
modern processors.

---

From: Joe Touch <[email-masked]>
Date: Fri, 05 Apr 2002 11:41:08 -0800

> although I don't know offhand if it's written down anywhere.

RFC793 describes the use of 1's complement as the TCP checksum.

A TCP checksum can never be 0x0000, by the same argument of RFC1624, 
since the TCP header length is never 0.

Most of RFC1624 is clarification of the mathematical properties of 1's 
complement arithmetic; it's not specific to IP.

>>My view is that the receiver is in error; it should be checking the special

The sender is in error. As noted in RFC1624, there is no summation of 
words which yields a 1's complement sum of 0x0000 except all zeroes, 
which can't occur because (as above) the TCP header length renders at 
least one word non-zero.

Since the TCP checksum is the 1's complement of the sum, and 0x0000 
cannot occur as a sum, 0xffff cannot occur as a valid TCP checksum.

It would be useful to check the math used at the source to compute the 
checksum. It is likely there is an error, in particular, see section 3 
of RFC1624 for one typical one.

>>representation for zero, hence there is no special case.

As per RFC1624, that depends on the inputs. Nonzero inputs generate only 
0xffff as a sum, it takes all-zeroes to generate 0x0000 as a sum, but, 
as per above, that can't occur.

Joe

---

From: Joe Touch <[email-masked]>
Date: Fri, 05 Apr 2002 12:05:33 -0800

Rob Austein wrote:
> Strictly speaking, either zero state is completely legal, 

See my other post on this, as per RFC1624 section 3, only one state 
(0x0000) is legal as the complement of the checksum of non-zero data. 
TCP checksummed data must contain at least one nonzero word (the one 
with the TCP header length, which must be >=20).

The receiver is entirely justified in considering 0xffff as an error.

Jeo

---

From: Rob Austein <[email-masked]>
Date: Fri, 05 Apr 2002 16:30:23 -0500

> with the TCP header length, which must be >=20).

RFC 1624 is (a) Informational, and (b) wrong on this point.  RFC 793
just says that it's a one's complement sum and does not dictate the
specific method by which it must be calculated.  The implementation is
free to subtract zero from the sum at any point in the calculation to
prevent overflow (even if the particular value of zero chosen would
happen to look like a very large number when considered as an unsigned
value).  An implementation whose native word size is larger than 16
bits is also free to first perform the summation then fold the results
down to 16 bits by applying mod 0xFFFF.

And yes, once upon a time, people wrote checksum code that worked this
way, at least on PDP-10s at MIT.

The point is not that I'd advise anyone to use these techniques in new
code, just that they're completely legal given what the standard
actually says, and that the robustness principle therefore suggests
that we should accept the checksums they generate.

> The receiver is entirely justified in considering 0xffff as an error.

I disagree, for the reasons given above.

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 5 Apr 2002 23:13:47 +0100 (BST)

On Fri, 5 Apr 2002, Rob Austein wrote:

> RFC 1624 is (a) Informational,

It was written before BCP came into being with RFC1818. More accurate
to say that it's not standards-track... I imagine any update
today would be BCP.

> and (b) wrong on this point.  RFC 793
> specific method by which it must be calculated.
>
> The implementation is

and RFC791 claims ttl is in seconds, ergo I don't have to decrement
ttl because I know my traffic is on paths less than a second
long.

Cool reasoning.

L.

---

From: Rob Austein <[email-masked]>
Date: Fri, 05 Apr 2002 17:56:13 -0500

> ttl because I know my traffic is on paths less than a second

Covered by RFCs 1122 and 1812.

---

From: Matt Crawford <[email-masked]>
Date: Fri, 05 Apr 2002 17:13:57 -0600

> ttl because I know my traffic is on paths less than a second

You lose -- 791 says you have to subtract at least 1 from TTL even if.

However, I think that (A) most or all extant IPv4 routers violate 791
if they happen hold a packet more than a second, and (B) IPv6
invalidated TCP's correctness by defining the Hop Limit field to be a
hop limit and have no connection to time.  A TCP riding on IPv6 may
receive old segments an unbounded time later without any other
network element breaking a spec.

I said so at the time, but nobody cared.  No doubt Vint will take
care of multi-second hops for us.

---

From: Lloyd Wood <[email-masked]>
Date: Sat, 6 Apr 2002 00:37:35 +0100 (BST)

> Covered by RFCs 1122 and 1812.

gee, 1812 isn't a standards document, and is updated by 2644, which
isn't a standards document either.

as for 1122, it's requirements for internet hosts, not requirements
for internet gateways... but matt points out,

$ You lose -- 791 says you have to subtract at least 1 from TTL even if.

damn. should have picked an option case instead.

L.

---

From: Daniel Senie <[email-masked]>
Date: Fri, 05 Apr 2002 19:05:01 -0500

At 06:37 PM 4/5/2002, Lloyd Wood wrote:
>gee, 1812 isn't a standards document,

RFC 1812 status is Proposed Standard.

>  and is updated by 2644, which

RFC 2644 is a BCP. It updated one item in RFC 1812 (Router Requirements) 
which was later deemed an exceedingly bad idea.

>for internet gateways... but matt points out,

RFC 1812, Router Requirements, references 1122. Routers generally have to 
be valid hosts, too.

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

-----------------------------------------------------------------
Daniel Senie                                        [email-masked]
Amaranth Networks Inc.                    http://www.amaranth.com

---

From: Fred Baker <[email-masked]>
Date: Fri, 05 Apr 2002 17:17:48 -0800

At 03:13 PM 4/5/2002, Matt Crawford wrote:
>I think that (A) most or all extant IPv4 routers violate 791

for the record, while IPv4 TTL remains theoretically a time in seconds, it 
effectively became a hop count a long time ago. Thus sayeth RFC 1812:

5.3.1 Time to Live (TTL)

    The Time-to-Live (TTL) field of the IP header is defined to be a
    timer limiting the lifetime of a datagram.  It is an 8-bit field and
    the units are seconds.  Each router (or other module) that handles a
    packet MUST decrement the TTL by at least one, even if the elapsed
    time was much less than a second.  Since this is very often the case,
    the TTL is effectively a hop count limit on how far a datagram can
    propagate through the Internet.

    When a router forwards a packet, it MUST reduce the TTL by at least
    one.  If it holds a packet for more than one second, it MAY decrement
    the TTL by one for each second.

In that it "MAY" decrement the value, it also may choose not to...