4 ms·

I'm just curious: the obvious response to the first problem (message extension attack) is to include the message length in the message. If this wouldn't work, c

by wzdd 13y ago

I'm just curious: the obvious response to the first problem (message extension attack) is to include the message length in the message. If this wouldn't work, could an expert please tell me why? Edit: To be specific, I was thinking of a Pascal-style length-at-start arrangement. It's clear that if you put the length at the end you may be vulnerable to exactly the same attack!

bazzargh 13y ago
I'm not an expert, but I can see a problem with schemes along those lines. MD5 (and similar) extension attacks also take advantage of the padding added after the thing you want to hash; so eg Secret: secret Message: foo&bar Let's include the length and hash 'secretfoo&bar13' What you actually hash is 'secretfoo&bar130x80...padding...0x20'. What the attacker sees as the 'known hash' includes this padding. When you perform an extension attack, the attack message would look like: secretfoo&bar130x80...padding...0x02&evil . At this point you're adding on the length and hashing it, so what you compare with is 'secretfoo&bar130x80...padding...0x02&evil93' ... but the attacker can precompute that hash just as easily as the one with just 'evil' appended. You could argue that your hashes would be constructed a bit differently (eg make messages that appear to have internal padding illegal; still vulnerable, btw), but the point is - you're still tinkering with the same basic structure, and are likely to make more mistakes. You're better off switching to HMAC for this application.
- deleted 13y ago
  [deleted]
jdbernard 13y ago
The attacker just needs to include the updated length, which he can likely calculate since the shared secret is probably the same length for all accounts-even if it is not he only needs it for this request--and he knows the length of the parameters and their values. It would take some guesswork and trial and error to nail it down, and the attacker would have to guess that the length was included in the first place. Assuming he has plenty of time and processing power it is not infeasible. There are a lot of fairly easy things you could add to make it more difficult to attack.
- deleted 13y ago
  [deleted]
  - tptacek 13y ago
    The attacker doesn't "update" the length. The attacker appends data to the message, which has the effect of turning the previously stamped message length into just another bunch of bits in the middle of the message, and then includes their own message length at the end. The final message must accurately represent the length of the original message including the shared secret, so there's trial and error involved, but it's just trials of "possible length of the shared secret". Again, this works on MD4, MD5, SHA1, and all the SHA2's. You shouldn't have deleted your comment. You're not expected to know this stuff. Very few people, relative to the whole industry, or even relative to the number of programmers who end up trying to build crypto, actually do know how a length extension attack works.
    - wzdd 13y ago
      Yes, sorry for deleting a comment when there was a reply! For posterity, it was something like: "it seems like you would need to break MD5 in order to do this, because you'd have to update the length."
tptacek 13y ago
MD4, MD5, SHA1, and all the SHA2 variants use a structure called Merkle Damgard, which does include the message size. Most are vulnerable to length extension attacks. SHA3 (Ketchup) is not vulnerable to length extension attacks, because resistance to length extension was a design criteria for the SHA3 contest. Edit: Doh, SHA2-224 and SHA2-384 are truncated and aren't vulnerable
- wzdd 13y ago
  Thanks, I looked up Merkle Damgard now understand the comments about padding and how they would affect things. But I was specifically thinking of the following scheme: Message: [length][key-value pairs] Hash: MD5 (shared secret, message) Assuming that the rule is: the length is at the start of the message, and only "length" bytes of the message are used after the hash check passes. It seems that if you have found a hash collision, Merkle Damgard lets you find more collisions easily. But the exploit in the article doesn't require a hash collision. If you haven't found a hash collision, would the above scheme be vulnerable to length extension?
  - tptacek 13y ago
    The attack has nothing to do with hash collisions; it has to do with the fact that the MD-structured hashes spit out their entire state at the end of the operation, which means an attacker can simply reformat the hash back into the hash core's state and continue hashing with it.
    - wzdd 13y ago
      I didn't think so, but I mentioned it because the Wikipedia article on Merkle-Damgård hashes (http://en.wikipedia.org/wiki/Merkle–Damgård_construction http://en.wikipedia.org/wiki/Merkle–Damgård_construction) talks about length extension attacks only in the context of hash collisions: "Length extension — once an attacker has one collision, he can find more very cheaply."
      - tptacek 13y ago

by wzdd 13y ago

bazzargh 13y ago

I'm not an expert, but I can see a problem with schemes along those lines. MD5 (and similar) extension attacks also take advantage of the padding added after the thing you want to hash; so eg Secret: secret Message: foo&bar Let's include the length and hash 'secretfoo&bar13' What you actually hash is 'secretfoo&bar130x80...padding...0x20'. What the attacker sees as the 'known hash' includes this padding. When you perform an extension attack, the attack message would look like: secretfoo&bar130x80...padding...0x02&evil . At this point you're adding on the length and hashing it, so what you compare with is 'secretfoo&bar130x80...padding...0x02&evil93' ... but the attacker can precompute that hash just as easily as the one with just 'evil' appended. You could argue that your hashes would be constructed a bit differently (eg make messages that appear to have internal padding illegal; still vulnerable, btw), but the point is - you're still tinkering with the same basic structure, and are likely to make more mistakes. You're better off switching to HMAC for this application.

deleted 13y ago
[deleted]

jdbernard 13y ago

The attacker just needs to include the updated length, which he can likely calculate since the shared secret is probably the same length for all accounts-even if it is not he only needs it for this request--and he knows the length of the parameters and their values. It would take some guesswork and trial and error to nail it down, and the attacker would have to guess that the length was included in the first place. Assuming he has plenty of time and processing power it is not infeasible. There are a lot of fairly easy things you could add to make it more difficult to attack.

deleted 13y ago
[deleted]
- tptacek 13y ago
  The attacker doesn't "update" the length. The attacker appends data to the message, which has the effect of turning the previously stamped message length into just another bunch of bits in the middle of the message, and then includes their own message length at the end. The final message must accurately represent the length of the original message including the shared secret, so there's trial and error involved, but it's just trials of "possible length of the shared secret". Again, this works on MD4, MD5, SHA1, and all the SHA2's. You shouldn't have deleted your comment. You're not expected to know this stuff. Very few people, relative to the whole industry, or even relative to the number of programmers who end up trying to build crypto, actually do know how a length extension attack works.
  - wzdd 13y ago
    Yes, sorry for deleting a comment when there was a reply! For posterity, it was something like: "it seems like you would need to break MD5 in order to do this, because you'd have to update the length."

tptacek 13y ago

MD4, MD5, SHA1, and all the SHA2 variants use a structure called Merkle Damgard, which does include the message size. Most are vulnerable to length extension attacks. SHA3 (Ketchup) is not vulnerable to length extension attacks, because resistance to length extension was a design criteria for the SHA3 contest. Edit: Doh, SHA2-224 and SHA2-384 are truncated and aren't vulnerable

wzdd 13y ago
Thanks, I looked up Merkle Damgard now understand the comments about padding and how they would affect things. But I was specifically thinking of the following scheme: Message: [length][key-value pairs] Hash: MD5 (shared secret, message) Assuming that the rule is: the length is at the start of the message, and only "length" bytes of the message are used after the hash check passes. It seems that if you have found a hash collision, Merkle Damgard lets you find more collisions easily. But the exploit in the article doesn't require a hash collision. If you haven't found a hash collision, would the above scheme be vulnerable to length extension?
- tptacek 13y ago
  The attack has nothing to do with hash collisions; it has to do with the fact that the MD-structured hashes spit out their entire state at the end of the operation, which means an attacker can simply reformat the hash back into the hash core's state and continue hashing with it.
  - wzdd 13y ago
    I didn't think so, but I mentioned it because the Wikipedia article on Merkle-Damgård hashes (http://en.wikipedia.org/wiki/Merkle–Damgård_construction http://en.wikipedia.org/wiki/Merkle–Damgård_construction) talks about length extension attacks only in the context of hash collisions: "Length extension — once an attacker has one collision, he can find more very cheaply."
    - tptacek 13y ago