home *** CD-ROM | disk | FTP | other *** search
/ Handbook of Infosec Terms 2.0 / Handbook_of_Infosec_Terms_Version_2.0_ISSO.iso / text / rfcs / rfc1624.txt < prev    next >
Text File  |  1996-05-07  |  10KB  |  220 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                             A. Rijsinghani, Editor Request for Comments: 1624                 Digital Equipment Corporation Updates: 1141                                                   May 1994 Category: Informational 
  8.  
  9.                    Computation of the Internet Checksum                          via Incremental Update 
  10.  
  11. Status of this Memo 
  12.  
  13.    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. 
  14.  
  15. Abstract 
  16.  
  17.    This memo describes an updated technique for incremental computation    of the standard Internet checksum.  It updates the method described    in RFC 1141. 
  18.  
  19. Table of Contents 
  20.  
  21.    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 
  22.  
  23. 1.  Introduction 
  24.  
  25.    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. 
  26.  
  27.    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 
  28.  
  29.  
  30.  
  31. Rijsinghani                                                     [Page 1] 
  32.  RFC 1624             Incremental Internet Checksum              May 1994 
  33.  
  34.     from the one obtained from scratch (one's complement of one's    complement sum of the original fields). 
  35.  
  36.    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. 
  37.  
  38. 2.  Notation and Equations 
  39.  
  40.    Given the following notation: 
  41.  
  42.           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 
  43.  
  44.           RFC 1071 states that C' is: 
  45.  
  46.           C' = C + (-m) + m'    --    [Eqn. 1]              = C + (m' - m) 
  47.  
  48.    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. 
  49.  
  50.    Finally, complementing the above equation to get the actual checksum,    RFC 1141 presents the following: 
  51.  
  52.           HC' = ~(C + (-m) + m')               = HC + (m - m')               = HC + m + ~m'    --    [Eqn. 2] 
  53.  
  54. 3.  Discussion 
  55.  
  56.    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. 
  57.  
  58.    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 
  59.  
  60.  
  61.  
  62. Rijsinghani                                                     [Page 2] 
  63.  RFC 1624             Incremental Internet Checksum              May 1994 
  64.  
  65.     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). 
  66.  
  67.    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]). 
  68.  
  69.    The problem is avoided by not assuming this property.  The correct    equation is given below: 
  70.  
  71.           HC' = ~(C + (-m) + m')    --    [Eqn. 3]               = ~(~HC + ~m + m') 
  72.  
  73. 4.  Examples 
  74.  
  75.    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. 
  76.  
  77.    Then the header checksum would be: 
  78.  
  79.           HC = ~(0xCD7A + 0x5555)              = ~0x22D0              =  0xDD2F 
  80.  
  81.    The new checksum via recomputation is: 
  82.  
  83.           HC' = ~(0xCD7A + 0x3285)               = ~0xFFFF               =  0x0000 
  84.  
  85.    Using [Eqn. 2], as specified in RFC 1141, the new checksum is    computed as: 
  86.  
  87.           HC' = HC + m + ~m'               =  0xDD2F + 0x5555 + ~0x3285               =  0xFFFF 
  88.  
  89.    which does not match that computed from scratch, and moreover can    never obtain for an IP header. 
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  Rijsinghani                                                     [Page 3] 
  98.  RFC 1624             Incremental Internet Checksum              May 1994 
  99.  
  100.     Applying [Eqn. 3] to the example above, we get the correct result: 
  101.  
  102.           HC' = ~(C + (-m) + m')               = ~(0x22D0 + ~0x5555 + 0x3285)               = ~0xFFFF               =  0x0000 
  103.  
  104. 5.  Checksum verification by end systems 
  105.  
  106.    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: 
  107.  
  108.           0xCD7A + 0x3285 + 0xFFFF = 0xFFFF           0xCD7A + 0x3285 + 0x0000 = 0xFFFF 
  109.  
  110.    However, implementations exist which verify the checksum by computing    it and comparing against the header checksum field. 
  111.  
  112.    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. 
  113.  
  114.    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: 
  115.  
  116.           HC' = HC - ~m - m'    --    [Eqn. 4] 
  117.  
  118.           In the example shown above, 
  119.  
  120.           HC' = HC - ~m - m'               =  0xDD2F - ~0x5555 - 0x3285               =  0x0000 
  121.  
  122. 6.  Historical Note 
  123.  
  124.    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). 
  125.  
  126.  
  127.  
  128.  
  129.  
  130. Rijsinghani                                                     [Page 4] 
  131.  RFC 1624             Incremental Internet Checksum              May 1994 
  132.  
  133.  7.  Acknowledgments 
  134.  
  135.    The contribution of the following individuals to the work that led to    this document is acknowledged: 
  136.  
  137.           Manu Kaycee - Ascom Timeplex, Incorporated           Paul Koning - Digital Equipment Corporation           Tracy Mallory - 3Com Corporation           Krishna Narayanaswamy - Digital Equipment Corporation           Atul Pandya - Digital Equipment Corporation 
  138.  
  139.    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. 
  140.  
  141. 8.  Security Considerations 
  142.  
  143.    Security issues are not discussed in this memo. 
  144.  
  145. 9.  Conclusions 
  146.  
  147.    It is recommended that either [Eqn. 3] or [Eqn. 4] be the    implementation technique used for incremental update of the standard    Internet checksum. 
  148.  
  149. 10.  Author's Address 
  150.  
  151.    Anil Rijsinghani    Digital Equipment Corporation    550 King St    Littleton, MA 01460 
  152.  
  153.    Phone: (508) 486-6786    EMail: anil@levers.enet.dec.com 
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169. Rijsinghani                                                     [Page 5] 
  170.  RFC 1624             Incremental Internet Checksum              May 1994 
  171.  
  172.  11.  References 
  173.  
  174.    [1] Postel, J., "Internet Protocol - DARPA Internet Program Protocol        Specification", STD 5, RFC 791, DARPA, September 1981. 
  175.  
  176.    [2] Braden, R., Borman, D., and C. Partridge, "Computing the Internet        Checksum", RFC 1071, ISI, Cray Research, BBN Laboratories,        September 1988. 
  177.  
  178.    [3] Mallory, T., and A. Kullberg, "Incremental Updating of the        Internet Checksum", RFC 1141, BBN Communications, January 1990. 
  179.  
  180.    [4] Thornton, J., "Design of a Computer -- the Control        Data 6600", Scott, Foresman and Company, 1970. 
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218. Rijsinghani                                                     [Page 6] 
  219.  
  220.