Incremental Checksum: Incremental updating of the Internet checksum
A corrected recipe for patching the Internet checksum when only one field of a packet changes.
Mallory, T. and A. Kullberg, "Incremental updating of the Internet checksum", RFC 1141, DOI 10.17487/RFC1141, January 1990, <https://www.rfc-editor.org/info/rfc1141>.
@misc{rfc1141,
series = {Request for Comments},
number = 1141,
howpublished = {RFC 1141},
publisher = {RFC Editor},
doi = {10.17487/RFC1141},
url = {https://www.rfc-editor.org/info/rfc1141},
author = {T. Mallory and A. Kullberg},
title = {{Incremental updating of the Internet checksum}},
pagetotal = 2,
year = 1990,
month = jan,
} RFC text
Contents
Network Working Group T. Mallory Request for Comments: 1141 A. Kullberg Obsoletes: RFC 1071 BBN Communications January 1990 Incremental Updating of the Internet Checksum Status of this Memo This memo correctly describes the incremental update procedure for use with the standard Internet checksum. It is intended to replace the description of Incremental Update in RFC 1071. This is not a standard but rather, an implementation technique. Distribution of this memo is unlimited. Description In RFC 1071 on pages 4 and 5, there is a description of a method to update the IP checksum in the IP header without having to completely recompute the checksum. In particular, the RFC recommends the following equation for computing the update checksum C' from the original checksum C, and the old and new values of byte m: C' = C + (-m) + m' = C + (m' - m) While the equation above is correct, it is not very useful for incremental updates since the equation above updates the checksum C, rather than the 1's complement of the checksum, ~C, which is the value stored in the checksum field. In addition, it suffers because the notation does not clearly specify that all arithmetic, including the unary negation, must be performed one's complement, and so is difficult to use to build working code. The useful calculation for 2's complement machines is: ~C' = ~(C + (-m) + m') = ~C + (m - m') = ~C + m + ~m' In the oft-mentioned case of updating the IP TTL field, subtracting one from the TTL means ADDING 1 or 256 as appropriate to the checksum field in the packet, using one's complement addition. One big-endian non-portable implementation in C looks like: unsigned long sum; ipptr->ttl--; /* decrement ttl */ sum = ipptr->Checksum + 0x100; /* increment checksum high byte*/ ipptr->Checksum = (sum + (sum>>16)) /* add carry */ This special case can be optimized in many ways: for instance, you can bundle updating and checking the ttl. Compiler mileage may vary. Here is a more general and possibly more helpful example which updates the ttl by n seconds: UpdateTTL(iph,n) struct ip_hdr *ipptr; unsigned char n; { unsigned long sum; unsigned short old; old = ntohs(*(unsigned short *)&ipptr->ttl); ipptr->ttl -= n; sum = old + (~ntohs(*(unsigned short *)&ipptr->ttl) & 0xffff); sum += ntohs(ipptr->Checksum); sum = (sum & 0xffff) + (sum>>16); ipptr->Checksum = htons(sum + (sum>>16)); } Security Considerations Security issues are not addressed in this memo. Authors' Addresses Tracy Mallory BBN Communications Corporation 50 Moulton Street Cambridge, MA 02238 Phone: (617) 873-3193 EMail: tmallory@CCV.BBN.COM A. Kullberg BBN Communications Corporation 50 Moulton Street Cambridge, MA 02238 Phone: (617) 873-4000 EMail: akullberg@BBN.COM
AI ELI5
On this page
§1Why an Update Was Needed
RFC 1071 describes a way to update the checksum in an IP header without recomputing it completely. It recommends the equation C' = C + (-m) + m' = C + (m' - m), where C is the original checksum and m and m' are the old and new values of the changed byte.
This memo says the equation is correct but not very useful. It updates C, while the value stored in the checksum field is ~C, the complement. It also does not make clear that all arithmetic, including the unary negation, must be done in one's complement, so it is hard to build working code from it.
The old recipe was right, but it told you how to fix a number that nobody writes down, and it did not say which kind of adding to use. This note fixes both problems.
§2The Corrected Update Rule
For 2's complement machines, the memo gives the useful calculation as ~C' = ~(C + (-m) + m') = ~C + (m - m') = ~C + m + ~m'. This works directly on the value stored in the packet and uses one's complement addition.
The memo points to the common case of updating the IP TTL field. Subtracting one from the TTL means adding 1 or 256 to the checksum field, as appropriate, using one's complement addition.
Take the number on the label, add the small difference, and carry any overflow back around. That gives the new label without redoing all the work.
§3C Examples for the TTL
The first example is a big-endian, non-portable C snippet. It decrements the TTL, adds 0x100 to the checksum, and folds the carry back in. The memo notes that this special case can be optimized in many ways, for instance by bundling the TTL update with the TTL check, and that compiler mileage may vary.
The second example, UpdateTTL, is more general. It lowers the TTL by n seconds, adds the old 16-bit word to the complement of the new one and to the stored checksum, then folds the carries twice before storing the result.
There are two little programs. One handles taking exactly one off the counter, and the other handles taking off any amount.
§4Security Considerations
The memo states that security issues are not addressed. It describes only a faster way to keep an existing checksum correct after a field changes.
This note is only about doing the arithmetic right. It does not say anything about keeping secrets or stopping bad guys.