Secret Life of Hashes Divulged – Length Extension Attack Explained

Sounds interesting!! Doesn’t it? Well, it sounds to me and so I want it penned down. Let’s see how this goes.

If you feel you’ve nailed it after reading through the entire blog, then I can consider diving deep into the blogging world. It’s my second post within 24 hours and I already feel I was born for it. Let’s not bore you guys with my shit, and learn something about a new form of cryptographic attack called the Hash Length Extension Attack, instead.

It all started when I was at Goa in India (an exotic place to be in for sure) a year ago for the null conference. I know, when I say Goa, the only thought that comes to your mind is the beaches – pristine blue with golden sand and perhaps a bottle of Goa’s favorite chilled beer “Kings”.  The thought of not attending the conference crossed my mind, but then my Boss gave me an intensive look and there I was, (‘Coz my employer paid for the trip). I already knew that I was going to hate it but things changed at the blink of an eye the moment I entered the conference. One of the trainings at this conference was about an attack called a Hash Length Extension Attack. This was the first time I've heard it and it kept me on my toes for the entire session.

Half way down the session, I realized that the attack is not only super awesomely cool, but also conceptually easy to understand and perform. To make your job much easier, there are various modules available over the internet such as HashPump and hash_extender. There’s another module which I like personally, is the one from Stephen Bradshaw called hlextend. This module can be found at GitHub.

As per Wikipedia, the basic definition of this attack goes by:

“In cryptography and computer security, a length extension attack is a type of attack where an attacker can use Hash (message1) and the length of message1 to calculate Hash (message1 ∥ message2). This attack can be used to sign a message when a Merkle–Damgard based hash is misused as a message authentication code, allowing for inclusion of extra information.

This attack can be done on hashes with construction H (secret ∥ message) when message and the length of secret is known. Algorithms like MD5, SHA-1, and SHA-256 that are based on the Merkle–Damgard construction are susceptible to this kind of attack.”

Before we begin, a quick go-through on how Hashing works:

·         Hash functions operate on fixed block sizes

·         Input data is split into fix-sized parts equal to the block size

·         If any of these parts is smaller than block size (mostly the last part), the missing bytes are padded

ü       PKCS7

ü       Bit Padding

·         The hash value represents the internal state of the hash function

ü       You can simply continue adding data + padding and hash again using the internal state

The Attack:

Let’s assume a web application which uses a known hash generated from an unknown secret value tied to a user entered input. The basic purpose of doing so is to check the integrity of the entered value to avoid any form of manipulation. For example, let’s assume the desired SHA1 hash value generated with an unknown secret length for a valid parameter value ‘student’ is ‘204036A1EF6E7360E536300EA78C6AEB4A9333DD’. So, if we try to access the below mentioned URL, we get all the details of a student.

Cool! I guess that’s what the application was supposed to do. It’s a valid request after all. Let’s see what happens if we try to play with the ‘param’ value. Let’s try to access the ‘/etc/passwd/’ file using path traversal. What do you think will happen?

Oops!! File not found.

Of course! And did you think it was that easy? So what do you think happened? 

Well, the requested file did not match the above SHA1 hash value since it belonged to ‘student’. In order to perform this attack successfully, we would need a valid SHA1 hash value for the ‘/../../../../etc/passwd’ file, combined with an unknown length of the secret value.

And how do you think we get that? Well, the first thing we need to do is to guess the length of the secret value. Without which it won’t be possible to generate a valid hash. In such cases, brute forcing the value by trying multiple different lengths can sometimes be possible, depending on the application.

Let’s first see what all data we already have that might come in handy:

Known Data: student

Hash of known Data: 204036A1EF6E7360E536300EA78C6AEB4A9333DD

Extended Data: /../../../../etc/passwd

Hash of Extended Data: <unknown>

Length of secret: <unknown>

Great!!

If I have to explain it in simple words, the application creates a sha1 hash value of '204036A1EF6E7360E536300EA78C6AEB4A9333DD', by concatenating an unknown secret of length ‘X’ and known data of 'student'. You wish to append the text '/../../../../etc/passwd' after 'student' and also provide a valid hash back to the application that it will produce when it concatenates your provided value (which will include the string 'student' followed by '/../../../../etc/passwd') with its secret.

I hope by now you already know what our ultimate goal is. Ready for some action!!! Here we go……

The goal is to read the /etc/passwd file, via bypassing the hash integrity check on the param parameter. This is what the script below will automate using the hlextend module to generate the extended hash values.

And the output:

Once we access the above displayed URL:

You may notice that the new value produced above contains a lot of additional data (in this case, a 0x80 followed by a number of 0x00s and a message length, which is the length of the key plus the original message, appended at the end) between the 'student' and the '/../../../../etc/passwd' - this is hex encoded padding data used by the hash algorithm that needs to be integrated into the hashed data in order for the attack to work - So strictly speaking you can't specify the EXACT value to append, only what comes after the padding, but under the right circumstances you can make the application ignore this extra padding.

So in short, if the hash algorithm used is vulnerable, it is possible to achieve this without knowing the secret value as long as you know (or can guess, perhaps by brute force) the length of that secret value. This is called a hash length extension attack.

Happy Hacking my Friends!!!