home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1624 < prev    next >
Text File  |  1994-05-22  |  10KB  |  340 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                             A. Rijsinghani, Editor
  8. Request for Comments: 1624                 Digital Equipment Corporation
  9. Updates: 1141                                                   May 1994
  10. Category: Informational
  11.  
  12.  
  13.                   Computation of the Internet Checksum
  14.                          via Incremental Update
  15.  
  16. Status of this Memo
  17.  
  18.    This memo provides information for the Internet community.  This memo
  19.    does not specify an Internet standard of any kind.  Distribution of
  20.    this memo is unlimited.
  21.  
  22. Abstract
  23.  
  24.    This memo describes an updated technique for incremental computation
  25.    of the standard Internet checksum.  It updates the method described
  26.    in RFC 1141.
  27.  
  28. Table of Contents
  29.  
  30.    1. Introduction ..........................................  1
  31.    2. Notation and Equations ................................  2
  32.    3. Discussion ............................................  2
  33.    4. Examples ..............................................  3
  34.    5. Checksum verification by end systems ..................  4
  35.    6. Historical Note .......................................  4
  36.    7. Acknowledgments .......................................  5
  37.    8. Security Considerations ...............................  5
  38.    9. Conclusions ...........................................  5
  39.    10. Author's Address .....................................  5
  40.    11. References ...........................................  6
  41.  
  42. 1.  Introduction
  43.  
  44.    Incremental checksum update is useful in speeding up several
  45.    types of operations routinely performed on IP packets, such as
  46.    TTL update, IP fragmentation, and source route update.
  47.  
  48.    RFC 1071, on pages 4 and 5, describes a procedure to
  49.    incrementally update the standard Internet checksum.  The
  50.    relevant discussion, though comprehensive, was not complete.
  51.    Therefore, RFC 1141 was published to replace this description
  52.    on Incremental Update.  In particular, RFC 1141 provides a
  53.    more detailed exposure to the procedure described in RFC 1071.
  54.    However, it computes a result for certain cases that differs
  55.  
  56.  
  57.  
  58. Rijsinghani                                                     [Page 1]
  59.  
  60. RFC 1624             Incremental Internet Checksum              May 1994
  61.  
  62.  
  63.    from the one obtained from scratch (one's complement of one's
  64.    complement sum of the original fields).
  65.  
  66.    For the sake of completeness, this memo briefly highlights key
  67.    points from RFCs 1071 and 1141.  Based on these discussions,
  68.    an updated procedure to incrementally compute the standard
  69.    Internet checksum is developed and presented.
  70.  
  71. 2.  Notation and Equations
  72.  
  73.    Given the following notation:
  74.  
  75.           HC  - old checksum in header
  76.           C   - one's complement sum of old header
  77.           HC' - new checksum in header
  78.           C'  - one's complement sum of new header
  79.           m   - old value of a 16-bit field
  80.           m'  - new value of a 16-bit field
  81.  
  82.           RFC 1071 states that C' is:
  83.  
  84.           C' = C + (-m) + m'    --    [Eqn. 1]
  85.              = C + (m' - m)
  86.  
  87.    As RFC 1141 points out, the equation above is not useful for direct
  88.    use in incremental updates since C and C' do not refer to the actual
  89.    checksum stored in the header.  In addition, it is pointed out that
  90.    RFC 1071 did not specify that all arithmetic must be performed using
  91.    one's complement arithmetic.
  92.  
  93.    Finally, complementing the above equation to get the actual checksum,
  94.    RFC 1141 presents the following:
  95.  
  96.           HC' = ~(C + (-m) + m')
  97.               = HC + (m - m')
  98.               = HC + m + ~m'    --    [Eqn. 2]
  99.  
  100. 3.  Discussion
  101.  
  102.    Although this equation appears to work, there are boundary conditions
  103.    under which it produces a result which differs from the one obtained
  104.    by checksum computation from scratch.  This is due to the way zero is
  105.    handled in one's complement arithmetic.
  106.  
  107.    In one's complement, there are two representations of zero: the all
  108.    zero and the all one bit values, often referred to as +0 and -0.
  109.    One's complement addition of non-zero inputs can produce -0 as a
  110.    result, but never +0.  Since there is guaranteed to be at least one
  111.  
  112.  
  113.  
  114. Rijsinghani                                                     [Page 2]
  115.  
  116. RFC 1624             Incremental Internet Checksum              May 1994
  117.  
  118.  
  119.    non-zero field in the IP header, and the checksum field in the
  120.    protocol header is the complement of the sum, the checksum field can
  121.    never contain ~(+0), which is -0 (0xFFFF).  It can, however, contain
  122.    ~(-0), which is +0 (0x0000).
  123.  
  124.    RFC 1141 yields an updated header checksum of -0 when it should be
  125.    +0.  This is because it assumed that one's complement has a
  126.    distributive property, which does not hold when the result is 0 (see
  127.    derivation of [Eqn. 2]).
  128.  
  129.    The problem is avoided by not assuming this property.  The correct
  130.    equation is given below:
  131.  
  132.           HC' = ~(C + (-m) + m')    --    [Eqn. 3]
  133.               = ~(~HC + ~m + m')
  134.  
  135. 4.  Examples
  136.  
  137.    Consider an IP packet header in which a 16-bit field m = 0x5555
  138.    changes to m' = 0x3285.  Also, the one's complement sum of all other
  139.    header octets is 0xCD7A.
  140.  
  141.    Then the header checksum would be:
  142.  
  143.           HC = ~(0xCD7A + 0x5555)
  144.              = ~0x22D0
  145.              =  0xDD2F
  146.  
  147.    The new checksum via recomputation is:
  148.  
  149.           HC' = ~(0xCD7A + 0x3285)
  150.               = ~0xFFFF
  151.               =  0x0000
  152.  
  153.    Using [Eqn. 2], as specified in RFC 1141, the new checksum is
  154.    computed as:
  155.  
  156.           HC' = HC + m + ~m'
  157.               =  0xDD2F + 0x5555 + ~0x3285
  158.               =  0xFFFF
  159.  
  160.    which does not match that computed from scratch, and moreover can
  161.    never obtain for an IP header.
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Rijsinghani                                                     [Page 3]
  171.  
  172. RFC 1624             Incremental Internet Checksum              May 1994
  173.  
  174.  
  175.    Applying [Eqn. 3] to the example above, we get the correct result:
  176.  
  177.           HC' = ~(C + (-m) + m')
  178.               = ~(0x22D0 + ~0x5555 + 0x3285)
  179.               = ~0xFFFF
  180.               =  0x0000
  181.  
  182. 5.  Checksum verification by end systems
  183.  
  184.    If an end system verifies the checksum by including the checksum
  185.    field itself in the one's complement sum and then comparing the
  186.    result against -0, as recommended by RFC 1071, it does not matter if
  187.    an intermediate system generated a -0 instead of +0 due to the RFC
  188.    1141 property described here.  In the example above:
  189.  
  190.           0xCD7A + 0x3285 + 0xFFFF = 0xFFFF
  191.           0xCD7A + 0x3285 + 0x0000 = 0xFFFF
  192.  
  193.    However, implementations exist which verify the checksum by computing
  194.    it and comparing against the header checksum field.
  195.  
  196.    It is recommended that intermediate systems compute incremental
  197.    checksum using the method described in this document, and end systems
  198.    verify checksum as per the method described in RFC 1071.
  199.  
  200.    The method in [Eqn. 3] is slightly more expensive than the one in RFC
  201.    1141.  If this is a concern, the two additional instructions can be
  202.    eliminated by subtracting complements with borrow [see Sec. 7].  This
  203.    would result in the following equation:
  204.  
  205.           HC' = HC - ~m - m'    --    [Eqn. 4]
  206.  
  207.           In the example shown above,
  208.  
  209.           HC' = HC - ~m - m'
  210.               =  0xDD2F - ~0x5555 - 0x3285
  211.               =  0x0000
  212.  
  213. 6.  Historical Note
  214.  
  215.    A historical aside: the fact that standard one's complement
  216.    arithmetic produces negative zero results is one of its main
  217.    drawbacks; it makes for difficulty in interpretation.  In the CDC
  218.    6000 series computers [4], this problem was avoided by using
  219.    subtraction as the primitive in one's complement arithmetic (i.e.,
  220.    addition is subtraction of the complement).
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Rijsinghani                                                     [Page 4]
  227.  
  228. RFC 1624             Incremental Internet Checksum              May 1994
  229.  
  230.  
  231. 7.  Acknowledgments
  232.  
  233.    The contribution of the following individuals to the work that led to
  234.    this document is acknowledged:
  235.  
  236.           Manu Kaycee - Ascom Timeplex, Incorporated
  237.           Paul Koning - Digital Equipment Corporation
  238.           Tracy Mallory - 3Com Corporation
  239.           Krishna Narayanaswamy - Digital Equipment Corporation
  240.           Atul Pandya - Digital Equipment Corporation
  241.  
  242.    The failure condition was uncovered as a result of IP testing on a
  243.    product which implemented the RFC 1141 algorithm.  It was analyzed,
  244.    and the updated algorithm devised.  This algorithm was also verified
  245.    using simulation.  It was also shown that the failure condition
  246.    disappears if the checksum verification is done as per RFC 1071.
  247.  
  248. 8.  Security Considerations
  249.  
  250.    Security issues are not discussed in this memo.
  251.  
  252. 9.  Conclusions
  253.  
  254.    It is recommended that either [Eqn. 3] or [Eqn. 4] be the
  255.    implementation technique used for incremental update of the standard
  256.    Internet checksum.
  257.  
  258. 10.  Author's Address
  259.  
  260.    Anil Rijsinghani
  261.    Digital Equipment Corporation
  262.    550 King St
  263.    Littleton, MA 01460
  264.  
  265.    Phone: (508) 486-6786
  266.    EMail: anil@levers.enet.dec.com
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282. Rijsinghani                                                     [Page 5]
  283.  
  284. RFC 1624             Incremental Internet Checksum              May 1994
  285.  
  286.  
  287. 11.  References
  288.  
  289.    [1] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
  290.        Specification", STD 5, RFC 791, DARPA, September 1981.
  291.  
  292.    [2] Braden, R., Borman, D., and C. Partridge, "Computing the Internet
  293.        Checksum", RFC 1071, ISI, Cray Research, BBN Laboratories,
  294.        September 1988.
  295.  
  296.    [3] Mallory, T., and A. Kullberg, "Incremental Updating of the
  297.        Internet Checksum", RFC 1141, BBN Communications, January 1990.
  298.  
  299.    [4] Thornton, J., "Design of a Computer -- the Control
  300.        Data 6600", Scott, Foresman and Company, 1970.
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Rijsinghani                                                     [Page 6]
  339.  
  340.