HMAC

Read six things out of that run.

The compact SHA-256 agrees with the standard library, checked on the first line before anything is built on it.

All three RFC 4231 vectors match, including the 131-byte key, which is longer than the 64-byte block and so must be hashed first. That case is the one implementations get wrong.

The two pads differ in four of eight bits, so K0 XOR ipad and K0 XOR opad differ in half their bits. That is the point of using two constants: the inner and outer computations behave as though they used two independent keys, derived from one.

A key longer than the block is hashed and a shorter one zero-padded, and the run notes the consequence: a key and the same key with zeros appended give the same K0, so they give the same tags. RFC 2104 notes it, and the practical rule is to use a key of exactly the digest length.

And the length-extension forgery succeeds. Given H(secret || message) and the length of the secret, the attacker set the hash's state to the tag, continued the computation with &to=9999, and produced a tag that matches the true tag for the extended message exactly. No key. The message the server sees is amount=500&to=8817, then the padding bytes, then &to=9999, and most parsers take the last value.

HMAC is not forgeable that way, because the outer hash is applied to the inner digest, which is a fixed-length value. There is no state in the output that corresponds to an extendable message, so there is nothing to continue.

Why the nesting works, in the shape an examiner wants

The inner hash produces a fixed-length digest of the key-prefixed message. Whatever length-extension property the hash has applies to that inner computation, and the attacker never sees its output.

The outer hash is applied to a fixed-length input: B bytes of keyed pad plus the inner digest. So the outer computation is a single-block or two-block hash of a fixed size, and length extension is meaningless on it: there is no message length to extend.

And the two keyed pads are effectively two keys. So an attacker cannot use a relation found in the inner computation against the outer one.

One efficiency note worth knowing: K0 XOR ipad and K0 XOR opad are each one block long and depend only on the key, so their compression can be precomputed once and reused for every message. HMAC therefore costs the hash of the message plus about one extra block, not two full hashes.

Two rules about using it

Truncation is allowed and is bounded. FIPS 198-1 permits the output to be truncated to t bytes. A shorter tag is cheaper and weaker: an attacker's chance of guessing a tag is 1 in 2 to the power 8t. The standard requires t to be at least 4 bytes and recommends at least half the digest length.

The comparison must be constant time. A comparison that returns as soon as two bytes differ tells an attacker how many leading bytes were right. With that, a tag is recovered byte by byte, at 256 tries per byte rather than 2 to the power 256 for the whole tag. A 32-byte tag falls in about 8,192 queries instead of never. The run's last lines say so, and the library function for it exists precisely because the obvious comparison is unsafe.

Worked example: where HMAC goes in a protocol

The requirement. A college API accepts amount and to parameters and must reject any request not issued by the college's own system.

The wrong design. tag = SHA256(secret + parameters), tag sent alongside. This is the design the run forges. An attacker who has seen one legitimate request appends &to=9999 and computes a valid tag.

The second wrong design. tag = SHA256(parameters + secret). No length extension, but a collision in SHA-256 gives two parameter strings with the same tag under every key, so the day the hash falls the scheme falls with it, for all keys ever used.

The right design. tag = HMAC-SHA256(secret, canonical_parameters), where canonical_parameters is a form that cannot be parsed two ways: parameters sorted, lengths included, separators that cannot appear in a value. The canonicalisation matters as much as the HMAC, because the forgery above worked partly by making a string that two parsers read differently.

And three more things. Include a timestamp inside the authenticated data and reject stale requests, or replay is still possible. Compare the tag in constant time. And use a key of 32 bytes, exactly the digest length.

The step that carries the marks. Naming all four: HMAC, canonicalisation, a timestamp inside the coverage, and a constant-time comparison. Three of the four are not about the MAC at all, and a scheme that gets only the MAC right is still broken.

Distinctions that carry marks

The first two columns are the two naive constructions: hash the key followed by the message, and hash the message followed by the key. A table cell cannot carry the concatenation symbol inside a code span, so they are named in words.

What beginners get wrong here

Writing H(key || message) as HMAC. That is the construction HMAC exists to replace, and this chapter forges it.

Getting the pads the wrong way round. 0x36 is ipad and goes in the inner hash; 0x5C is opad and goes in the outer one.

Forgetting that a long key is hashed first. A key longer than the block is replaced by its own digest. RFC 4231's third test case checks exactly this.

Comparing tags with ==. It leaks timing and the tag falls byte by byte in a few thousand queries.

Thinking HMAC needs a collision-resistant hash. It does not, which is why HMAC-SHA-1 remains acceptable after SHA-1's collision.

Quick revision

• HMAC(K, text) = H((K0 XOR opad) || H((K0 XOR ipad) || text)), from FIPS 198-1 and RFC 2104.
• K0 is the key zero-padded to the block size, or H(K) padded if the key is longer than the block.
• ipad is 0x36 repeated, for the inner hash; opad is 0x5C, for the outer. They differ in four of eight bits, so the two derived keys differ in half their bits.
• H(key || message) is forgeable by length extension, performed in this chapter: the tag is the hash's state, so an attacker who knows the key's length extends the message and computes a valid tag without the key.
• H(message || key) is not extendable but falls to a hash collision, for every key.
• HMAC's nesting defeats both, and it has a proof: a secure fixed-length compression function gives a secure arbitrary-length MAC.
• The keyed pads depend only on the key, so their compression is precomputed: HMAC costs one hash plus about a block.
• Truncation to t bytes is allowed, at least 4 and preferably half the digest; guessing costs 1 in 2 to the power 8t.
• Compare tags in constant time. A byte-by-byte comparison recovers a 32-byte tag in about 8,192 queries.
• HMAC does not need collision resistance, which is why HMAC-SHA-1 is still acceptable.

Test yourself

1. Write the HMAC construction and define each part. HMAC(K, text) = H((K0 XOR opad) || H((K0 XOR ipad) || text)). H is a cryptographic hash function with block size B. K0 is the key padded with zeros to B bytes, or H(K) padded to B bytes if the key is longer than B. ipad is the byte 0x36 repeated B times and opad is 0x5C repeated B times.

2. Why is H(key || message) not a secure MAC? Because an iterated hash's digest is its internal chaining state. An attacker who has the tag and knows the length of the key can set the state to that tag and continue the computation with data of their choosing, producing a valid tag for the original message followed by the hash's padding and their own addition, without ever knowing the key. The chapter performs this forgery and the forged tag matches the true one exactly.

3. Why is H(message || key) also unsatisfactory? Because a collision in the hash gives two messages with the same tag under every possible key: if two messages hash identically then appending the same key to both yields identical inputs to the final compression. So a single published collision would break the scheme for all users and all keys at once.

4. What are ipad and opad, and why are there two of them? ipad is the byte 0x36 repeated to the block size and opad is 0x5C repeated likewise. Two are used so that the inner and outer hashes are keyed differently: the two bytes differ in four of their eight bits, so K0 XOR ipad and K0 XOR opad differ in about half their bits and behave as two independent keys derived from one.

5. What happens to a key longer than the hash's block size, and what subtlety follows? It is replaced by its own hash and then zero-padded to the block size. The subtlety is that zero padding means a key and the same key with trailing zero bytes appended produce the same K0, and therefore the same tags, so they are not distinct keys. The practical rule is to use a key of exactly the digest length.

6. How is HMAC made efficient? The two keyed pads, K0 XOR ipad and K0 XOR opad, are each exactly one block long and depend only on the key, so the compression of each can be computed once and reused for every message under that key. HMAC therefore costs the hash of the message plus roughly one extra block, rather than two complete hashes.

7. Why must an HMAC tag be compared in constant time? Because a comparison that stops at the first differing byte takes a time that depends on how many leading bytes matched. An attacker who can measure that recovers the tag one byte at a time, needing about 256 attempts per byte instead of searching the whole tag space, so a 32-byte tag falls in a few thousand queries. A comparison that always examines every byte removes the signal.