RFC 1624

RFC 1624: Computation of the Internet Checksum via Incremental Update 🎀

okay bestie, let's get into RFC 1624 💅 It's titled Computation of the Internet Checksum via Incremental Update, edited by A. Rijsinghani from Digital Equipment Corporation, dated May 1994. It's Informational, so it's sharing info with the internet community and not setting a standard 📚. It updates RFC 1141, and the title block doesn't list any Obsoletes entry 🌸.

Status of this Memo ✨

This memo gives info to the Internet community. It does not specify an Internet standard of any kind. Distribution is unlimited 🦋.

Abstract 🌸

This memo describes an updated way to incrementally compute the standard Internet checksum, and it updates the method from RFC 1141 🫶.

Table of Contents 📋

   1. Introduction ..........................................  1
   2. Notation and Equations ................................  2
   3. Discussion ............................................  2
   4. Examples ..............................................  3
   5. Checksum verification by end systems ..................  4
   6. Historical Note .......................................  4
   7. Acknowledgments .......................................  5
   8. Security Considerations ...............................  5
   9. Conclusions ...........................................  5
   10. Author's Address .....................................  5
   11. References ...........................................  6

1. Introduction 🍓

okay so incremental checksum updates are a big deal for speeding up stuff we do all the time to IP packets, like updating the TTL, IP fragmentation, and source route updates. It's giving efficiency ✨

RFC 1071, on pages 4 and 5, describes how to incrementally update the standard Internet checksum. Its discussion is thorough but not complete 🥺. So RFC 1141 came along to replace that description of Incremental Update. RFC 1141 goes into way more detail about the RFC 1071 procedure. The catch is that it computes a result for certain cases that is different from the one you get by computing from scratch (the one's complement of the one's complement sum of the original fields). Not me being like 😭

For completeness, this memo quickly covers the key points from RFCs 1071 and 1141. Based on those, it develops and presents an updated procedure for incrementally computing the standard Internet checksum 💖

2. Notation and Equations 🧚

Here's the notation we're working with:

          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

          RFC 1071 states that C' is:

          C' = C + (-m) + m'    --    [Eqn. 1]
             = C + (m' - m)

As RFC 1141 points out, that equation isn't directly useful for incremental updates, because C and C' don't refer to the actual checksum stored in the header 🙈. It's also pointed out that RFC 1071 didn't specify that all arithmetic has to be done using one's complement arithmetic.

Finally, to get the actual checksum by complementing the equation above, RFC 1141 gives us this:

          HC' = ~(C + (-m) + m')
              = HC + (m - m')
              = HC + m + ~m'    --    [Eqn. 2]

3. Discussion 💅

This equation looks like it works, but there are boundary conditions where it gives a different result from computing the checksum from scratch 😬. The reason is how zero gets handled in one's complement arithmetic.

In one's complement there are two representations of zero: the all zero bit value and the all one bit value, often called +0 and -0. One's complement addition of non-zero inputs can produce -0 as a result, but it never produces +0. Since there is guaranteed to be at least one 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 gives an updated header checksum of -0 when it should be +0 💀. This happens because it assumed one's complement has a distributive property, and that property doesn't hold when the result is 0 (see the derivation of [Eqn. 2]).

The fix is to not assume that property. The correct equation is below:

          HC' = ~(C + (-m) + m')    --    [Eqn. 3]
              = ~(~HC + ~m + m')

4. Examples 🎀

Let's say we have an IP packet header where a 16-bit field m = 0x5555 changes to m' = 0x3285. Also, the one's complement sum of all the other header octets is 0xCD7A.

Then the header checksum would be:

          HC = ~(0xCD7A + 0x5555)
             = ~0x22D0
             =  0xDD2F

The new checksum from 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

That doesn't match the one computed from scratch, and it can never be obtained for an IP header, so it's a whole mess 😭

Applying [Eqn. 3] to the example above gives us the correct result 🫶:

          HC' = ~(C + (-m) + m')
              = ~(0x22D0 + ~0x5555 + 0x3285)
              = ~0xFFFF
              =  0x0000

5. Checksum verification by end systems 🦋

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 RFC 1071 recommends, it doesn't matter if an intermediate system generated a -0 instead of +0 because of the RFC 1141 property described here. In the example above:

          0xCD7A + 0x3285 + 0xFFFF = 0xFFFF
          0xCD7A + 0x3285 + 0x0000 = 0xFFFF

However, there are implementations that verify the checksum by computing it and comparing against the header checksum field 🙈.

It is recommended that intermediate systems compute the incremental checksum using the method in this document, and that end systems verify the checksum using the method in RFC 1071 🌈.

The method in [Eqn. 3] is slightly more expensive than the one in RFC 1141. If that's a concern, the two extra instructions can be removed by subtracting complements with borrow [see Sec. 7]. That gives us this equation:

          HC' = HC - ~m - m'    --    [Eqn. 4]

In the example shown above:

          HC' = HC - ~m - m'
              =  0xDD2F - ~0x5555 - 0x3285
              =  0x0000

6. Historical Note 📜

Historical aside: the fact that standard one's complement arithmetic produces negative zero results is one of its main drawbacks, because it makes things harder to interpret 🤓. On the CDC 6000 series computers [4], this problem was avoided by using subtraction as the primitive in one's complement arithmetic (so addition is subtraction of the complement).

7. Acknowledgments 🫶

Here's the list of people whose contributions to the work behind this document are 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 found during IP testing on a product that implemented the RFC 1141 algorithm. It was analyzed, and the updated algorithm was devised. The algorithm was also verified using simulation. It was also shown that the failure condition goes away if checksum verification is done as per RFC 1071 ✨.

8. Security Considerations 🔒

Security issues are not discussed in this memo. The memo doesn't cover security at all, so keep that in mind when you use it 👀.

9. Conclusions 👑

It is recommended that either [Eqn. 3] or [Eqn. 4] be the implementation technique used for incremental update of the standard Internet checksum 💜.

10. Author's Address 💌

   Anil Rijsinghani
   Digital Equipment Corporation
   550 King St
   Littleton, MA 01460

   Phone: (508) 486-6786
   EMail: anil@levers.enet.dec.com

11. References 📚

[1] Postel, J., "Internet Protocol - DARPA Internet Program Protocol Specification", STD 5, RFC 791, DARPA, September 1981.

[2] Braden, R., Borman, D., and C. Partridge, "Computing the Internet Checksum", RFC 1071, ISI, Cray Research, BBN Laboratories, September 1988.

[3] Mallory, T., and A. Kullberg, "Incremental Updating of the Internet Checksum", RFC 1141, BBN Communications, January 1990.

[4] Thornton, J., "Design of a Computer -- the Control Data 6600", Scott, Foresman and Company, 1970.

---

That's the whole RFC! Checksums, zeros, and one's complement all explained 🌈💖