Length extension attack

In cryptography and computer security, length extension attacks are a type of attack on certain types of hashes which allow inclusion of extra information.

This attack can be done on hashes with construction H(key ∥ message) when the message is known and the length of the secret is known. Algorithms like MD5 and SHA-1 that are based on the Merkle–Damgård construction are susceptible to this kind of attack. Note that since HMAC doesn't use the construction H(key ∥ message), HMAC hashes using susceptible algorithms are not susceptible to length extension attacks.

Detailed Explanation

A simple length extension attack may be illustrated as follows:

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

In this case the key length is 14 bytes, and the attack will switch the waffle from "eggo" to "liege". It does this by taking advantage of a flexibility in the message format: duplicate content in the query string tends to give preference to the latter value. This flexibility does not indicate an exploit in the message format, because the message format was never designed to be cryptographically secure in the first place, without the signature algorithm to help it.

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

In order to sign this new message, the attacker would need to know the key the message was signed with. In a length extension attack, however, the attacker takes advantage of not needing to know the key, per se, but more generally the state of the hash function at some point during the hash. If he or she can get the internal state of the hash, then they simply have to continue the hash from that point to get a signed message. In the Merkle–Damgård construction, the final digest is the internal state. However, he can't sign this message as is. Most hashing algorithms call for the message to be padded to some number of bytes before the final digest is produced. The content of this padding is always specified by the hash. The attacker must include all of these padding bits in his message before the internal states of his message and the original will line up. Thus, the attacker constructs a slightly different message using these padding rules:

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x02(&waffle=liege

This message includes all of the padding that was appended to the original message inside of the hash function before his payload(in this case, a 0x80 followed by a number of 0x00s and a message length appended at the end). The attacker knows that the state behind the hashed key/message pair for the original message is identical to that of new message up to the final "&." The attacker also knows the hash digest at this point, which means they know the internal state of the hash at that point. It is then trivial to then initialize a hashing algorithm at that point, input the last few characters, and generate a new digest which can sign his new message without the original key.

New Signature: 0e41270260895979317fff3898ab85668953aaa2

This attack has mostly been used for forging signed data, but it does have other possibilities.

Implementations

There are not many known tools for implementing this attack. One tool which uses OpenSSL to implement this attack for various hash algorithms is HashPump. This tool supports the Length Extension Attack for MD5, SHA1, SHA256 and SHA512. In development of this tool, SHA224 and SHA384 were found not vulnerable to this attack due to their reduced output of their state variables, instead of all their state variables.