1
$\begingroup$

Here is my situation. I'm working with an application for which uses hashing to authenticate data.

I have a string, which is hashed. It is, like in a hash length extension attack, H(key:known_value)

This hash is incremented by a nonce upon repeated attempts. On the first attempt there is no nonce, further attempts are H(key:known_value:nonce)

I believe I misunderstood a hash length extension attack (and was up for 9 hours last night learning that) in that by knowing the hash value, and the length of that entire hashed string, that I could add a nonce and get the same hash?

Not sure if I'm making sense, so let me demonstrate with example values:

hash("IamSecret:YouKnowMe") = 389fiu3vb93h39v (yes, not a real hash) hash("IamSecret:YouKnowMe:1") = f5d725d78223hjd2d2 (also made up)

I thought that a hash length extension would allow me to take the first hash, "389fiu3vb93h39v" and knowledge of the length of the secret (9) and the known data (":YouKnowMe") and append my data (":1") and come up with "f5d725d78223hjd2d2"?

But after 9 hours of messing with it, it seems thats NOT possible? What a hash length extension attack would allow me to do is to take my known values above, and come up with a string (something like :YouKnowMe\x80\x00\x00.......\x00:1) and figure out what the hash would be **IF I DID **hash("IamSecret:YouKnowMe\x80\x00\x00.......\x00:1")?

Is my understanding correct?

And if so, is there ANY way to do what my original issue was? I know the hash algorithm used, I know the hashed value of secret:known, I know 'known', I know the length of secret. Can I ADD DATA to 'known' and get the same hash that the client app would get if it just hashed secret:known:added_data?

I'm running on 4 hours sleep, sorry if my question is confusing :)

$\endgroup$
  • $\begingroup$ Yes, you need to include the padding. This is often not as big a hurdle as you might think. That said, just use an HMAC which is designed for this sort of thing. $\endgroup$ – Stephen Touset Apr 3 '15 at 17:26
  • $\begingroup$ I don't understand your comment... I'm sure you're answering me but I'm not getting it. As for using an HMAC designed for it - I'm not in control of that part of the project, I've already suggested it, and been told "it's already done". So, out of the question. I'm trying to determine if this is vulnerable or not as is. $\endgroup$ – InfernusDoleo Apr 3 '15 at 17:50
  • $\begingroup$ Ok, thats a start - how does getting it to have the right length help? What would that length be? Using a very large nonce number it is possible to extend that to a longer length. (Since the nonce is part of "YouKnowMe" when all is said and done) $\endgroup$ – InfernusDoleo Apr 3 '15 at 19:12
  • $\begingroup$ I was about to comment and say I see now that its not possible, after messing with a PHP sha1 generation library where I could inject echo's and see exactly how the sha1 hash is built (and how it's not possible to circumvent the padding?) yet Ricky's comment above says maybe I'm wrong? From what I saw if the length is <= 55 there is 1 chunk with 1 padding byte and the 8 bytes for the length. >= 56 and <= 64 there is a second chunk that is all padding (56 to 64 bytes worth + size block) and the extra data is in the first chunk. It cant ever sit on a boundary and just have a character added? $\endgroup$ – InfernusDoleo Apr 3 '15 at 19:13
  • $\begingroup$ Oh, yeah, it's more difficult than I thought. $\:$ You would probably need the padding anyway. $\:$ Does the application use unicode or just ascii or something else? $\:$ Can YouKnowMe contain the character Ç? $\:$ What about null characters? $\;\;\;\;$ $\endgroup$ – user991 Apr 3 '15 at 19:32
1
$\begingroup$

Length extension attacks exploit the pattern that it's possible to use H(k || m1) to compute H(k || m1 || m2) without knowing the value of k, but it is restricted to messages m2 of a particular form. Which is, they have to begin with the padding p that the hash algorithm applies to expand to a multiple of the block size. This is critical, because it's what allows the attack to infer the internal state of the hash when it starts to process the non-padding part of m2. Without the padding, the hash algorithm never gets to the state represented by the original output.

In your example, "IamSecret:YouKnowMe" and "IamSecret:YouKnowMe:1" don't follow that pattern - the second message does not have the padding before the new data. Therefore you can't know the internal state when it starts consuming the nonce, and so you can't predict the output.

The authentication protocol in your application is not strong, you probably want to use HMAC or similar. It's not clear to me if it's vulnerable to a length-extension attack; I don't quite understand which of the inputs are under control of the attacker (presumably known_value) and what the hash is used for.

See also Understanding the length extension attack for an accessible write-up.

$\endgroup$
  • $\begingroup$ A good portion of KnownValue is user changeable (though a portion is not and is tied to your login credentials), as well as the nonce. But from all I've read, a length extension attack against this is impossible. Thanks for the input. $\endgroup$ – InfernusDoleo Apr 3 '15 at 23:26

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.