## Thursday, 7 April 2011

### 1's complement, if only I had a time machine...

I hate 1's complement arithmatic at the best of times, but the way it is done for IP, TCP, and UDP is slightly special even then.

It is a shame you cannot go back in time and fix some of the little and stupid things in life. See http://xkcd.com/567/

Basically, in 1's complement arithmatic a value of all 0's and all 1's are the same value giving two possible answers for "zero".

With checksums used for IP, UDP, and TCP, you make a 1's complement 16 bit sum (based on the checksum field set to 0x0000), and then store the inverse in the checksum. This means to check it you do a 1's complement 16 bit sum and check for an answer zero (i.e. 0x0000 or 0xFFFF).

That sounds so simple, but....

UDP has a special case. It allows (sensibly in my view) the option of "no checksum". This is where the fact there are two zeros is actually handy as you can use one of the zeros as a rogue valid to mean "no checksum". UDP uses 0x0000 as that value.

The problem is that the checksum algorithm does not prohibit the use of 0x0000 for TCP and IP checksums, which it so easily could have.

What is worse is that typical checksum calculations would never end up with 0x0000 as a total (unless all source bytes were 0x00) as it would not wrap 0xFFFF to 0x0000 without a carry set and hence going to 0x0001. This means that typically a checksum as stored (inverse of the sum) will use 0x0000 version of zero, normally. I do not think this is in fact mandated and the exact algorithm for how you do the 1's complement sum is not defined, and in 16 bit 1's complement 0x0000 means the same as 0xFFFF, so a sum algorithm that normalizes the answer to only use 0x0000 (and hence store 0xFFFF) would, in my opinion be valid.

The problem is that some systems do normalise the answer and some do not, so you encounter both 0x0000 and 0xFFFF in the real world. What is worse, is some stacks will check the checksum by working it out and comparing, rather than by working out a checksum including the stored checksum and checking it copmes out as (one of the values of) zero. So in fact some systems fail if 0xFFFF is stored in the checksum field rather than 0x0000.

This means, in effect, IP and TCP only ever store the 0x0000 version of zero, but for UDP you have to use the 0xFFFF version of zero instead as 0x0000 means "no checksum". I wonder how many stacks generate 0x0000 and get away with is as it just means 1 in 65535 packets are unchecksummed and so not checked. I bet that happens!

As a result the checksum generation and checking have to be different for UDP and for TCP/IP, which from a coding point of view is a total pain in the arse, especially when making NATing systems that adjust checksums in a generic way and now have to check if the packet is UDP or not to do their job.

It is further complicated in IPv6 by mandating that UDP 0x0000 is not allowed, but still the expected version of zero for IP and TCP! Arrrrrg.

In case you had not guessed, this meant a slight snag in the NAT code on the FB2700. Nobody had noticed for something like 6 months because it is pretty subtle in its effect, and more importantly FB2700 users are mostly sane enough to avoid NAT at all costs. Turns out I made the same mistake on the FB105, and only did not remember this stupidity because Cliff fixed it for me 9 years ago! I do now remember the same symptoms though, I just did not take in the implications properly I guess (that or I am losing my memory, which is more likely I expect).

If one (competant) person designed and coded this, they would have made it consistent for all uses of the checksum. The use of 1's complement as such is not that bad, and the availability of a rogue value is nice in some ways, but the inconsistent usage is a nightmare. I can only assume it is "design by committee" syndrome. IMHO the whole lot should have mandated one level for integrity checking at the packetisation over any medium (i.e. Ethernet) and not had checksums at IP or TCP/UDP anyway, but that is just my opinion.

Oh well...