Checksums

For this lesson, we'll cover what checksums can and can't detect, work through the Internet checksum by hand, compare it with CRCs, cryptographic hashes and HMACs, and map where each one shows up in real systems, from TCP headers to S3 uploads to Dropbox-style chunking. This is a "good to know" topic: it rarely gets its own question, but it decides whether your answer to "how do you know the file you stored is the file the user uploaded?" sounds hand-wavy or precise.

01Picture it first: compute, send, recompute

Every scheme on this page follows the same four steps; they differ only in the function f and who's allowed to compute it.

Notice three things:

• Detection, not correction. A checksum tells you that something changed, not what. Recovery is a separate step: retransmit the packet, read another replica, restore a backup.
• Match means "probably unchanged". A 16-bit checksum has only 65,536 possible values, so some corruptions will land on the same value. Bigger and better-mixed functions make that vanishingly unlikely.
• No secret, no security. If the attacker can change the bytes, they can change the checksum. That's the whole difference between a checksum and a MAC.

02The Internet checksum, by hand

IP, TCP and UDP all use the same function, defined in RFC 1071: treat the data as 16-bit words, add them with ones'-complement arithmetic (any carry out of the top bit is wrapped around and added back at the bottom), then flip every bit of the result. The receiver adds up everything including the checksum, and a correct packet sums to 0xFFFF.

Here's my working:

  0x8F2A
+ 0x9B11
= 0x12A3B   ← carry out of 16 bits
→ 0x2A3B + 0x1 = 0x2A3C   (end-around carry)
+ 0x1234
= 0x3C70
checksum = ~0x3C70 = 0xC38F            (sent with the data)

Receiver, data intact:   0x3C70 + 0xC38F = 0xFFFF   ✓ accept
One bit flipped (0x8F2B): 0x3C71 + 0xC38F = 0x10000 → 0x0001   ✗ caught
Words 1 and 2 swapped:    same sum, 0xFFFF   ✓ accepted: missed!
+1 in word 1, -1 in word 2: same sum, 0xFFFF   ✓ accepted: missed!

That's the design trade-off in four lines. The Internet checksum is a sum, so it can't see reordering and it misses errors that cancel out. It was chosen because it's cheap to compute in software and can be updated incrementally when a router changes one header field, not because it's strong.

03CRCs, hashes and MACs: picking the right tool

The four families answer different questions. The table is what I'd draw if an interviewer asks "would a checksum stop that?"

A few lines on each:

• CRC (cyclic redundancy check). Treats the data as a big polynomial and keeps the remainder after dividing by a fixed one. It's built for the errors hardware actually makes: bursts of flipped bits. CRC32C uses the Castagnoli polynomial, which modern x86 and ARM CPUs can compute with dedicated instructions, so it costs almost nothing. Java ships it as java.util.zip.CRC32C since Java 9.
• Cryptographic hash (SHA-256). Designed so nobody can find two inputs with the same output. That makes the hash a safe name for the content, which is what deduplication relies on. MD5 and SHA-1 are still fine for catching accidental corruption but broken for anything adversarial.
• HMAC. A hash mixed with a secret key. Only someone holding the key can produce a matching tag, so it proves integrity and origin. A digital signature does the same with a public/private key pair, so anyone can verify without being able to sign.

04In Java

Here's what each of those looks like in code. Each is a few lines; the hard part is deciding which one the threat calls for.

// Accidental corruption: CRC32C (Java 9+), cheap enough for every block
CRC32C crc = new CRC32C();
crc.update(block, 0, block.length);
long crc32c = crc.getValue();

// Content identity / dedup: SHA-256
byte[] sha256 = MessageDigest.getInstance("SHA-256").digest(block);

// Tampering: HMAC-SHA256 with a shared secret
Mac mac = Mac.getInstance("HmacSHA256");
mac.init(new SecretKeySpec(secret, "HmacSHA256"));
byte[] expected = mac.doFinal(body);
boolean authentic = MessageDigest.isEqual(expected, receivedTag); // constant-time compare

Notice the last line. Comparing MACs with Arrays.equals can leak, through timing, how many leading bytes matched; MessageDigest.isEqual doesn't stop early.

05Where checksums live in a system

Every layer checks its own piece of the path, and each one stops at its boundary. This figure is the reason "TCP already has a checksum" isn't an answer.

The end-to-end argument

This pattern has a name. Saltzer, Reed and Clark's 1984 paper on the end-to-end argument uses careful file transfer as its example: however reliable each step is, only a check by the endpoints, comparing what was written with what was read, can guarantee the file arrived intact. Lower-layer checks are still worth having because they catch most errors early and cheaply, but they're a performance optimisation, not the guarantee.

06How it shows up in design problems

You'll rarely be asked "explain CRC32". You'll be asked about uploads, storage and messaging, and a checksum is the precise answer to the integrity follow-up.

File upload, sync and dedup

In Design Dropbox / Google Drive, the standard move is to split files into fixed-size chunks and name each chunk by its hash. Dropbox's engineering blog (Streaming file synchronization) describes exactly this: files split into 4 MB blocks, each hashed with SHA-256, and a file described by its list of block hashes.

The client sends the hash list first, the server answers with the hashes it doesn't have, and only those blocks travel. Unchanged blocks of an edited file, and files another user already uploaded, cost nothing. Because the block's name is its hash, the store verifies every block on arrival for free. Two cautions: cross-user dedup can leak whether a file already exists (an attacker uploads a guess and watches whether it transfers), and a change near the start of a file shifts every fixed-size block after it, which content-defined chunking fixes at some complexity.

Other problems

• Design an object store like S3: client-supplied checksums on upload, stored with the object, re-verified on read and by a background scrubber that repairs from another replica.
• Design a distributed message queue (Kafka): a CRC per batch, set by the producer and checked by the consumer, so a bad disk on one broker can't silently corrupt messages.
• Design a webhook delivery service: an HMAC signature over the body plus a timestamp, so receivers can reject forged or replayed calls. That's integrity and authenticity, not a checksum.
• Design a key-value store: Merkle trees (hashes of hashes) let two replicas find which key ranges differ without comparing every value.

At this point, you should ask your interviewer what you're defending against. "Bit rot and bad disks" leads to CRC32C and scrubbing; "a malicious client or a man in the middle" leads to HMACs, signatures and TLS.

07Trade-offs and failure modes

08Follow-up questions

What if the interviewer asks: "TCP already has a checksum, why add another?"

TCP's 16-bit checksum covers only the hop between two hosts' network stacks, it misses reordered and cancelling errors, and it says nothing about data sitting in memory, on disk, or passing through proxies that re-send it on a new connection. Measurements of real traffic found errors slipping past it at rates you hit every day at scale. An application checksum covers the whole path.

What if two different chunks have the same hash in a dedup system?

With SHA-256, finding a collision isn't practically possible, so systems treat the hash as the identity. With CRC32 it would happen by chance after tens of thousands of chunks, which is why CRC is used to detect corruption, never to name content. If someone insists, you can compare the bytes on a hash match, at the cost of reading the stored chunk.

What if a disk silently corrupts a block that nobody reads for a year?

Then the corruption is discovered only when a user asks, and by then the other replicas may have failed too. Store a checksum with every block, verify on every read, and run a background scrubber that reads cold data on a schedule and repairs bad copies from healthy replicas.

What if an attacker can modify messages in your internal queue?

Then CRCs don't help; they'll recompute them. Sign messages with an HMAC using a key the attacker doesn't have, or a signature if many consumers need to verify without being able to sign, and protect the transport with TLS. Rotate keys and include a key ID so you can.

09How to say it in the interview

When I ask "how do you know the data wasn't corrupted?", I'm listening for three things: that you separate accidental corruption from tampering, that you pick a function to match, and that you check end to end rather than trusting each layer.