【计网拾遗】Internet Checksum

因特网检验和（Internet checksum），也称为 IPv4 头部校验和，被广泛应用于网络层的 IPv4 、ICMP 以及运输层的 TCP 和 UDP 等协议，但在校验的数据范围上有所不同。

Protocol	校验和计算范围
IPv4	IP Header
ICMP	IP Header + ICMP Data
TCP	PseudoHeader + TCP Header + TCP Data
UDP	PseudoHeader + UDP Header + UDP Data

IPv6 的首部不包含校验和字段，以简化路由器的工作。保证数据完整性的工作被交由更高层的协议完成，因此 IPv6 强制 UDP 也要计算校验和。

Internet Checksum Algo

Common Solution

首先，将报文首部数组按每 2 个字节为一组，转换为一系列 16 位的整数，对应 C 语言<stdint.h>中uint16_t

可参考如下代码，通过位运算或乘法将两个字节合并为一个 16 位整数。

1
2
3
4
5
6

uint_8 byte1 = 0x45;
uint_8 byte2 = 0x00;
// 将 byte1 的值左移 8 位，然后与 byte2 的值进行或运算
uint_16 word = (byte1 << 8) | byte2; // 0x4500
// 如果首部的长度为奇数（单位：字节），那么最后一个字节末尾补 0
uint_16 last_word = last_bytes << 8);

然后，计算 1 的补码和(1’s complement sum)。一种计算方式为：首先，将所有 16 位整数相加，和存储到一个 32 位整数中，记作sum。如果sum的高 16 位不为 0，将高 16 位加到低 16 位上。重复这个过程，直到和的高 16 位为 0。

最后，将和取反，即为校验和

1’s complement sum —— 摘自 RFC 1071
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.

上述算法的计算过程，可结合如下示例进行理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

一个首部长度为 20 字节的 IP4 报文，它的十六进制表示如下：

   IP4 Header Bytes:
1. 0x45, 0x00, 0x00, 0x14
2. 0x00, 0x00, 0x00, 0x00
3. 0x40, 0x00, 0x00, 0x00
4. 0xA8, 0xE0, 0x17, 0xE7
5. 0x85, 0xE9, 0xE8, 0xBC

sum：
0x4500 + 0x0014 + 0x0000 + 0x0000 + 0x4000 + 0x0000 + 0xA8E0 + 0x17E7 + 0x85E9 + 0xE8BC = 0x0002B480

wraparound：
0x0002 + 0xB480 = 0xB482

checksum = ~(0xB482) = 0x4B7D

Parallel Summation

如果校验和的计算范围比较小时，例如 20 字节的 IP4 首部，那么上述算法的效率是可以接受的。
但对于 TCP 来说，它的校验和字段计算的范围是 (pseudo-header、TCP header、TCP data)，这个范围可能会比较大，因此需要考虑算法的效率。

RFC-1071 [Page 3] Parallel Summation 中给出了一种并行计算校验和的方法，可以有效提高计算效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

0x45, 0x00, 0x00, 0x14  -> uint_32t 0x4500_0014
0x00, 0x00, 0x00, 0x00  -> uint_32t 0x0000_0000
0x40, 0x00, 0x00, 0x00  -> uint_32t 0x4000_0000
0xA8, 0xE0, 0x17, 0xE7  -> uint_32t 0xA8E0_17E7
0x85, 0xE9, 0xE8, 0xBC  -> uint_32t 0x85E9_E8BC

sum: (此时 sum 应该用 uint_64t 存储)
0x4500_0014 + 0x0000_0000 + 0x4000_0000 + 0xA8E0_17E7 + 0x85E9_E8BC = 0x0000_0001_B3CA_00B7

wraparound:
0x0000_0000_0001_B3CA + 0x00B7 = 0x0000_0000_0001_B481
0x0000_0000_0000_0001 + 0xB481 = 0x0000_0000_0000_B482

对应伪代码如下
while (sum > 0xFFFF) {
    sum = (sum & 0xFFFF) + (sum >> 16);
}

checksum = ~(0xB482) = 0x4B7D

• common_solution

• parallel_summation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {
    /**
     * 计算互联网校验和
     *
     * @hex_bytes_array: 表示十六进制字节数组，形如{0x45, 0x00, 0x00, 0x14,
     * 0x00, 0x00, 0x00, 0x00}
     * @count: 字节数组的长度，注意 len 为奇数的情况
     * @return 计算得到的 16 bit 校验和
     */
    uint32_t sum = 0;  // 使用 32位 存储校验和，使用 16 位存储结果有溢出风险

    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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {
    uint64_t sum = 0;  // 使用 uint64_t 防止溢出
    size_t i = 0;

    // 将字节数组分成32位的块并进行并行加法
    while (i + 3 < count) {
        // 将4个字节作为一个32位整数读入
        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;
        // 将剩余的字节作为一个32位整数读入
        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 初步提出增量更新的设想，RFC 1141 给出技术实现，之后 RFC 1624 针对 RFC 1141 中的部分错误进行了修正。

可参考 RFC 1624 实现增量更新校验和。公式如下

1
2
3
4
5
6
7
8
9
10

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


HC' = ~(C + (-m) + m')
    = ~(~HC + ~m + m')

下面是一个示例代码，代码比较简单，重在理解增量更新校验和的原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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);
}

输出
Incremental update checksum test
Incremental update checksum: 0x0000

Reference

• RFC 791 INTERNET PROTOCOL 由 Jon Postel 等人于 1981 年编写，定义了 IPV4 的相关规范，本文中 IP4 Datagram 的格式与该文档一致。
• RFC 1071 Computing the Internet Checksum： 主要介绍 Internet Checksum 的计算方法，引出几种优化方案。
• RFC 1141 Incremental Updating of the Internet Checksum：介绍了增量更新校验和的算法实现。
• RFC 1624 Computation of the Internet Checksum via Incremental Update RFC 1624 主要解决了 RFC 1141 中描述的增量更新校验和算法存在的问题