A service authenticates messages with tag = SHA-256(secret || message) and validates by recomputing. Show the attack this allows, what the attacker needs to know, and name the two constructions that stop it.

A service authenticates messages with tag = SHA-256(secret || message) and validates by recomputing. Show the attack this allows, what the attacker needs to know, and name the two constructions that stop it.

Approach: Consider what the internal state of a Merkle-Damgard hash is at the end of a message and whether the published tag reveals it.

An attacker who has one valid message and tag can forge a tag for that message extended with data of their choice, without knowing the secret. SHA-256 is a Merkle-Damgard construction that processes the input in 512-bit blocks and carries a 256-bit chaining state, and the output tag is exactly that final state. So an attacker sets the hash function's internal state to the observed tag, appends any suffix, and continues compressing, producing the correct hash of secret || message || padding || suffix. All they need is the tag, the message, and the length of the secret, which is usually a known constant or can be searched over a small range. A concrete case is a request string where appending an extra parameter overrides an earlier one, letting the attacker change an amount or a permission while the tag still verifies. The two constructions that stop it are HMAC, which is H(K xor opad || H(K xor ipad || message)) and whose outer hash of a fixed-size inner digest breaks the extension, and a sponge-based hash such as SHA-3 or a hash whose output is a truncation of a larger state, since the tag no longer reveals the full internal state. Prefixing the secret is the error; HMAC is the standard answer and should be used rather than any hand-built keyed hash.

Follow-up: Would tag = SHA-256(message || secret) fix the length extension problem, and what different weakness does it have?

Key concepts: length extension, merkle-damgard, hmac, message authentication.