Detecting Corruption

A receiver cannot know what the sender meant, only what arrived. To notice that data changed on the way, the sender attaches a small summary computed from it, and the receiver computes the same summary from what it got and compares. If the two differ, something changed. If they match, the data is probably intact, and this topic is about that "probably".

Parity, checksums, CRCs and cryptographic hashes are four answers of increasing cost, each built to catch a different kind of damage. None of them proves a file is correct. Each proves only that the data matches a summary, and only against the failures it was designed for. A wrong pick fails silently, letting corruption sail through a check everyone trusted.

Parity

The cheapest check is one extra bit, set so that the total number of ones is even. The receiver counts the ones again, and an odd total means something flipped. Parity catches any single flipped bit, and any odd number of flips. It misses every even number, because two flips cancel out in the count.

The figure uses the digit 2 from a feed message, whose byte has three ones, so its parity bit is 1. Flip one bit and the byte reads 3, with an odd total: caught. Flip two neighbouring bits and it reads 1, with an even total again: missed, and Lantern would record one copy on the shelf instead of two. Parity suits places where errors are rare and come one at a time. Extended into an error-correcting code, the same idea can say which bit flipped and repair it, which is what ECC memory in servers does.

Checksums

A checksum adds the data up in fixed-size words and sends the sum. The Internet checksum, defined in RFC 1071 and carried by IPv4 headers, UDP and TCP, adds the data as 16-bit words, folds each carry back into the total and sends the complement. It is cheap enough to compute in software for every packet, which was the point when it was designed.

def internet_checksum(data: bytes) -> int:
    total = 0
    for i in range(0, len(data), 2):
        total += (data[i] << 8) | data[i + 1]
        total = (total & 0xFFFF) + (total >> 16)   # fold the carry back in
    return ~total & 0xFFFF

# b"branch 7, record 1048576: 2 on shelf"   checksum 0xb367   crc32 0x71cdfddc
# b"branch 7, record 1850476: 2 on shelf"   checksum 0xb367   crc32 0x2bd2dc34

The algorithm fits in the function above: add 16-bit words, keep the total within 16 bits by folding the overflow back in, and send the complement. The two messages under it differ in the record number. Swapping two aligned pairs of digits turned record 1048576 into record 1850476, and because addition does not care about order, the checksum is identical. The CRC in the last column changed completely.

That is the checksum's weakness: it misses reordered words and errors that cancel out. On real traffic the gap is measurable. Jonathan Stone and Craig Partridge traced real internet packets for their paper "When the CRC and TCP Checksum Disagree" in 2000. Between 1 packet in 1,100 and 1 in 32,000 failed the TCP checksum, even on links whose own CRC should have caught almost everything, so the damage was happening inside hosts and routers. They estimated that the checksum lets a corrupted packet through somewhere between once in 16 million packets and once in 10 billion.

CRCs

A cyclic redundancy check treats the data as one long binary number, divides it by a fixed divisor and sends the remainder. The arithmetic is chosen to catch what real links produce. A 32-bit CRC catches every burst of flipped bits no longer than 32 bits, and other damage slips through with odds of about 1 in 4 billion. Ethernet frames, zip archives and PNG images all carry a 32-bit CRC.

Noise on a wire tends to damage neighbouring bits together, which is the upper strip in the figure: twenty bits in a row, inside the CRC's 32-bit span, caught every time. Scattered damage, the lower strip, is caught all but about once in 4 billion. CRCs are also fast. Measured through Python 3.15 on one laptop, an Apple M1 Max, the CRC-32 routine ran at about 29 gigabytes a second, because modern processors have an instruction for it.

Cryptographic Hashes

A cryptographic hash such as SHA-256 turns any input into 256 bits in a way that makes finding two inputs with the same result infeasible, even for an attacker who tries on purpose. That property, not stronger detection of accidents, is what it adds over a CRC. It costs more: on the same laptop SHA-256 ran at about 2.5 gigabytes a second, roughly a tenth of the CRC's speed. Git names every object by its hash, and package managers pin each download to one.

The older cryptographic hashes are broken only against deliberate attacks. Researchers produced MD5 collisions in 2004 and a practical SHA-1 collision, called SHAttered, in 2017. Both still detect accidental corruption as well as ever. Chapter 5 covers the third family, the fast hashes that hash tables use, which are built for speed and spread and resist neither.

Integrity Is Not Authenticity

Any check sent alongside the data can be replaced alongside the data. Someone who can change the file can recompute its CRC, and with no more effort its SHA-256. A hash protects a download only when the expected value arrives by a path the attacker cannot touch: a signed release, a lock file committed to your own repository, a value pinned in your deployment configuration.

Proving who sent a message needs a key. A message authentication code, or MAC, is a hash keyed with a shared secret, and a digital signature uses a private key that only the sender holds. Both are named here and belong to the security courses. The dividing line is simple to state: a check anyone can compute defends against accidents, and only a check that needs a secret defends against people.

Where Checks Belong

Data is corrupted in places no network check sees: in a server's memory, on a disk, in a buggy copy routine. File systems that checksum every block, such as ZFS and Btrfs from Chapter 10, find the damage when the block is read. Object stores return a hash of what they stored, so a client can compare it with the hash it computed before sending. An application that keeps a hash beside its own records can tell, years later, that a copy is bad.

The cheapest check that matches the threat is the right one. A CRC is correct for a network link and wrong for a software download. A SHA-256 is correct for a download and wasteful for every frame on a wire. No check at all is the only answer that is never right.