SHA-1 length extension attack example in python

This is nothing special and was done a million times before, but not by me :). So what is the "length extension attack" that I'm talking about. Easy, this just means that you can add anything to some popular hashes like MD5, SHA-1 and SHA-2 (with exception of SHA-224 and SHA-384, they truncate the output), almost any hash based on Merkle–Damgård construction. The problem is in the design of the hash. Basically the hash/digest that you receive at the end of the computation is exactly the internal state of the hashing function at the end of the operation. This is not a very bad thing if you know about it and you will uses hashes correctly. 

I've implemented this attack for SHA-1 only but it is quite trivial to do it for other functions based on this example.

First let generate a hash of some message ("secret" in this case):

> ./sha1.py secret
msg: secret
e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4

Now knowing only the hash and that the length of the hashed message was 6 bytes I can produce a hash of the original message (that is unknown to me) and some added data (in this case " that can be shared"):

> ./sha1_len_ext_attack.py e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4 6 " that can be shared"
msg: 8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003020746861742063616e20626520736861726564
e73b327069f3658ab8f60d9a21a3961e5d371b8d

In green you see padding of the original hash (we need the length of the message for this) and in pink our added message. In orange is the hash that we were looking for.

Now lets verify that we got the correct output, normally you can't do this because you don't know the original message. First we need to get hex values of the characters in the word "secret":

> printf secret | xxd
0000000: 7365 6372 6574                           secret

Now lets put together the above value and the green and pink values from the sha1_len_ext_attack.py command. The option -x to sha1.py allows for providing hex values:

> ./sha1.py -x 7365637265748000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003020746861742063616e20626520736861726564
msg: secret?0 that can be shared
e73b327069f3658ab8f60d9a21a3961e5d371b8d

As you can see the orange hashes match. The message adding is not perfect, there is some garbage between the original and the new added message (one \x80 byte, some null bytes and a few bytes that represent the length of the original message in bits) but this sometimes is not a problem.

To implement this attack you first need to implement the hash function you are attacking (or take somebody else implementation). I did mine based on the method 1 from RFC 3174. It was more fun this way. In the second step you will need to change the initial internal state of the function (the h(0)-h(n) values) based on the original hash that you've got, then calculate the rest of the hash normally and you are done.

In real life this can cause issues like for example in the Flick's API case.

No comments:

Post a Comment