16
$\begingroup$

A lot of hash functions, including the SHA-2 family(but not the SHA-3 candidates and SHA256d) are vulnerable to length extension attacks. But when is this property a problem?

I guess certain naive MAC implementations might have issues. Are there also some situations where length-extensions cause problems for unkeyed hashes?

$\endgroup$

2 Answers 2

11
$\begingroup$

The archetypal situation where the length-extension property becomes problematic is when ones builds a Message Authentication Code from a hash function as $$\textrm{BadMAC}(K,M)=\textrm{Hash}(K||M)$$ where $K||M$ is the concatenation of the Key and the Message.

The length extension property then translates directly into the capability to forge a different message, starting as the original, for which computing the $\textrm{BadMAC}$ is trivial.

In practice, that could allow adding an appendix to a text protected by $\textrm{BadMAC}$ (after a short rash of garbage in most cases, but often it could be invisible when printed). Also, that could allow extending the size of a short signed message so that it creates a buffer overflow after its integrity is checked using $\textrm{BadMAC}$.

That's not a worry when the hash is used in HMAC, which is secure against the length-extension; and then more.


Another (artificial) example could be when it is asked the hash of increasingly long messages (with precisely the wrong content) as a Proof-Of-Work: one user knowing the hash constituting the POW of a user could abuse that into another POW indicative of slightly more work.


To build a hash secure against the length-extension attack, there are a number of methods:

  • re-hash the output of the hash; that's the strategy in $\operatorname{SHA-256d}$, defined as $\operatorname{SHA-256d}(M)\gets\operatorname{SHA-256}(\operatorname{SHA-256}(M))$.
  • throw away at least as many bits of the hash output as the desired security level; e.g. SHA-512/256, which is a 256-bit hash obtained by truncating a 512-bit hash.
  • build the hash with the sponge construction, e.g. SHA-3.
$\endgroup$
3
  • 3
    $\begingroup$ Similar multi collision attacks apply to all narrow pipe hashes, since for them, finding a state collision isn't harder than finding an output collision. $\endgroup$ Jun 19, 2015 at 6:53
  • $\begingroup$ Length-Extension can also be exploited to make for more impressive demonstrations of collision attacks as Thomas explained here. $\endgroup$
    – SEJPM
    Mar 9, 2017 at 13:25
  • $\begingroup$ Since this answer has bubbled up to the surface: The entirety is dependent on following and interpreting an initial link that ties the answer to Merkle–Damgård pipey architectures. Other hashes of (K||M) are okay (BLAKEx). Would this be the oldest edit (10 years)? $\endgroup$
    – Paul Uszak
    Oct 31, 2022 at 17:01
2
$\begingroup$

Another affected use is in commitments where a hash function is meant to perfectly hide some information until time comes to reveal it. A function susceptible to length-extension would allow an adversary to attempt to link publicly known hashes (of unknown preimages) by testing whether their preimages are substrings of one another, thus weakening the unlinkability property. The attack is feasible only for smaller lengths, as it involves brute-forcing some N bytes of extensions to test any 2 hashes.

There is some literature discussing this:

The binding property of this commitment follows from the collision-resistance of the hash function H, since to be able to open the commitment in two different ways a malicious sender would need to find collisions in H. For the hiding property we need to assume that H is a random oracle. We think that this is satisfactory since anyway the security of the Bitcoin PoWs relies on the random oracle assumption. Clearly, if H is a random oracle then no adversary can obtain any information about x if he does not learn s (which an honest C keeps private until the opening phase).

Notice that use of single SHA-256 would be insecure here, because it is constructed using Merkle–Damgard transformation and therefore it is susceptible to the length extension attack [21]. It this attack an adversary which knows H(x) can compute a value H(x||y) for some string y controlled by him without the knowledge of the original value x. It could allow to completely compromise the lottery protocol, because the winner choosing function (described later) highly depends on the lengths of the secrets.

M. Andrychowicz, S. Dziembowski, D. Malinowski and L. Mazurek, "Secure Multiparty Computations on Bitcoin," 2014 IEEE Symposium on Security and Privacy, 2014, pp. 443-458, doi: 10.1109/SP.2014.35.

The "unlinkability" property has a good definition here:

Unlinkability of two or more items of interest (IOIs, e.g., subjects, messages, actions, ...) from an attacker’s perspective means that within the system (comprising these and possibly other items), the attacker cannot sufficiently distinguish whether these IOIs are related or not.

See also: https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks, which provides a practical example and a hash_extender tool.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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