0
$\begingroup$

I was trying to solve a cryptography challenge and the problem was about "hash length key extension". After some reading in different topics, I don't know why I still didn't solve the challenge.

I read this page. From what I understood, we have the MAC which is $\mathrm{md5}(\mathrm{secret}||\mathrm{data})$. We want to append some string at the end, so we will have the new hash $\mathrm{md5}(\mathrm{secret}||\mathrm{data}||\mathrm{append})$.

When I run $\mathrm{md5}(\mathtt{secretdata})$, I get 6036708eba0d11f6ef52ad44e8b74d5b like in the tutorial. But when I compute $\mathrm{md5}(\mathtt{secretdataappend})$, I get 81efe001a23d41765fa7323d22861558. However, the tutorial says it should be 6ee582a1669ce442f3719c47430dadee.

In other tutorials it is the same hash value, so I am probably doing something wrong. My instinct is that I have to guess the value of $\mathrm{secret}||\mathrm{data}||\mathrm{append}$, without knowing $\mathrm{secret}$. I only know the length of $\mathrm{secret}$.

Why do I get the wrong hash when trying to perform this attack?

$\endgroup$
  • 2
    $\begingroup$ You have to take the padding and length encoding into consideration, I guess. $\endgroup$ – Maarten - reinstate Monica Sep 24 '17 at 22:49
  • 3
    $\begingroup$ MD5 always adds padding at the end of what is passed to it. So, the length extension turns out to be "secret"+"data"+"padding"+"append". So you have to calculate what the padding would be for just "secret"+"data". $\endgroup$ – mikeazo Sep 25 '17 at 0:05
  • $\begingroup$ i know about padding, but in the server side they are just doing md5(secret+data+append) the padding it's for us when we want to forge something similar ? $\endgroup$ – Nazime Lakehal Sep 25 '17 at 6:05
  • 1
    $\begingroup$ What's appended can't be "append"; it is "padding"||"append", where "padding" is the padding for "secret"||"data"; that "padding" depends on the length of "secret"||"data" (but nothing else). $\endgroup$ – fgrieu Sep 25 '17 at 12:11
  • $\begingroup$ i still don't get the point .... in the server side, what hash is running? $\endgroup$ – Nazime Lakehal Sep 25 '17 at 14:48
1
$\begingroup$

OK, so the general idea of MD5 and SHA-1 and SHA-2 is that they process the data in blocks. For the last block the algorithms first append a padding to the plaintext data and the encoding of the length to create the final block. If the padding and length do not fit then an additional block is used.

Now the problem with these algorithms is that the intermediate state, that is: the state after a block encrypt is directly used as the output for the final block. So if you have three blocks then the value of the last block operation is used as output. So if you have a message that consists of the first block and then two blocks that mimic the last part of the message, padding and length indication then the intermediate value between block 3 and block 4 will be identical to the output of the previous calculation. After that you can add any data and keep processing as usual.

Let's put this in a scheme, ignoring the secret for now:

| message_b1 | message_b2 | message_p3 | padding_p3 | length__p3 |
| process_b1 | process_b2 |              process_p3              |
| h_state_b1 | h_state_b2 |              h_state_p3              |

can be extended using

| message_b1 | message_b2 | message_b3 | message_p4 | padding_p4 | length__p4 |
| process_b1 | process_b2 | process_p3 |              process_p4              | 
| h_state_b1 | h_state_b2 | h_state_p3'|              h_state_p4              |

For this to happen message_b3 must of course consist of message_p3 | padding_p3 | length__p3 otherwise h_state_p3' will be different from h_state_h3 and therefore h_state_p4 the final output will be invalid.

If the secret is (part of) message_b1 then the verifier will automatically prefix the secret for you. So you just need to provide the message itself, but it must consist of the special format.


SHA-3 post processes the hash, so the length extension is not possible anymore as the final hash cannot be an intermediate value of another hash calculation.

$\endgroup$
  • $\begingroup$ The answer would be clearer with A) message_b3 aligned below message_p3 | padding_p3 | length__p3; and B) h_state_xxon the right of message_xx and process_xx, rather than aligned, since that's the state at the end of the process. To make enough room, I suggest to have a single occurrence of message, process and h_state on the left $\endgroup$ – fgrieu Sep 26 '17 at 10:10
  • $\begingroup$ @fgrieu I'll try and amend the answer whenever I find the time (and that's a big if), if you want to edit it please go ahead. $\endgroup$ – Maarten - reinstate Monica Sep 27 '17 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.