Hash extension attack

We had Filippo Valsorda hold a small presentation at Hacker School today. The topic has how to exploit a hash extension vulnerability.

Problem lies in a combination of how hash-functions work, and unsafe ways of transmitting an API-secret in a request. The example-case was VIMEO’s old API that had this vulnerability some years ago (nowdays the vulnerability is fixed).

About MD5-hashes

MD5 hashes can’t be reversed, it’s a one-way functions.

This means checking equality a server checks hashes a string and compares it with the received hashed string. The actual passwords are never compared, just the hashes.For ex. a naive hashed password check would mean taking a password from the database and comparing it with the hashed password from client.

MD5 hashses are nearly unique - accidental collisions are extremely rare, but a collision attack is possible. It’s an iterative hash function, which means hashes are created by combining 512-bit (=64 byte) chunks of the input the the hash seed (which is predefined in MD5 spec). The hash is created only based on the input, so the next seed is formed from the created hash etc. This means the hash has to be extensible.

The vulnerability

The extensibility is built so, that there is no secret component. This means if someone captures the hash, they can extend it. This is important.

In this case, the hashed signature string was created by concatenating secret and key-value pairs alphabetically, md5-hashing that string, and adding it as api_sig value to the request. So (in this request) naive pseudocode representation of the request could be:

1
2
3

method: vimeo.test.login
api_key: e1df59512d6e136e5ba0936e8ac273cb
api_sig: hash_md5(api_secret + "api_key" + api_key + "method" + method)

So the hash would be created from string

1

sec12345api_keye1df59512d6e136e5ba0936e8ac273cbmethodvimeo.test.login

This had two design flaws: - The secret was prepended to the string that was hashed - All the other components (except the secret) is passed in plaintext in the request

If the attacker captures a request (eg. by doing a man-in-the-middle-attack), changes the content, extends the signature hash to match the new request content, she can successfully pretend to be the original user and run any command she wishes (presuming it’s allowed for the original user).

Example of the forged request:

1
2
3
4
5
6

a: api_keye1df59512d6e136e5ba0936e8ac273cbmethodvimeo.test.login\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\xe8\x02\x00\x00\x00\x00\x00\x00
video_id: 1337
favorite: 1
method: vimeo.videos.setFavorite
api_key: e1df59512d6e136e5ba0936e8ac273cb
api_sig: caf3d8384c2fbf2917c2b78dcf8ac588

api_sig is formed by hashing the whole new request key-value pairs in alphabetical order. An important part is the a-attribute, which contains the old request + padding required by MD5, which can be considered just an implementation detail. The main idea is that the new signature can be constructed from the old request and new added key-value pairs, which may be completely different from the original ones.

Further reading

A more complete article about hash-extension attacks https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks

A very thorough article about why and how to use salts & hashes when storing passwords: http://www.codeproject.com/Articles/704865/Salted-Password-Hashing-Doing-it-Right