Computation of the Internet Checksum via Incremental Update
RFC 1624

Document Type RFC - Informational (May 1994; Errata)
Updates RFC 1141
Last updated 2016-08-20
Stream Legacy
Formats plain text pdf html bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 1624 (Informational)
Telechat date
Responsible AD (None)
Send notices to (None)
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.

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

   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.

2.  Notation and Equations

   Given the following notation:

          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, 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]

3.  Discussion

   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:

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

4.  Examples

   Consider an IP packet header in which a 16-bit field m = 0x5555
Show full document text