米葫芦网

RFC1624 - Computation of the Internet Checksum via Incremental Update

热度:3℃ 发布时间:2023-11-16 19:43:46
Network Working Group A. Rijsinghani, EditorRequest for Comments: 1624 Digital Equipment CorporationUpdates: 1141 May 1994Category: InformationalComputation of the Internet Checksum via Incremental UpdateStatus 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 RFC1141.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 ........................................... 61. 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. RFC1071, on pages 4 and 5, describes a procedure to incrementally update the standard Internet checksum. The relevant discussion, though comprehensive, was not complete. Therefore, RFC1141 was published to replace this description on Incremental Update. In particular, RFC1141 provides a more detailed eXPosure to the procedure described in RFC1071. However, it computes a result for certain cases that differs 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 headerC - one"s complement sum of old headerHC" - new checksum in header
C" - one"s complement sum of new headerm - old value of a 16-bit fieldm" - new value of a 16-bit fieldRFC1071 states that C" is:C" = C + (-m) + m" -- [Eqn. 1] = C + (m" - m) As RFC1141 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 RFC1071 did not specify that all arithmetic must be performed using one"s complement arithmetic. Finally, complementing the above equation to get the actual checksum, RFC1141 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 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). RFC1141 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 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 RFC1141, 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. Applying [Eqn. 3] to the example above, we get the correct result:HC" = ~(C + (-m) + m") = ~(0x22D0 + ~0x5555 + 0x3285) = ~0xFFFF
= 0x00005. 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 recommended by RFC1071, 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:0xCD7A + 0x3285 + 0xFFFF = 0xFFFF0xCD7A + 0x3285 + 0x0000 = 0xFFFF 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 RFC1071. 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:HC" = HC - ~m - m" -- [Eqn. 4]In the example shown above,HC" = HC - ~m - m" = 0xDD2F - ~0x5555 - 0x3285 = 0x00006. Historical Note 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).7. Acknowledgments The contribution of the following individuals to the work that led to this document is acknowledged:Manu Kaycee - Ascom Timeplex, IncorporatedPaul Koning - Digital Equipment CorporationTracy Mallory - 3Com CorporationKrishna Narayanaswamy - Digital Equipment CorporationAtul Pandya - Digital Equipment Corporation The failure condition was uncovered as a result of IP testing on a product which implemented the RFC1141 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 RFC1071.8. Security Considerations Security issues are not discussed in this memo.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.com11. References [1] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
Specification", STD 5, RFC791, DARPA, September 1981. [2] Braden, R., Borman, D., and C. Partridge, "Computing the Internet Checksum", RFC1071, ISI, Cray Research, BBN Laboratories, September 1988. [3] Mallory, T., and A. Kullberg, "Incremental Updating of the Internet Checksum", RFC1141, BBN Communications, January 1990. [4] Thornton, J., "Design of a Computer -- the Control Data 6600", Scott, Foresman and Company, 1970.
网友评论
评论
发 布

更多软件教程
  • 软件教程推荐
更多+
Greenfoot设置中文的方法

Greenfoot设置中文的方法

Greenfoot是一款简单易用的Java开发环境,该软件界面清爽简约,既可以作为一个开发框使用,也能够作为集成开发环境使用,操作起来十分简单。这款软件支持多种语言,但是默认的语言是英文,因此将该软件下载到电脑上的时候,会发现软件的界面语言是英文版本的,这对于英语基础较差的朋友来说,使用这款软件就会...

07-05

Egret UI Editor修改快捷键的方法

Egret UI Editor修改快捷键的方法

Egret UI Editor是一款开源的2D游戏开发代码编辑软件,其主要功能是针对Egret项目中的Exml皮肤文件进行可视化编辑,功能十分强大。我们在使用这款软件的过程中,可以将一些常用操作设置快捷键,这样就可以简化编程,从而提高代码编辑的工作效率。但是这款软件在日常生活中使用得不多,并且专业性...

07-05

KittenCode新建项目的方法

KittenCode新建项目的方法

KittenCode是一款十分专业的编程软件,该软件给用户提供了可视化的操作界面,支持Python语言的编程开发以及第三方库管理,并且提供了很多实用的工具,功能十分强大。我们在使用这款软件进行编程开发的过程中,最基本、最常做的操作就是新建项目,因此我们很有必要掌握新建项目的方法。但是这款软件的专业性...

07-05

Thonny设置中文的方法

Thonny设置中文的方法

Thonny是一款十分专业的Python编辑软件,该软件界面清爽简单,给用户提供了丰富的编程工具,具备代码补全、语法错误显示等功能,非常的适合新手使用。该软件还支持多种语言,所以在下载这款软件的时候,有时候下载到电脑中的软件是英文版本的,这对于英语基础较差的小伙伴来说,使用这款软件就会变得十分困难,...

07-05

最新软件下载