12
$\begingroup$

As I understand length extension attacks, they depend on the coincidental property of most cryptographic hash functions that the hash value is exactly the hash function state after hashing the last block of data. This enables an attacker to initialize their own hash function with the state as it "left off".

This being the case, why are hash functions simply not defined as outputting the n-byte prefix of their state (i.e. for a 256-bit hash, maintain 512 bits of state)? I'm assuming there's a fundamental reason this isn't done, but I haven't been able to find any literature specifically addressing it.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ That approach is secure. Perhaps there are even some SHA-3 candidates which use this approach, though I can't think of one. $\endgroup$ – CodesInChaos Jul 14 '15 at 14:20
13
$\begingroup$

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are output. These hash functions are resistant against length-extension attacks since an attacker would have to guess the remaining (too many) bits of the internal state. (Note that the choice of different initial values is irrelevant to this issue, so just truncating SHA-256 or SHA-512 also yields length-extension-resistant hashes.)

As another almost-example: In some sense, Keccak/SHA3's first $r$ output bits are simply a prefix of the internal state after consumption of the last block, while the rest of the state is kept secret (and possibly used to compute more output bits, which are again prefixes of the internal state, through repeated application of a so-called "sponge function"). With this construction one can argue, and in fact this is advertised as a feature of Keccak, that the keyed hash $\operatorname{Keccak}(\mathit{key}\mathbin\Vert\mathit{data})$ yields a secure MAC, while the same construction for Merkle-Damgård hashes is vulnerable to length-extension attacks.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Well, SHA-224 has a lot less than 112/224-bit security if used in a way that allows length extension. SHA-384 likewise. SHA-512/256, OTOH, is secure regardless. $\endgroup$ – otus Jul 14 '15 at 19:45
  • $\begingroup$ Is there any disadvantage to having extra state bits that are held back? Suppose if one were to xor the first 32 bits of each block with the arithmetic checksum of the words in the previous block and the next 32 bits with the xor of those words. If hashing time is dominated by data fetching, the cost of the extra computations should be negligible, but only one in 2^64 otherwise-possible illicit block substitutions would "work". $\endgroup$ – supercat Jul 14 '15 at 20:05
  • 1
    $\begingroup$ I imagine that it comes down to what you're defending against. Any bits "held back" are being used to protect against length extension, and are thus not present in the output hash protecting against hash collision. $\endgroup$ – sehrgut Jan 25 '16 at 20:45
  • $\begingroup$ @otus SHA-224 is a truncated SHA-256 which only has an internal state size of 256 bits. So that leaves 32 bits of unknown state. Probably it is possible to brute force to find the missing bits in order to create a length extension attack? SHA-384 on the other hand is based on a truncated SHA-512 with an internal state size of 512 bits. So that leaves 128 bits of unknown state. Much harder to brute force. I would say SHA-384 is probably strong against length extension attacks. $\endgroup$ – NDF1 Jun 3 '17 at 4:09
  • $\begingroup$ @NDF1, I agree that it would be strong in practice, but I was talking about theoretical breaks – SHA-384 claims at least 192-bit resistance against all attacks, which such a scenario would likely violate. With SHA-512/256 there is no such issue. $\endgroup$ – otus Jun 6 '17 at 5:07

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.