Why HMAC Hashes Twice and What Length Extension Has to Do With It

The obvious way to authenticate a message with a hash function is to put the key in front: $\mathrm{Hash}(k ,|, M)$. It is also broken for every hash function built on the Merkle-Damgard iteration, which includes MD5, SHA-1, and the entire SHA-2 family. The attack needs no cryptanalysis of the compression function, only the ability to read a digest. HMAC exists because of that attack, and its shape is a direct response to it.

Length extension, mechanically

A Merkle-Damgard hash processes the message in fixed-size blocks and carries an internal state of one block size between them. SHA-256 starts from a fixed initial vector, absorbs each 512-bit block by running the compression function with the current chaining value, and finishes by appending a padding that encodes the message length and processing one or two final blocks. The output is the final chaining value.

The important property is that the digest is the complete internal state at the end. Given a digest and the length of the hashed message, an attacker can restart the iteration from that digest, append arbitrary extra bytes, and compute the digest of the extended message without knowing the original bytes. The only obstacle is the padding: the original message was followed by a padding block that encodes its bit length, and that padding block is still part of the hashed data. So the attacker’s “extended message” is $M ,|, \mathrm{pad}(M) ,|, X$, and its digest is computable.

Now apply that to $\mathrm{Hash}(k ,|, M)$ as a MAC. The attacker has seen a valid tag $t$ for some message $M$ it did not choose, and it knows or can guess the key length. It computes $t’ = \mathrm{Hash}$ continued from state $t$ over $X$, and now has a valid tag for $M’ = M ,|, \mathrm{pad}(k|M) ,|, X$. The appended bytes include padding that will look like garbage in a protocol, but plenty of protocols tolerate trailing bytes, ignore unknown fields, or parse the message as a structured document where trailing bytes are harmless. Once one such message is accepted, the attacker has an existential forgery and, with the right message format, a practical one.

The construction that fixes this without modifying the hash is to key both ends. HMAC computes

$$\mathrm{HMAC}(k, M) = H\big((k \oplus \mathrm{opad}) ,|, H((k \oplus \mathrm{ipad}) ,|, M)\big)$$

with $\mathrm{ipad}$ being the byte 0x36 repeated to the block size and $\mathrm{opad}$ the byte 0x5c repeated to the block size. For SHA-256 the block size is 64 bytes, so each pad is 64 bytes and the inner hash produces 32 bytes.

Why the outer hash stops the attack

The attacker who sees the tag sees the output of the outer hash, not the inner one. The inner digest is a secret, because producing it requires $k \oplus \mathrm{ipad}$. Length extension works by continuing from a known chaining value; the attacker has no known chaining value at the point where the message ends, because the value there is the inner digest and it is not transmitted.

The outer hash also compresses the inner result from 32 bytes down to a fixed 32-byte tag, and that second compression is what makes the construction indifferent to the hash’s internal structure. The security argument does not require the compression function to resist anything beyond collision resistance in a specific sense. The proof treats the compression function as a black box: if the compression function is a pseudorandom function under a secret-prefix key, then HMAC is a secure MAC. This is why HMAC-SHA-256 remains sound even though SHA-256’s Merkle-Damgard structure is exactly what made the naive construction fail.

The double hashing also decouples key length from block size. A key longer than the block size is hashed first and then padded to the block size; a shorter key is zero-padded to the block size. Both cases end with a 64-byte block for SHA-256, so the number of compression calls is fixed regardless of key length, and there is no key length that produces a degenerate state.

The pads are not decoration

The two distinct pad bytes serve two purposes, and both are structural.

First, they ensure that the inner and outer hashes start from different chaining values even for an empty message, so the two invocations cannot share a compression result. If the pads were identical, the outer hash’s first block and the inner hash’s first block would be the same function of the key, and the construction would lose the separation between the two stages.

Second, the pad value keeps the key out of the message path in a specific way. The inner hash is $H((k \oplus \mathrm{ipad}) ,|, M)$, and the value $k \oplus \mathrm{ipad}$ is a full block. Since the pad byte is fixed and public, the keyed block is a bijective transform of the key, and the message begins at a block boundary. This matters for implementations that precompute the state after absorbing the keyed block: the first 64-byte block of the inner hash depends only on the key, so it can be computed once per key and reused for every message. A server that verifies many short messages under one key saves one compression call per verification, which is a measurable fraction of the cost for short messages.

The precomputation is safe because the keyed block is exactly one block. If the key were allowed to span blocks, the precomputable prefix would depend on where the key ended, and the reuse would be more complex and easier to get wrong. RFC 2104 fixes the key to the block size for this reason, and the hashing of oversized keys makes the rule total.

What HMAC does not give

HMAC is a MAC, so it inherits the verification capability described in the MAC and signature split: anyone who can verify can also forge. It is also a single primitive over a whole message, not a way to authenticate a stream of records. Tagging each record independently allows reordering and truncation unless the record index is inside the tagged data; tagging the whole transcript requires buffering it. Protocols that need incremental verification either bind a sequence number into each record’s tagged bytes or use a tree construction over blocks.

Truncation is permitted and specified. HMAC output can be cut to any length, and a 128-bit tag is a common choice, but the security level drops to the tag length in bits against online guessing. A 64-bit tag leaves a one-in-$2^{64}$ chance per forgery attempt, which is out of reach for a single verifier but not for an attacker who can submit guesses at volume to a fast endpoint. The truncation rule is that the leftmost bytes are taken, so implementations that compare the wrong end of the digest are broken in a way that passes casual testing.

Key reuse across protocols is a subtler failure. HMAC is a PRF-like construction, and using the same key for two different protocols is generally acceptable only if the protocol inputs are disjoint or the key is derived per use. A single key used both to authenticate request bodies and to derive session identifiers gives an attacker a way to relate the two outputs. The fix is a key derivation step, not a change to HMAC.

There is also the question of what a valid tag proves about a message that has been parsed. HMAC authenticates bytes. If a receiver authenticates a serialized form and then parses it into a structure, and the parser accepts multiple encodings of the same structure, the authentication covers one encoding while the application acts on the semantic content of another. The mismatch is the same class of error that makes signature verification and parsing need to agree, and it is why protocols that sign structured data first canonicalise it. HMAC’s contribution is narrower: it binds a secret to a byte string, and it does so without the length-extension hole that the naive key-prefix construction leaves open. The next construction in this cluster, CBC-MAC and CMAC, solves the same problem from a block cipher instead of a hash, with a different set of edge cases.