4
$\begingroup$

I came across a few articles about length extension attacks on cryptographic hash functions. I was very surprised to read that SHA-256 and SHA-512 are prone to length extension attacks. This seems contradictory to the fact that—to the best of my knowledge—there are no known collisions on these algorithms.

According to the comparison of SHA functions table from Wikipedia the capacity against length extension attacks is 0 for both SHA-256 and SHA-512 which should mean that this attack does not require much computing resources.

Aren't length extension attacks considered as collisions as well?

$\endgroup$
  • 3
    $\begingroup$ Length extension attacks are conditional collisions. So assuming you know one collision, the length extension attack allows you to construct arbitrarily many out of that one. $\endgroup$ – SEJPM Nov 19 '19 at 13:01
  • $\begingroup$ Can you define conditional collision? Does assuming you know one collision mean that the length extension attack is still impractical for SHA-2? $\endgroup$ – DurandA Nov 19 '19 at 13:48
7
$\begingroup$

No, the length extension attack/property is not considered a collision. It does not allow to build a collision.

The length extension property is that given the hash of a bitstring $M$ of given length $l$ (but arbitrary and unknown content), it is possible to compute the hash of $M\mathbin\|F(l)\mathbin\|E$ with $F(l)$ a short bitstring deduced from the length of $l$, and any known bitstring $E$.

It follows that if messages $M$ and $M'$ of the same length collide (have the same hash even though $M\ne M'$), then $M\mathbin\|F(l)\mathbin\|E$ and $M'\mathbin\|F(l)\mathbin\|E$ also collide. Therefore, the length extension property eases building more collisions from an existing collision among messages of the same length.

MD5, SHA-1, SHA-256, SHA-512 have the length extension property (and correspondingly, it is used to extend MD5 and SHA-1 collisions). SHA-3 and SHA-512/256 do not have the length extension property, because enough of the internal state does not make it to the output. The situation is not clear cut for other SHA-2 hashes truncated to more than half their internal state size (e.g. SHA-224 has only 32 bits of resistance to length extension).

|improve this answer|||||
$\endgroup$

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.