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).