Network Working Group A. Rijsinghani, Editor Request for Comments: 1624 Digital Equipment Corporation Updates: 1141 May 1994 Category: Informational
Computation of the Internet Checksum via Incremental Update
Status of this Memo
This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
Abstract
This memo describes an updated technique for incremental computation of the standard Internet checksum. It updates the method described in RFC 1141.
Incremental checksum update is useful in speeding up several types of operations routinely performed on IP packets, such as TTL update, IP fragmentation, and source route update.
RFC 1071, on pages 4 and 5, describes a procedure to incrementally update the standard Internet checksum. The relevant discussion, though comprehensive, was not complete. Therefore, RFC 1141 was published to replace this description on Incremental Update. In particular, RFC 1141 provides a more detailed exposure to the procedure described in RFC 1071. However, it computes a result for certain cases that differs
Rijsinghani [Page 1]
RFC 1624 Incremental Internet Checksum May 1994
from the one obtained from scratch (one's complement of one's complement sum of the original fields).
For the sake of completeness, this memo briefly highlights key points from RFCs 1071 and 1141. Based on these discussions, an updated procedure to incrementally compute the standard Internet checksum is developed and presented.
HC - old checksum in header C - one's complement sum of old header HC' - new checksum in header C' - one's complement sum of new header m - old value of a 16-bit field m' - new value of a 16-bit field
As RFC 1141 points out, the equation above is not useful for direct use in incremental updates since C and C' do not refer to the actual checksum stored in the header. In addition, it is pointed out that RFC 1071 did not specify that all arithmetic must be performed using one's complement arithmetic.
Finally, complementing the above equation to get the actual checksum, RFC 1141 presents the following:
HC' = ~(C + (-m) + m') = HC + (m - m') = HC + m + ~m' -- [Eqn. 2]
Although this equation appears to work, there are boundary conditions under which it produces a result which differs from the one obtained by checksum computation from scratch. This is due to the way zero is handled in one's complement arithmetic.
In one's complement, there are two representations of zero: the all zero and the all one bit values, often referred to as +0 and -0. One's complement addition of non-zero inputs can produce -0 as a result, but never +0. Since there is guaranteed to be at least one
Rijsinghani [Page 2]
RFC 1624 Incremental Internet Checksum May 1994
non-zero field in the IP header, and the checksum field in the protocol header is the complement of the sum, the checksum field can never contain ~(+0), which is -0 (0xFFFF). It can, however, contain ~(-0), which is +0 (0x0000).
RFC 1141 yields an updated header checksum of -0 when it should be +0. This is because it assumed that one's complement has a distributive property, which does not hold when the result is 0 (see derivation of [Eqn. 2]).
The problem is avoided by not assuming this property. The correct equation is given below:
Consider an IP packet header in which a 16-bit field m = 0x5555 changes to m' = 0x3285. Also, the one's complement sum of all other header octets is 0xCD7A.
Then the header checksum would be:
HC = ~(0xCD7A + 0x5555) = ~0x22D0 = 0xDD2F
The new checksum via recomputation is:
HC' = ~(0xCD7A + 0x3285) = ~0xFFFF = 0x0000
Using [Eqn. 2], as specified in RFC 1141, the new checksum is computed as:
HC' = HC + m + ~m' = 0xDD2F + 0x5555 + ~0x3285 = 0xFFFF
which does not match that computed from scratch, and moreover can never obtain for an IP header.
Rijsinghani [Page 3]
RFC 1624 Incremental Internet Checksum May 1994
Applying [Eqn. 3] to the example above, we get the correct result:
If an end system verifies the checksum by including the checksum field itself in the one's complement sum and then comparing the result against -0, as recommended by RFC 1071, it does not matter if an intermediate system generated a -0 instead of +0 due to the RFC 1141 property described here. In the example above:
However, implementations exist which verify the checksum by computing it and comparing against the header checksum field.
It is recommended that intermediate systems compute incremental checksum using the method described in this document, and end systems verify checksum as per the method described in RFC 1071.
The method in [Eqn. 3] is slightly more expensive than the one in RFC 1141. If this is a concern, the two additional instructions can be eliminated by subtracting complements with borrow [see Sec. 7]. This would result in the following equation:
A historical aside: the fact that standard one's complement arithmetic produces negative zero results is one of its main drawbacks; it makes for difficulty in interpretation. In the CDC 6000 series computers [4], this problem was avoided by using subtraction as the primitive in one's complement arithmetic (i.e., addition is subtraction of the complement).
The contribution of the following individuals to the work that led to this document is acknowledged:
Manu Kaycee - Ascom Timeplex, Incorporated Paul Koning - Digital Equipment Corporation Tracy Mallory - 3Com Corporation Krishna Narayanaswamy - Digital Equipment Corporation Atul Pandya - Digital Equipment Corporation
The failure condition was uncovered as a result of IP testing on a product which implemented the RFC 1141 algorithm. It was analyzed, and the updated algorithm devised. This algorithm was also verified using simulation. It was also shown that the failure condition disappears if the checksum verification is done as per RFC 1071.