TCP/IP Checksum

Why Detect Errors? A Transmission Example

During transmission, data can change because of electrical interference, hardware failures, software errors, or problems along the network path. The receiver therefore needs a way to detect that the received bits differ from the bits that were sent. Receiving a packet alone does not confirm that its contents are correct.

Data traveling across the internet passes through cables, routers, and switches. A data unit, a data packet, crosses that path as a header and payload. Along the way, a bit can change from 0 to 1 or from 1 to 0. This is called data corruption.

A single flipped bit can change a number in a financial transaction, corrupt an instruction in a software update, or create a glitch in a video stream. Protocols therefore need a mechanism to check whether received data agrees with the data that was sent. The TCP/IP Internet Checksum is a simple, fast method used by TCP, UDP, and IPv4 for a basic integrity check. IPv6 has no checksum in its base header, while upper-layer protocols can still use their own checksums.

Core Concept: Ones Complement Arithmetic

The Internet Checksum algorithm is based on a specific type of binary math called ones complement arithmetic. To understand it, we need to cover two simple operations. For all our examples, we will assume we are working with 16-bit numbers, as this is the standard size for the checksum.

1. The Ones Complement (Bitwise Inversion)

The ones complement of a binary number is its bitwise inverse. You take the number and flip every bit: every 0 becomes a 1, and every 1 becomes a 0. This is the final step in calculating the checksum value.

2. Ones Complement Addition with End-Around Carry

The calculation resembles standard binary addition but has one additional rule for the carry bit.

1. Perform Binary Addition: Add the two 16-bit numbers together just as you would in normal binary arithmetic.
2. Handle the Carry Bit (The Special Rule): If the sum of the 16-bit numbers is larger than what 16 bits can hold, a 17th bit, called a carry bit, is generated. In many forms of arithmetic, this bit is discarded. However, in ones complement addition, this carry bit is wrapped around and added back to the least significant bit (the rightmost bit) of the result. This is called an end-around carry.

How the Checksum is Calculated (Sender's Side)

The sender of a packet follows a simple four-step process to generate the checksum.

1. Step 1: Prepare the Data

   The sender takes the data to be protected, such as the TCP header and application data. It temporarily sets the checksum field in the header to all zeros ($00000000\ 00000000$), because that field belongs to the area being summed and must start from a known value.

   For TCP and UDP, the calculation also includes a pseudo-header containing the IP addresses, protocol number, and length. The pseudo-header verifies the context of the segment or datagram but is not transmitted as a separate part of it.

   In IPv4, a zero UDP checksum indicates that this check is omitted. For ordinary IPv6 traffic, a UDP checksum is required. A transmitted zero is therefore invalid and is discarded by receivers, except where a standards-defined IPv6 tunnel mode enables zero-checksum operation.

   IPv4 separately calculates a checksum for its header, and a router can recalculate it after changing fields such as TTL. IPv6 has no checksum field in its base header.

   If the total length of the bytes included in the calculation is odd, a temporary "padding" byte of all zeros is added to the end for calculation purposes. This lets the bytes be divided into 16-bit words. This padding byte is not transmitted with the packet.

2. Step 2: Sum the Data

   The data is divided into 16-bit words. The sender then adds all of these words together using ones complement addition, making sure to wrap around any carry bits as described before. This process continues until all 16-bit words have been added into a single 16-bit sum.

3. Step 3: Invert the Sum

   The final 16-bit sum from Step 2 is inverted by taking its ones complement (flipping all the bits). The resulting number is the Internet Checksum.

4. Step 4: Insert the Checksum

   The sender places this calculated checksum value back into the now-empty checksum field in the packet header. The packet is ready for transmission across the network.

How the Checksum is Verified (Receiver's Side)

Verification of a ones complement checksum is direct. The receiver does not need to reconstruct a separate reference value; it calculates the sum over the received area, including the checksum field.

1. Step 1: Receive the Packet

   The receiver gets the packet from the network. The packet includes the data as well as the checksum calculated by the sender, which is stored in the checksum header field.

2. Step 2: Sum Everything

   The receiver performs the same process as the sender: it divides the received data (including the header with the sender's checksum) into 16-bit words and adds them together using ones complement addition with end-around carry.

3. Step 3: Check the Result

   After summing all parts, the receiver checks the final 16-bit sum. The properties of ones complement arithmetic mean that:

   If there were no errors during transmission, the final sum at the receiver's end will be a 16-bit word consisting of all ones (11111111 11111111, or 0xFFFF in hexadecimal).

   If the final sum is anything other than all ones, the receiver detects likely corruption and responds according to the protocol rules. TCP can initiate retransmission of missing data, while UDP leaves error handling to the application.

Worked Example with 4-bit Words

Consider a simplified example with three 4-bit words: $1101$, $1000$, and $0110$.

On the Sender's Side

1. The sender adds the data words together using ones complement addition:
   
2. The final sum is $1100$.
3. The sender calculates the checksum by inverting the final sum: $\text{checksum} = \sim 1100 = 0011$.
4. The sender transmits the original data followed by the checksum: $1101, 1000, 0110, 0011$.

On the Receiver's Side (No Errors)

1. The receiver gets the four words ($1101, 1000, 0110, 0011$) and adds them all together:
2. The final sum is $1111$ (all ones). The receiver concludes the packet is free of errors and accepts it.

On the Receiver's Side (With an Error)

1. The first word $1101$ was corrupted during transmission and became $1100$.
2. The receiver now adds: $1100 + 1000 + 0110 + 0011$.
3. The final sum is $1110$, which is not all ones. The receiver detects the error and discards the packet.

Important Limitations of the Internet Checksum

The Internet Checksum is designed for fast calculation. Its simple algorithm can be implemented efficiently in software, which mattered in early networks when processor time was limited. That simplicity also creates limitations.

The checksum is not a cryptographically secure hash function. It can fail to detect several common types of errors:

• If two 16-bit words are swapped, the final sum remains the same.
• If a bit in one word is flipped from 0 to 1, and a corresponding bit in another word is flipped from 1 to 0, the errors can cancel each other out, and the checksum will still verify correctly.
• Inserting or deleting words that contain all zeros may also go undetected.

These limitations are acceptable for a lightweight additional check. Stronger error-detection mechanisms, such as the Cyclic Redundancy Check (CRC), are already applied at the Data Link Layer (e.g., by Ethernet). The Internet Checksum provides an extra, lightweight layer of protection against errors that might be introduced inside routers, where the link-layer header (and its CRC) is stripped off and reassembled for the next hop. It's a fast check sufficient for its specific role in the network stack.