Hacker News Reader

Comment by tptacek | Hacker News Reader

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

View on HN

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?

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.

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) 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."

That's actually a relatively new finding, and a very cool attack (I assume we're talking about Joux multicollisions).

Multi-collisions is another thing. What Wikipedia means is that once you find m and m' s.t. H(m) = H(m'), then you've also found the collision H(m || X) = H(m' || X) for whatever X, i.e., unlimited collisions.

Reply on news.ycombinator.com