Length extension

The digest is the state

A server signs user=guest as md5(secret + message). You see the message and the signature. You don't see the secret. Safe? Not even close.

MD5, SHA-1, SHA-256 and SHA-512 eat their input in blocks. After the last block the digest is simply the state, written out. So pick up that state, pretend the padding was part of the message, and keep hashing. Out comes a valid signature for a longer message. The secret never shows up.

import { extendDigest, md5 } from "@agntn/hashes";

const text = (value: string) => new TextEncoder().encode(value);
const signature = md5(text("keyuser=guest")); // f7e20fd66ebbe27bcdb0fa8ef25023fb

const forged = extendDigest({
  algorithm: "md5",
  digest: signature,
  message: text("user=guest"),
  secretLength: 3,
  suffix: text("&admin=true"),
});
forged.digest.toHex(); // "cf098ea633bbf37494ef7b56cdae939b"
forged.message.length; // 72, with 51 bytes of padding in the middle

forged.message is what you send: the original, the padding, then your suffix. The server puts key in front and gets cf098ea6... too. node:crypto agrees.

What do you need to know?

The digest, the message, the suffix. And how long the secret is, not what it is.

Don't know the length? Try a range. Lengths that land in the same block give the same digest, only the padding inside the message moves:

hashes extend md5 f7e20fd66ebbe27bcdb0fa8ef25023fb --message user=guest --suffix '&admin=true' --secret-length 2 --secret-length-max 4 --json \
  | jq -r '.extensions[] | "\(.secretLength) \(.digest)"'
# 2 cf098ea633bbf37494ef7b56cdae939b
# 3 cf098ea633bbf37494ef7b56cdae939b
# 4 cf098ea633bbf37494ef7b56cdae939b

Without --json you get each length with its digest, message and padding in hex. The padding is binary, so hex is the only honest way to print it. The hashes_digest_extend tool takes the same range as secretLengthMax, up to 64 lengths per call.

Which hashes fall for it?

The ones whose digest is the whole state: SHA-256, SHA-512, SHA-1, SHA-0, MD5, MD4, RIPEMD-128, 160, 256 and 320, Whirlpool, Tiger and HAVAL-256. Tiger opens its padding with 0x01 instead of 0x80. Same trick, one different byte. Whirlpool keeps the 0x80 and writes the length into 32 bytes. Same trick, bigger field.

HAVAL-256 falls for it too, it just wants papers. Its padding carries a little ID card: two bytes before the length with the version, the pass count and the fingerprint length. The forged padding has to show the same card, so tell extendDigest which HAVAL signed the message:

const signature = "206c3be5e68bae6a479028c23a69b369bc643dc7d106260a89b4a8f4506334f2"; // haval256,4 of "k3yuser=a"

const forged = extendDigest({
  algorithm: "haval",
  parameters: { passes: 4, bits: 256 },
  digest: Uint8Array.fromHex(signature),
  message: text("user=a"),
  secretLength: 3,
  suffix: text("&admin=1"),
});
forged.digest.toHex(); // "742f315b0257b1345e7fc65dcf9fef3b963d1d3f72f19c50cec93da4676a45e0"

PHP's hash("haval256,4", ...) of the secret and the forged message agrees. hashes_digest_extend takes the same parameters, and hashes extend takes them as JSON: --parameters '{"passes":4,"bits":256}'. Forget bits and the error names it for you. HAVAL-128 to 224 are out of luck. They fold the spare words into the kept ones, and nothing unfolds that.

SHA-224, SHA-384 and SHA-512/t cut part of the state off before they print it, so there's nothing complete to resume from. SHA-3, Keccak and BLAKE aren't built that way at all. HMAC isn't either. It hashes the result once more under the key, and that outer hash is what you see. Ask for one of those and you get a list of what works:

hashes extend sha384 "$(hashes sha384 x)" --message x --suffix y --secret-length 1
# Invalid option algorithm=sha384: cannot be extended, use one of sha256, sha512, ripemd160, ripemd320, whirlpool, md5, md4, sha1, sha0, ripemd128, ripemd256, haval, tiger

So the fix for the server above is boring. Use HMAC. That's the whole point of it.