Understanding the length extension attack

Question

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.

Let's assume that for a message $m$, a secret $s$ is prepended 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 $\textrm{H}(s \mathbin\| m \mathbin\| \textrm{padding})$.

Now SHA-1 internally uses 5 registers — it takes in a 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 \mathbin\ m \mathbin\ \textrm{padding})$ was processed. Let's also assume that the attacker knows $\textrm{len}(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?

Answer 1

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 actual 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, see 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).

Answer 2

The key to understanding hash extension attacks is to understand that the hash output isn't just the output of the machine generating the hash, it's also the state of the machine up till that point. In other words, just the hash output alone contains enough information for you to keep going and append more content to the hashed input.

The catch is that since hashes work on fixed-size blocks, if the data size doesn't line up properly along one of these block boundaries, it will be padded with zeros until it does. So we have to account for that in our attack. (Yes, SHA-1 has additional padding rules, which we'll ignore for simplicity)

An example

Let's say your super-secure authentication protocol is to take a given message, prepend a password to it, and send the hashed result as the "signature". I can compute the hash of your string plus an additional string just by knowing your hash output.

So lets say I have your "signature" for the string count=1&price=100.2, but I want to change the price to 1. I know your parsing algorithm replaces earlier values with later ones and it doesn't choke on embedded nulls. So theoretically I can compute the hash for my desired string, count=1&price=100.2&price=1.0.

But I can't just append my string to yours and expect it to work. I have to account for padding. We'll assume a block size of 10 for simplicity. (nb: "•" = null)

   123456789|123456789|123456789|123456789|             <- ruler
A: [mysecurepassword]count=1&price=100.2                
B: [mysecurepassword]count=1&price=100.2•••

Ostensibly I have the hash for string A, but what I really have is the hash for string B -- with the three nulls appended at the end for padding.

So instead of sending the string count=1&price=100.2&price=1, I would have to send the string count=1&price=100.2•••&price=1.0.

To generate my signature, I just initialize the hash engine with the signature you gave me, add &price=1.0, and output the result.

Of course, the rules of SHA-1 are somewhat different than my pretend 10-byte hash, but the principle still applies, it's just a matter of getting the bytes to line up.