Cryptographic Hash Functions · Message Authentication Codes

Message integrity asks two questions at once — did this really come from Alice, and is it unchanged — and a hash function on its own answers neither.

Words you will meet

Cryptographic hash function — a fingerprint nobody can forge a second message to match.
Message digest — another name for the fixed-length output H(m).
Authentication key — a secret string of bits, shared in advance, written s.
Message authentication code — the value H(m + s). This book writes MAC for media access control too; the note below explains.
HMAC (Hashed Message Authentication Code) — the most popular message authentication code standard, which runs the data and key through the hash twice.

Why this matters

Bob receives a message he believes came from Alice. To trust it he must verify two separate things: that it really originated from Alice, and that nobody tampered with it on the way.

The book’s example is not e-mail. It is chapter 5’s link-state routing. Each router broadcasts a list of its neighbours and their costs, and every other router builds a map from those messages. Trudy sending one bogus link-state message corrupts the forwarding tables of the entire network.

That is why message integrity runs through every remaining section of this chapter. It is not a nicety attached to confidentiality — it is a separate property, and the mechanism that provides it is separate too.

MAC means something else in this book

In chapter 6, MAC meant medium access control — the link-layer address burned into an interface.

Here it means message authentication code, and the two have nothing to do with one another. The book flags this collision itself. This site’s acronym page keeps the chapter 6 meaning, so on these pages the phrase is written out in full.

A hash is not a checksum

A hash function takes an input m and computes a fixed-size string H(m). The Internet checksum from chapter 3 and the CRCs from chapter 6 both fit that description.

A cryptographic hash function must have one extra property:

It is computationally infeasible to find any two different messages x and y such that H(x) = H(y).

Informally: an intruder cannot forge a second message with the same fingerprint as the first. Given (m, H(m)), Trudy cannot construct a different y whose hash matches.

An ordinary checksum fails that badly, and the book shows exactly how.

Figure 8.8 — two messages, one checksum

Message	bytes 1–4	bytes 5–8	bytes 9–12	checksum

What Bob means to sign: he owes Alice $100.99.

What Trudy substitutes: he owes Alice $900.19.

Cells marked ⓘ have an explanation — click to read it.

Add each column of bytes. Both messages give B2 C1 D2 AC. The digits 1 and 9 have simply swapped between the fourth and eighth positions, which sit in the same column — so the column sums cannot tell the difference.

Bob wants to sign an IOU for $100.99**. Trudy substitutes one for **$ 900.19. Both messages produce the checksum B2 C1 D2 AC.

Why the collision is arithmetic, not luck

The scheme adds the bytes in columns, four at a time. The fourth and eighth characters therefore land in the same column.

In the honest message those two are 1 (0x31) and 9 (0x39). In the forged one they are 9 and 1. One gained 8, the other lost 8, and the column total did not move.

That means finding a second message with a given checksum is not a search — it is a subtraction. tools/check-hash-ch08.mjs recomputes both checksums and then finds seven more messages of the same shape with the same value.

A cryptographic hash function is precisely one for which this cannot be done.

The two hash algorithms the book names

Algorithm	Output length	Note

Cells marked ⓘ have an explanation — click to read it.

A hash alone still does not give integrity

Now the obvious construction, and its failure.

Alice computes H(m) and sends (m, H(m)).
Bob receives (m, h), computes H(m), and checks that it equals h.

This is broken, and the reason is one line: the hash function is public. Trudy writes her own message m′ claiming to be Alice, computes H(m′) herself, and sends (m′, H(m′)). Bob’s check passes perfectly.

In plain words

A hash proves that the message and the fingerprint match each other. It does not prove that either of them came from Alice.

Anyone can make a matching pair, because anyone can run the hash function. What is missing is something only Alice could supply.

The message authentication code

Alice and Bob share a secret s — a string of bits called the authentication key — agreed in advance. Then:

Alice concatenates s with m, computes H(m + s), and calls it the message authentication code.
She sends (m, H(m + s)).
Bob, who also knows s, computes H(m + s) from the received message and compares.

Figure 8.9 — the message authentication code, step by step

The naive attempt: send the hash alongside the messagestep 1 of 4

Alice computes H(m) and sends (m, H(m)). Bob recomputes H(m) and compares. This looks fine and is completely broken.

Nothing here is encrypted. Watch where the secret enters and where it never travels.

Read all steps as text

The naive attempt: send the hash alongside the message — Alice computes H(m) and sends (m, H(m)). Bob recomputes H(m) and compares. This looks fine and is completely broken.
Add a shared secret before hashing — Alice concatenates the secret s with the message and hashes the result: H(m + s). That value is the message authentication code.
Send the message and the MAC — but not the secret — Alice sends (m, H(m + s)). The message itself may be plaintext; the MAC is what makes it trustworthy.
Bob recomputes it, because he also knows s — Bob receives (m, h), computes H(m + s) himself, and compares. If they match, the message came from someone holding s, and nothing in it has changed.

Trudy can still compute the hash of anything she likes. What she cannot do is compute H(m′ + s), because she does not have s.

Two things worth noticing about this construction

No encryption happens anywhere in it. The message may travel entirely in plaintext. Entities that care about integrity but not confidentiality get what they need without integrating any encryption algorithm at all — which is a real saving, and a real design freedom.

The secret never travels. It is an input to a hash, not something sent. That is what separates this from every scheme in section 8.2.

Checksum, cryptographic hash, and MAC

	Internet checksumchapter 3	Cryptographic hash§8.3.1	MAC§8.3.2
What goes in
Can you find a second message with the same output?
Detects accidental corruption?
Detects a deliberate substitution?
Says who sent it?

Cells marked ⓘ have a reason behind them — click to read it.

Three things that produce a short string from a long one, and they are not interchangeable. Click any cell.

The standard in practice is HMAC, usable with either MD5 (Message Digest 5) or SHA-1. It runs the data and the authentication key through the hash function twice.

The problem this leaves behind

There is still an unanswered question, and the book asks it directly: how does the shared authentication key reach the parties in the first place?

For the link-state example, every router in the autonomous system needs the secret — and they can all use the same one. A network administrator could visit each router physically. Or, if each router already has a public key, the administrator can encrypt the authentication key with that router’s public key and send it over the network.

That is section 8.2.2 being used to bootstrap this section. It is the same shape as the session key — the expensive public-key operation runs once, on something tiny, to establish the cheap shared secret.

The mental model

Three things shorten a long message into a short string, and they answer different questions.

A checksum answers “did this get corrupted by accident?” A cryptographic hash answers the same question against an attacker who cannot forge a collision. Neither says anything about who sent it. A MAC answers “did someone holding the shared secret send this, unchanged?”

The difference between the last two is a single extra input, and that input never leaves the machines that already know it.

Check yourself

0 of 7 answered

1.What extra property does a cryptographic hash function have, that the Internet checksum does not?
2.predictIn Figure 8.8 the digits 1 and 9 swap between the fourth and eighth characters. Why does the checksum not change?
3.Alice sends (m, H(m)) and Bob checks that the hash matches. Why is this not message integrity?
4.What exactly does the shared secret s add?
5.Every router in an autonomous system shares one authentication key. A router receives a link-state message with a valid MAC. What has it learned?
6.How does the book suggest distributing the shared authentication key to routers, if the administrator does not want to visit each one?
7.MAC appeared in chapter 6 as well. Does it mean the same thing?

What to remember

A hash alone gives no integrity, because the hash function is public. Trudy writes her own message, hashes it herself, and Bob’s check passes. What is missing is something only Alice could supply.
The MAC adds a shared secret as an input to the hash, and encrypts nothing. H(m + s) travels alongside a message that may be entirely plaintext, and the secret s never appears on the wire at all.
A checksum collision is arithmetic, not search. Swapping two digits that land in the same column of Figure 8.8’s grid leaves every column total unchanged — which is exactly the property a cryptographic hash must not have.