Internet Draft H. Heikkila Intended Status: Informational Updates: 1071, 1141, 1624 (once approved) Expires: May 9, 2013 November 5, 2012 Practical Math and Algorithms for TCP/IP checksum Abstract This document reformulates the definition of TCP/IP checksum. The new formulation is equivalent to the traditional one, but it uses much simpler mathematics, avoiding concepts like "one's complement sum". This document attempts to be helpful for both newbies and seasoned engineers when considering checksum problems. Practical calculation and software examples are included. Status of this Memo Distribution of this memo is unlimited. This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright and License Notice Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents Heikkila Expires: May 2013 [Page 1] Internet Draft IP checksum November 5, 2012 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction 2. Old Definition of Checksum 3. Mathematical Observations 3.1. Basics 3.2. The Shift Property 3.3. Negation and Subtraction 3.4. Byte Order Independence 4. New Definition of Checksum 5. Examples of Algorithms 5.1. Basic Calculations 5.2. Integer Division versus Folding 5.3. Choice of Data Types 5.4. Efficient Calculation of Sum 5.5. Byte Order Issues 5.6. Incremental Update of Checksum 5.7. The Last Octet 6. Security Considerations 7. IANA Considerations 8. References 8.1. Normative References 8.2. Informative References Heikkila Expires: May 2013 [Page 2] Internet Draft IP checksum November 5, 2012 1. Introduction RFC 793 defines the TCP checksum briefly as "the 16 bit one's complement of the one's complement sum of all 16 bit words in the header and text" [RFC0793]. RFC 1071 contains helpful details and examples that make the checksum understandable, and mentions the useful method of "end around carry". However, it can be argued that the presentation of RFC 1071 is still more complicated than necessary [RFC1071]. This document argues that the checksum is best described in terms of more elementary mathematics, namely remainders modulo 65,535. It may be easier to avoid the concept of one's complement sum, which is nowadays not widely used for computer arithmetic. This document also attempts to show that the proposed new description is, in general, sufficient for practical purposes. In what follows, the equivalence of the old and new definition is proved, example calculations are included to show how the known mathematical properties of the checksum can be derived from the new definition, and software code examples are included. 2. Old Definition of Checksum RFC 1071 uses the notation +' for one's complement sum. Here is a definition of it: (Definition of binary operation +') For any two integers a and b such that 0 <= a,b <= 65,535, a +' b = a+b, if a+b <= 65,535; [Eq. 1] = a+b-65,535, otherwise. Textually, this definition appears to differ from that in RFC 1071; but if the reader understands the +' operation in RFC 1071, he or she can easily verify that the two formulations of +' are equivalent. RFC 1071 calls this operation "1's complement addition". But in the definition of this document, the operands a,b and the result are definitely non-negative integers (actual 1's complement calculations are not involved). Note that this definition uses elementary school mathematics: the right-hand side of the definition uses just the well-known addition and subtraction operators. Overflow or wraparound properties are not used as such and wraparound of +' is defined explicitly. Also, the decimal constant 65,535 is chosen (instead of the hexadecimal constant ffff) to emphasize the elementary character of the proposed mathematical operations. Heikkila Expires: May 2013 [Page 3] Internet Draft IP checksum November 5, 2012 Operation +' wraps around to prevent results larger than 65,535, but the wraparound is slightly different from ordinary addition modulo 65,535. The following figure illustrates the wraparound properties of operator +' and compares it to the normal wraparound modulo 65,535 (wrap-to-one versus wrap-to-zero). Of course, both wrap methods differ from the familiar 16-bit register addition modulo 2^16, since 65,535 = 2^16-1. +---------- wraparound of +' ----------+ | | v | -> 0 -> 1 -> 2 -> . . . -> 65,534 -> 65,535 ->+ [Fig. 2] ^ | | | +--- wraparound modulo 65,535 ---+ Following RFC 1071 very closely, we define IP checksum as follows: (1) Data consists of octets, which are paired to form 16-bit unsigned integers, with most significant octet first (network byte order). Within the data, there is a field for 16-bit checksum, in an even offset location. If the total number of octets is odd, an additional zeroed octet is added to the end of the octet string for checksum calculation and removed after the calculation. (2) To generate a checksum, the checksum field itself is cleared, the sum B is computed over the octets concerned using operation +', and the value (65,535-B) is placed in the checksum field. (Note that 65,535-B means just the elementary subtraction.) (3) To check a checksum, the sum B is computed over the octets concerned using operation +'. If the result is 65,535, the check succeeds. Note some differences to RFC 1071: We have 16-bit *unsigned* integers, while RFC 1071 has just "integers" (probably to make it possible to interpret these 16 bits as a signed integer with one's complement representation). Instead of (65,535-B), RFC 1071 uses bit complementation, but the reader can easily see that the results are the same. Thus, the definition presented above is equivalent to that in RFC 1071. For completeness, we add a fourth rule, mandated by [RFC0768] and [RFC2460]: Heikkila Expires: May 2013 [Page 4] Internet Draft IP checksum November 5, 2012 (4) To generate a checksum for UDP header, calculate as above, but if the resulting checksum is 0, place 65,535 instead in the checksum field. One observation is still in order. If some data consists of nothing but octets where all bits are cleared, we call the data "zeroed". Real protocols never send such data; for example, IPv4 header starts with version number 4 and so IPv4 header checksum is never calculated over zeroed data [RFC0791]. However, the algorithm may still face zeroed data, as errors are possible. The following facts are notable. o If checksum is generated over zeroed data, the checksum will be 65,535. After that checksum has been placed to the checksum field, the resulting data will be acceptable to the checking algorithm. o If checksum checking is done over zeroed data (meaning that even the checksum is zeroed), the checking will reject the data. (This is appropriate, because no reasonable protocol would send such data anyway.) In what follows, we occasionally need to consider three special cases for checksum calculation: UDP data, zeroed data with valid checksum 65,535, and zeroed data with invalid checksum 0. (This is slightly annoying, because without these cases the checksum analysis would be easier.) 3. Mathematical Observations This section contains basic mathematical analysis of the checksum algorithm. While this section is not really difficult, the reader may anyway choose to skip it. The later part of this document uses only simple and well-known concepts like division with remainder and bit shift. 3.1. Basics We use the symbol % for remainder division, in accordance with the C programming language. While our divisors are positive, we allow the dividends to be negative. The remainder is always positive; for example, (-2) % 65,535 = 65,533. Computers are known to be unpredictable with division of negative integers; so we avoid such divisions in algorithms. As expected, we need the concept of "congruence modulo M"; we use symbol =' for the congruence relation. Thus Heikkila Expires: May 2013 [Page 5] Internet Draft IP checksum November 5, 2012 a =' b (mod M) means simply that a and b have the same remainder when divided by M. Equivalently, this means that the difference a-b is an integral multiple of M. For checksum, the modulus M is always 65,535, and we omit the (mod M) from the notation, from now on. One well-known property of congruence is this. If a =' b and c =' d then a+c =' b+d and a-c =' b-d and ac =' bd. [Eq. 3] This fact makes it possible to calculate with congruences almost as easily as with equalities. Obviously a+b =' a+b-65,535, so that definition [Eq. 1] yields this: Fact. a+'b =' a+b. Corollary. If B is the sum calculated with +' over some 16-bit unsigned integers and S is the sum calculated with ordinary addition over the same data, then B =' S. According to definition item (3), the sum with +' yields 65,535 when calculated over correctly checksummed data; since 65,535 =' 0, we see: Corollary. If S is the sum calculated with ordinary addition over some data that has correct checksum, S =' 0; equivalently, S is divisible by 65,535. [Eq. 4] Now we see that [Eq. 4] is an almost complete definition of the checksum, without referring to one's complement sum. From it, we can derive both generation and checking algorithms for checksum, with the following open issues: for generating a checksum, [Eq. 4] does not tell whether 0 or 65,535 should be chosen if both are possible; for checking a checksum, [Eq. 4] considers both 0 and 65,535 equal as checksums, while sometimes they are not. 3.2. The Shift Property Obviously, 65,536 =' 1 and 65,536 = 2^16. From this we see that for any integer a, we have a*2^16 =' a. But for non-negative integers, multiplication by 2^16 means bit shifting to the left by 16 bits. Heikkila Expires: May 2013 [Page 6] Internet Draft IP checksum November 5, 2012 Using the C notation for bit shift (left shift is <<, right shift is >>), we have the following basic property for any non-negative integer a: a << 16 =' a. [Eq. 5] As a first application of this property, consider four-octet integers, using the notation of RFC 1071, sec. 2(C). [A,B,C,D] + [E,F,G,H] = [A,B,0,0] + [C,D] + [E,F,0,0] + [G,H] = ([A,B]<<16) + [C,D] + ([E,F]<<16) + [G,H] =' [A,B] + [C,D] + [E,F] + [G,H] This is what RFC 1071 calls "parallel summation": we can accumulate the sum in 32-bit pieces. The resulting block sum is not the same as the real block sum, but still congruent to it. It is fairly easy to see that we can do parallel summation even for eight bytes, if we have 64-bit arithmetic support in hardware. The next trick is what RFC1071 calls "folding"; long integers can be shortened with bit shifting. [A,B,C,D] = [A,B,0,0] + [C,D] = ([A,B]<<16) + [C,D] =' [A,B] + [C,D] 3.3. Negation and Subtraction Negation and subtraction are easy to do with unsigned (non-negative) numbers if the modulus 65,535 is first added to the operands sufficiently many times. To manipulate the negative of A, first find some N such that N*65,535 >= A; then (-A) =' N*65,535-A, and the latter value is non-negative but still congruent to the mathematically correct value. Similarly, to do subtraction A-B, substitute (N*65,535+A-B), where N is chosen so that the result is positive and calculations do not overflow. 3.4. Byte Order Independence We use the notation [a,b] = a*256+b for a 16-bit integer that consists of two octets a and b, as RFC 1071. If we multiply [a,b] by 256, we can calculate: 256*[a,b] = 256*(a*256+b) = a*256*256 + b*256 = a*2^16 + b*256 = b*256 + (a << 16) =' b*256 + a. Heikkila Expires: May 2013 [Page 7] Internet Draft IP checksum November 5, 2012 From this we see: 256*[a,b] =' [b,a] and 256*[b,a] =' [a,b]. Byte swapping is thus equivalent to multiplying by 256, modulo M. But multiplication is distributive over addition, so that 256*([a,b]+[c,d]+ ... + [y,z]) = 256*[a,b]+256*[c,d]+ ... +256*[y,z] =' [b,a] + [d,c] + ... + [z,y] From this we see that if we deliberately swap the bytes of terms of a sum, calculate the sum, and then swap the bytes back, we get a result that is (of course) in general not identical to the correct sum but at least congruent to it modulo 65,535. And in checksum calculation the critical results 0 = [0,0] and 65,535 = [255,255] are immune to swapping. So the congruence method yields rather elegantly the well known property of IP checksum: it can be calculated with inverted byte order. 4. New Definition of Checksum Here is a modified checksum definition. The mathematical considerations above show that it is equivalent to the traditional one. We define the *blocksum* over a set of 16-bit unsigned integers to be the arithmetic sum of these integers. (1) Data consists of octets, which are paired to form 16-bit unsigned integers, with most significant octet first (network byte order). Within the data, there is a field for 16-bit checksum, in an even offset location. If the total number of octets is odd, an additional zeroed octet is added to the end of the octet string for checksum calculation and removed after the calculation. (2) To generate a checksum, the checksum field itself is cleared, the blocksum B is computed over the octets concerned, then B is divided by 65,535, yielding remainder R. The value C is placed in the checksum field, computed as follows. (2a) If the blocksum B is zero, let C = 65,535. (This is the theoretical case of zeroed data.) (2b) Otherwise, if R = 0 and the checksum is for UDP header, let C = 65,535 [RFC0768] [RFC2460]. (2c) Otherwise, if R = 0, let C = 0. (2d) Otherwise, let C = 65,535 - R. Heikkila Expires: May 2013 [Page 8] Internet Draft IP checksum November 5, 2012 (3) To check a checksum, the blocksum B is computed over the octets concerned. If the result B is non-zero and divisible by 65,535, the check succeeds. Note for the UDP case: UDP protocol examines the checksum field before applying algorithm (3); if the checksum is zero, (3) is not applied at all, as there is no checksum. (Instead, the zero-checksum data is either accepted as in [RFC0768] or rejected as in [RFC2460].) Note also that the definition above is formulated to be exactly identical to that in RFC 1071. For example, if IPv4 header contains checksum 65,535 (hex-ffff), algorithm (3) accepts it (as RFC 1071 would do) although algorithm (2) would not produce such a checksum except in case (2b). Also, in algorithm (3) the condition "B is non- zero" is usually unnecessary, because B=0 implies that all data is zeroed, and reasonable protocols reject such data on other grounds (for example, IPv4 header is rejected if its protocol version is not 4). 5. Examples of Algorithms All examples use the C programming language. Naturally, identical algorithms can be implemented in other software languages and even in hardware. 5.1. Basic Calculations When calculating checksum, the basic method is just to add together the 16-bit unsigned integers over the data, accumulating the sum in a 32-bit variable. The following example is taken from RFC 1071 (where it appears in a slightly more complicated form): register unsigned long sum = 0; unsigned short *addr = . .; int count = . . /* octet count */ while (count > 1) { sum += *addr++; count -= 2; } If checksum is to be generated, the blocksum is calculated as above, after ensuring that the checksum field is cleared. The basic method to calculate checksum is then: checksum = ((N*65535) - sum) % 65535; (This calculates the remainder of the negative of sum, but the Heikkila Expires: May 2013 [Page 9] Internet Draft IP checksum November 5, 2012 addition of N*65535 with suitably large N guarantees that dividend is positive without changing the result. For example, N can be 65537.) But if the checksum is calculated for UDP header, the algorithm is this: udp_checksum = 65535 - (sum % 65535); To check the checksum of some received data, blocksum is calculated as above, and verification can be done like this: if (sum % 65535 != 0) goto checksum_error; (Pedantically, the check should be "if (sum == 0 || sum % 65535 != 0)", but usually the sum is not zero, and if it is, other parts of the software reject the packet anyway.) In practice, many alterations of the algorithm are possible and often necessary, as follows. o If hardware support for efficient remainder division is not available, some alternative algorithm is needed. o The summing algorithm usually needs optimizations (as emphasized already in RFC 1071). o The summing can be done in pieces (usually pieces of even offset and, except for the last piece, even size), and pieces can be summed in any order. o Computer byte order needs to be taken into account (little- endian machines tend to reverse the byte order when doing arithmetic operations). o The last odd octet, if any, needs special attention. o We need algorithms for incremental update of checksum. The following sections consider these points. We start with some preliminary remarks. The checksum algorithm is such that usually only the remainder of the sum is significant (when divided by 65,535). There are several operations that change the mathematical value but preserve the remainder. Such operations can be used during the course of calculation. (The mathematical section above proves the validity of these operations.) o Any multiple of 65,535 can be added or subtracted, as long as Heikkila Expires: May 2013 [Page 10] Internet Draft IP checksum November 5, 2012 there is no overflow or underflow. In particular, 0xffffffff (the largest unsigned 32-bit integer) is a multiple of 65,535. o Remainder division can be done: sum = sum % 65535. o A non-negative value can be bit-shifted left by 16 bits: sum = sum << 16. o A non-negative value can be folded by shifting the most- significant bits right by 16 and adding to the rest of the number, for example: 0x123456789ab = 0x12345670000 + 0x89ab = (0x1234567<<16) + 0x89ab -> change to 0x1234567 + 0x89ab In C language, we can define folding essentially as in RFC 1071: #define FOLD(sum) (((sum) & 0xffff) + ((sum) >> 16)) o In assembly programming, the carry bit that overflows after unsigned 16-, 32-, or 64-bit addition can be shifted to the right and added back to the sum ("end around carry" [RFC1071]). 5.2. Integer Division versus Folding The algorithms, as defined, use the % operator, the remainder division. Of course it is not available in all hardware implementations; on the other hand, even relatively simple microprocessors like the 16-bit Intel 8086 can divide a 32-bit integer by 65,535 and find the remainder with one single machine instruction (DIV). Regarding efficiency, consider the example of Intel386SX (developed in 1980's); in 32-bit mode it can execute DIV instruction, nominally, in 38 clock cycles [386SX]. This should be contrasted with the masking, shifting and addition operations that would be the division-free alternative (folding); they might together take some ten clock cycles. Also, divisions would not be frequently repeated anyway. Processing a typical incoming TCP segment might require exactly two division operations, one to the check the IPv4 header, the other to check the TCP data. So, compared with other necessary processing, division is likely to be a feasible alternative in some applications. But there is an alternative to division, folding (defined above). This algorithm reduces any positive integer to 16 bits without changing the remainder (again, it is found in RFC 1071): Heikkila Expires: May 2013 [Page 11] Internet Draft IP checksum November 5, 2012 while (sum>>16) sum = FOLD(sum); But usually sum has no more than 32 bits, in which case only two foldings are needed: sum = FOLD(FOLD(sum)); Note that folding never produces zero result (unless its argument is zero), so folding has wrap-to-one behaviour; see [Fig. 2]. This changes the algorithms slighly, as folding tends to produce 65,535 when true remainder is zero. So here are the algorithms for checksum generation (UDP considered separately) and checking, without division: checksum = 65535 - FOLD(FOLD(sum)); udp_checksum = FOLD(FOLD(0xffffffff - sum)); if (FOLD(FOLD(sum) != 65535) goto checksum_error; In many systems, operations (65535-x) and (0xffffffff-x) can be easily implemented with bit complement. Such optimizations are left to the reader as exercise. 5.3. Choice of Data Types We usually prefer unsigned integers, because division of signed integers is unpredictable in computers. (It is worth noting, however, that signed division can be faster than unsigned division in some implementations.) Usually 32-bit integers are suitable for blocksum calculations. For example, the maximum amount of data in a TCP/IPv4 segment is less than 65,535 octets (32,768 octet pairs), which sets an upper limit of block sum to 32,768*65,535 = 2,147,450,880; this means that blocksums fit in 32-bit integers, or even in signed 32-bit integers. However, 16-bit values can be calculated in parallel as 32-bit values, and then it may be advantageous to use 64-bit values for blocksums. See below for parallel calculation. 5.4. Efficient Calculation of Sum As RFC 1071 correctly points out, it is usually appropriate to optimize the checksum routine; and obviously the reading and summing loop is *the* most important point to optimize. Note that while the examples shown here are in the C programming language, the most Heikkila Expires: May 2013 [Page 12] Internet Draft IP checksum November 5, 2012 optimal solution is usually achieved with assembly language. Data sum should be calculated in the natural byte order, as in example above: "sum += *addr". This means that little-endian machines swap bytes, e.g., data that the network signifies as 0x1234 is summed as 0x3412. As known, and shown in the mathematical section above, this leads to correct results, if the calculated checksum is written to its field in the same natural manner: "*addr = checksum". Also, the important values 0 and 65,535 are immune to byte order. However, see section 5.5 below. It may be advantageous to read data in bigger pieces, 32 bits (or even 64 bits) as follows. However, addition must not overflow, which is why folding is used in this example: register unsigned long sum = 0; unsigned long *addr = . .; /* long assumed to have 32 bits */ int count = . . /* octet count */ while (count > 3) { sum += FOLD(*addr++); count -= 4; } But if the sum counter has 64 bits, folding as above is not necessary. As a curiosity, consider the following case, which assumes that sum is a 17-bit (sic!) integer and addr is a pointer to 16-bit integer: while ( . . . ) { sum += *addr++; sum = FOLD(sum); count -= 2; } The case of a "17-bit" integer may sound theoretical, but actually this is precisely what 16-bit processors often do: the sum is accumulated to a 16-bit register, which, together with the "carry" bit, is effectively a 17-bit counter. The FOLD operation corresponds to what RFC 1071 calls "end around carry". Often blocksum is calculated in pieces, and sometimes the start of some piece is not at an even offset from the beginning of data. Such calculation swaps the octets in the sum; but this can be corrected so that the blocksum is swapped again before incorporating to the final sum (as noted in RFC 1071). Heikkila Expires: May 2013 [Page 13] Internet Draft IP checksum November 5, 2012 5.5. Byte Order Issues As explained above, byte order should usually be ignored in software algorithms, permitting the processor to move data from memory to calculation as efficiently as possible. However, this means that checksum data is in network byte order while ordinary data is in host byte order. Then the standard operations "htons()" (host-to-network swap, short variable) and "ntohs()" (network-to-host) should be used as appropriate [POSIX]. Consider the case of IPv4 header, where the TTL field is decremented by 1 at every router, and this means that one element in the blocksum is decremented by 0x0100. In order not to recalculate the whole header checksum, the checksum is simply incremented by 0x0100, but this value must be modified as follows: new_chksum = ((unsigned long)old_chksum + htons(0x0100)) % 65535; Here, "htons()" is necessary because computers keep arithmetic constants in host byte order. (The pedantic typecast "(unsigned long)" is a C technicality to force the machine to use at least 32 bits during calculation to prevent overflow, even if old_chksum is a 16-bit integer. Here, the typecast is shown also with a documentation purpose, to emphasize that more than 16 bits are indeed necessary during the calculation.) Note: RFC 1141 and RFC 1624 consider a similar problem, but they emphasize hardware optimization (use bit operations instead of division), and do not mention byte order [RFC1141] [RFC1624]. 5.6. Incremental Update of Checksum Incremental update of checksum is an old idea; it is addressed in [RFC1141] and [RFC1624], and also section 5.5 above uses one case of it as an example. This section contains a new example, ICMPv6 Echo Reply message, to illustrate the method of incremental update. RFC 4443 defines the important Echo Request message, to which a host replies with Echo Reply (ping6). Suppose a host has received a Request message; naturally, it has to verify the checksum of that message before accepting it. Before sending the Reply message, the host has to calculate also the checksum over the reply. But since the Request and Reply are almost identical, some CPU time can be saved so that the Reply checksum is calculated from the Request checksum. Inspection of RFC 4443 shows that the checksums of Request and Reply differ only with respect to IPv6 addresses (in pseudo- header) and ICMPv6 type (and the checksum itself). So the methods of incremental update are well applicable to the Echo Reply case. We limit our consideration to the IPv6 address case; the update of ICMPv6 type from 128 to 129 is an easy exercise to the reader. Heikkila Expires: May 2013 [Page 14] Internet Draft IP checksum November 5, 2012 In some cases, the IPv6 addresses of Request and Reply are the same, just so that the source and destination are swapped; and the order of addresses does not, of course, change the checksum. But if the destination address of the Request is a multicast or anycast address, the source address of the Reply must be a unicast address; see [RFC4443], Sec. 4.2. In what follows, we imitate the notation of RFC 1624, using ordinary addition and subtraction instead of +' and bit complement. We occasionally use the congruence operation =' (modulo 65,535). HC - old checksum in ICMPv6 header C - blocksum of old data HC' - new checksum in ICMPv6 header (ICMPv6 type still unchanged) C' - blocksum of new data (ICMPv6 type still unchanged) m - blocksum over the 16-octet old address (multicast or anycast) m' - blocksum over the 16-octet new address (unicast) Then, if the blocksum of the unchanged part of the data is A, we have: A + m + HC = C A + m' + HC' = C' Subtracting the two equations we get this: HC' - HC + m' - m = C' - C Although C and C' need not be identical, they are the same modulo 65,535 (in fact, C =' C' =' 0, if the checksum is correctly calculated), so that C' - C =' 0. Then, doing elementary manipulations, we get these facts, analogously to RFC 1642: HC' =' HC + m - m' HC' =' -(m' - m - HC) Both of these formulas can be used. The former formula is suitable if we use division, and the latter one if we use folding. (RFC 1642 does not consider division and so prefers the latter formula.) We obtain the following C code (two alternatives): new_chk = (9*65535 + old_chk + oldaddr_sum - newaddr_sum) % 65535; new_chk = 65535 - FOLD(FOLD(9*65535 + newaddr_sum - oldaddr_sum - old_chk)); Heikkila Expires: May 2013 [Page 15] Internet Draft IP checksum November 5, 2012 The constant 9*65535 is chosen small enough so that 32-bit addition does not overflow but large enough so that subtraction cannot make the result negative. Note that a sum over a 16-bit IPv6 address cannot exceed 8*65,535 and a checksum cannot exceed 65,535, hence the constant 9. A final note: if we were to update UDP checksum incrementally, we would need a checksum in the range 1...65,535, and so the following C code would be appropriate (two alternatives, where old_ds and new_ds are sum over old data and sum over new data, respectively): n_udp_chk = 65535 - (N*65535 + new_ds - old_ds - o_udp_chk) % 65535; n_udp_chk = FOLD(FOLD(N*65535 + o_udp_chk + old_ds - new_ds)); Also in this case, N must be chosen according to circumstances so that addition and subtraction cannot lead to overflow or underflow in 32-bit arithmetic. Note that byte order is not an issue in this example, provided that all calculations are done with the same byte order (the octets in IPv6 addresses are calculated with the same algorithm as all other octets in the data). 5.7. The Last Octet If checksum is calculated over an odd number of octets, the last octet is alone and needs a zeroed octet to form a 16-bit unsigned integer. This is easy, if byte order is taken into account. Here are two ways to add the last octet to a sum: { unsigned short tmp = 0; ((unsigned char*)&tmp)[0] = ((unsigned char*)last_addr)[0]; sum += tmp; } sum += htons(((unsigned char*)last_addr)[0] << 8); Heikkila Expires: May 2013 [Page 16] Internet Draft IP checksum November 5, 2012 6. Security Considerations There are no security considerations relevant to this document. 7. IANA Considerations No actions are required from IANA as result of the publication of this document. 8. References 8.1. Normative References [RFC0768] Postel, J., "User Datagram Protocol", STD 6, RFC 768, August 1980. [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981. [RFC1071] Braden, R., Borman, D., and C. Partridge, "Computing the Internet checksum", RFC 1071, September 1988. [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [RFC4443] Conta, A., Deering, S., and M. Gupta, Ed., "Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification", RFC 4443, March 2006. 8.2. Informative References [POSIX] The Open Group Base Specifications Issue 7. IEEE Std 1003.1-2008. [RFC1141] Mallory, T. and A. Kullberg, "Incremental updating of the Internet checksum", RFC 1141, January 1990. [RFC1624] Rijsinghani, A., Ed., "Computation of the Internet Checksum via Incremental Update", RFC 1624, May 1994. [386SX] Intel386(TM) SX Microprocessor Programmers's Reference Manual. Inter Order No. 240331-002, ISBN 1-55512-154-3, 1991. Heikkila Expires: May 2013 [Page 17] Internet Draft IP checksum November 5, 2012 Authors' Addresses Heikki Heikkila Tellabs Oy Sinimaentie 6 C 02630 Espoo Finland EMail: heikki.heikkila@tellabs.com Heikkila Expires: May 2013 [Page 18]