Dec 08·6 min· PV

Internet Checksum

Notes from designing an Internet checksum lab, covering parallel summation and incremental checksum updates.

The Internet checksum, also known as the IPv4 header checksum, is widely used by IPv4 and ICMP at the network layer and by TCP and UDP at the transport layer, though the range of data each protocol covers differs.

Protocol	Checksum coverage
IPv4	IP Header
ICMP	IP Header + ICMP Data
TCP	PseudoHeader + TCP Header + TCP Data
UDP	PseudoHeader + UDP Header + UDP Data

The IPv6 header contains no checksum field, which simplifies the work of routers. Data integrity is left to higher-layer protocols, which is why IPv6 makes the UDP checksum mandatory.

Internet Checksum Algo

Common Solution

First, group the header byte array into pairs of 2 bytes and convert them into a sequence of 16-bit integers, corresponding to uint16_t in C’s <stdint.h>.

The following code shows how to merge two bytes into one 16-bit integer using bitwise operations or multiplication.

uint_8 byte1 = 0x45;uint_8 byte2 = 0x00;// Shift byte1 left by 8 bits, then OR it with byte2uint_16 word = (byte1 << 8) | byte2; // 0x4500// If the header length is odd (in bytes), pad the last byte with a trailing zerouint_16 last_word = last_bytes << 8);

Next, compute the 1’s complement sum. One way to do this: add all the 16-bit integers together and store the result in a 32-bit integer, call it sum. If the high 16 bits of sum are nonzero, add the high 16 bits to the low 16 bits. Repeat until the high 16 bits are zero.

Finally, take the complement of the sum. That is the checksum.

1’s complement sum
On a 2’s complement machine, the 1’s complement sum must be computed by means of an “end around carry”, i.e., any overflows from the most significant bits are added into the least significant bits.
RFC 1071

The following example may help in understanding the algorithm above.

An IP4 packet with a 20-byte header, shown in hexadecimal:   IP4 Header Bytes:1. 0x45, 0x00, 0x00, 0x142. 0x00, 0x00, 0x00, 0x003. 0x40, 0x00, 0x00, 0x004. 0xA8, 0xE0, 0x17, 0xE75. 0x85, 0xE9, 0xE8, 0xBCsum:0x4500 + 0x0014 + 0x0000 + 0x0000 + 0x4000 + 0x0000 + 0xA8E0 + 0x17E7 + 0x85E9 + 0xE8BC = 0x0002B480wraparound:0x0002 + 0xB480 = 0xB482checksum = ~(0xB482) = 0x4B7D

Parallel Summation

When the checksum covers a small range, such as a 20-byte IP4 header, the algorithm above performs acceptably.

For TCP, however, the checksum covers (pseudo-header、TCP header、TCP data), which can be fairly large, so efficiency matters.

RFC-1071 Parallel Summation describes a way to compute the checksum in parallel, which improves efficiency considerably.

0x45, 0x00, 0x00, 0x14  -> uint_32t 0x4500_00140x00, 0x00, 0x00, 0x00  -> uint_32t 0x0000_00000x40, 0x00, 0x00, 0x00  -> uint_32t 0x4000_00000xA8, 0xE0, 0x17, 0xE7  -> uint_32t 0xA8E0_17E70x85, 0xE9, 0xE8, 0xBC  -> uint_32t 0x85E9_E8BCsum: (sum should now be stored as uint_64t)0x4500_0014 + 0x0000_0000 + 0x4000_0000 + 0xA8E0_17E7 + 0x85E9_E8BC = 0x0000_0001_B3CA_00B7wraparound:0x0000_0000_0001_B3CA + 0x00B7 = 0x0000_0000_0001_B4810x0000_0000_0000_0001 + 0xB481 = 0x0000_0000_0000_B482The corresponding pseudocode:while (sum > 0xFFFF) {    sum = (sum & 0xFFFF) + (sum >> 16);}checksum = ~(0xB482) = 0x4B7D

uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {    /**     * Compute the Internet checksum     *     * @hex_bytes_array: a hexadecimal byte array, e.g. {0x45, 0x00, 0x00, 0x14,     * 0x00, 0x00, 0x00, 0x00}     * @count: length of the byte array; watch out for odd lengths     * @return the computed 16-bit checksum     */    uint32_t sum = 0;  // Store the sum in 32 bits; a 16-bit result risks overflow    size_t i = 0;    while (i + 1 < count) {        uint16_t word = (hex_bytes_array[i] << 8) | hex_bytes_array[i + 1];        sum += word;        i += 2;    }    if (count % 2 == 1) {        sum += hex_bytes_array[count - 1] << 8;    }    // wraparound    while (sum > 0xFFFF) {        sum = (sum & 0xFFFF) + (sum >> 16);    }    // Return the 1's complement of the sum: checksum = ~sum    return (uint16_t)~sum;}

uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {    uint64_t sum = 0;  // Use uint64_t to prevent overflow    size_t i = 0;    // Split the byte array into 32-bit chunks and add them in parallel    while (i + 3 < count) {        // Read 4 bytes as one 32-bit integer        sum +=            (uint32_t)(hex_bytes_array[i] << 24 | hex_bytes_array[i + 1] << 16 |                       hex_bytes_array[i + 2] << 8 | hex_bytes_array[i + 3]);        i += 4;    }    if (i < count) {        uint32_t word = 0;        // Read the remaining bytes as one 32-bit integer        for (size_t j = 0; i < count; i++, j++) {            word |= hex_bytes_array[i] << (24 - j * 8);        }        sum += word;    }    // wraparound    while (sum > 0xFFFF) {        sum = (sum & 0xFFFF) + (sum >> 16);    }    // Return the 1's complement of the sum: checksum = ~sum    return (uint16_t)~sum;}

Incremental Update Checksum

RFC 1071 first sketched the idea of incremental updates, RFC 1141 gave a technical implementation, and RFC 1624 later corrected some errors in RFC 1141.

You can implement incremental checksum updates following RFC 1624. The formula:

HC  - old checksum in headerC   - one's complement sum of old headerHC' - new checksum in headerC'  - one's complement sum of new headerm   - old value of a 16-bit fieldm'  - new value of a 16-bit fieldHC' = ~(C + (-m) + m')    = ~(~HC + ~m + m')

Below is a sample program. The code itself is simple; the point is to understand how incremental checksum updates work.

#include <stdint.h>#include <stdio.h>uint16_t incremental_update_checksum(uint16_t old_checksum, uint16_t old_value,                                     uint16_t new_value) {    uint32_t res = ~(~old_checksum + ~old_value + new_value);    return (uint16_t)(res);}int main() {    printf("Incremental update checksum test\n");    uint16_t old_checksum = 0xDD2F;    uint16_t old_value = 0x5555;    uint16_t new_value = 0x3285;    uint16_t new_checksum =    incremental_update_checksum(old_checksum, old_value, new_value);    printf("Incremental update checksum: 0x%04X\n", new_checksum);}OutputIncremental update checksum testIncremental update checksum: 0x0000

Reference

RFC 791 INTERNET PROTOCOL Written by Jon Postel et al. in 1981, it defines the IPv4 specification; the IP4 Datagram format in this post follows this document.
RFC 1071 Computing the Internet Checksum: Describes how to compute the Internet checksum and introduces several optimizations.
RFC 1141 Incremental Updating of the Internet Checksum: Describes an algorithm for incrementally updating the checksum.
RFC 1624 Computation of the Internet Checksum via Incremental Update RFC 1624 fixes the problems in the incremental update algorithm described in RFC 1141.