Understanding the length extension attack I have been trying to understand exactly how a length extension attack works on SHA-1. I'll detail below what I've understood so far, so that I can convey my understanding of the same and hopefully get advice on where I'm going wrong.

Lets assume that for a message $m$, a secret $s$ is appended to it and the SHA-1 hash is calculated. If $\textrm{len}(m) + \textrm{len}(s)$ is not a multiple of the block size, a certain amount of padding is added to it to make it a multiple, and the hash is generated using what is essentially $s || m || \textrm{padding}$.

Now SHA-1 internally uses 5 registers — it takes in an block, generates new register values, turns the crank, takes in another block, generates new register values, turns the crank ... and so on till the end. When all blocks are exhausted, the register values are concatenated and spit out.

Assume that an attacker knows a certain value of $m$, for which he also knows the hashed key. In such a case, he knows the state of the 5 registers when $(s || m || \textrm{padding}$ was processed. Lets also assume that the attacker knows the length of $s$, so that he can predict how much padding was added.

Here is where I get confused. From what I've read so far, the attack involves taking the known hash, adding a certain amount of padding and then the value that we want. However, isn't the padding already used up in creating the hash? Why are we using padding in our attack?
SHA-1 processes data by 512-bit blocks (64 bytes). For a given input message m, it first appends some bits (at least 65, at most 576) so that the total length is a multiple of 512. Let's call p the added bits (that's the padding). The padding bits depend only on the length of m (these bits include an encoding of that length, but they do not depend on the value of the bits).

The padded message m||p is then split into successive 512-bit blocks, which are processed one after the other. SHA-1 uses an internal compression function (that's the traditional term); it also has a running state consisting of five 32-bit words. The compression function takes as input two values of 160 and 512 bits, respectively, and outputs 160 bits. The processing goes like this:


The running state is initialized to a fixed, conventional value (which is given in the SHA-1 specification).
For each input block, the compression function is evaluated, with as input the current running state, and the input block; the output of the function is the new running state.
The running state after processing the last block is the hash output.


So now, the length-extension attack. Suppose that you give me a hash value h, computed over a message m that is unknown to me. I know the length of m, but not its contents. Since I know the length of m, I can easily compute the padding p that you used. Then I imagine a message m', which begins with m||p; that is, m' = m||p||z where z is a sequence of bits that I can choose arbitrarily. I will now proceed to computing the SHA-1 hash of m', even though I do not know part of it (it begins with m, which I do not know).

When SHA-1 is computed over m', the latter is first padded with p', which depends on the length of m' (which I know). The resulting stream is m||p||z||p'. Then, the 512-bit blocks are processed one by one. I cannot do it for the first blocks, since I do not know m. However, I can imagine myself doing it. At some point, I would reach precisely the end of the p string (since the length of m||p is a multiple of 512). What would be the value of the running state at that point ? Well, that's exactly the hash value h that you gave me ! Therefore, I can stop imagining; I can start my SHA-1 computation of SHA-1(m') right at that point, at the beginning of z, using your hash value h as value for the running state.

That's the core of it. I can use SHA-1(m) to compute SHA-1(m'), a message which begins with the contents of m, and I can do that without knowing m. This property of SHA-1 (which applies to other Merkle-Damgård hash functions such as MD5 or SHA-256) is not in contradiction with the usual hash function security features (resistance to collisions, preimages and second preimages), but it shows that SHA-1 is not a random oracle.

What good can it do to the attacker ? Well, consider the following (flawed) construction for a Message Authentication Code: for a given key k and data to protect d, compute SHA-1(k||d) as the MAC value. This scheme breaks in the presence of the length-extension attack: if I, as an attacker, sees a MAC for a message d, then I can compute the MAC for a message d' which extends d -- and I can do that without knowing k||d (so, in particular, without knowing the key). This allows me to forge messages with a valid MAC.

The length-extension attack is the reason why, when building a MAC out of a hash function, we need something a bit more convoluted, namely HMAC (which is safe against it).