3
$\begingroup$

It always seemed to me that length extensions are possible simply because no special operation is performed after the last operation - for instance in a Merkle-Damgård construction. Basically the MD construction makes sure that the hash state is secure after processing each block, and therefore the hash state can be directly used as the output of the hash function.

All the bits in the state should depend on all the input bits. That should mean that it will be as hard to find a hash with a short Hamming distance to an existing hash value as to find a hash with a much larger Hamming distance.

So if this reasoning is correct then any operation that:

  1. doesn't affect the security of the hash;
  2. cannot be reduced to the operation performed on each block;

should be able to turn a hash that allows length extension attacks to a hash that doesn't allow length extension attacks.

Questions:

  1. Any problem with my reasoning? Is any bit flip enough for the full output of the hash (see note below)?
  2. If it is that simple, is there any reason why it hasn't been performed on SHA-2? Were length extension attacks unknown or not seen as a problem?
  3. Would such a stupidly simple construction be an viable alternative to HMAC (with $K \| M$ as input message and a static size of $K$)?

Note: Flipping a single bit could do the trick if my reasoning is correct, but it has the drawback that partial hashes may not be affected. Flipping every bit - to get the complement of the hash value - should work as well - I think.

$\endgroup$
  • 4
    $\begingroup$ Could you clarify what bit(s) you would be flipping at what step in say, SHA-256 or a stated modification of that? Merely flipping (some of) the output won't prevent a slightly modified length extension attack that undoes the flip. $\endgroup$ – fgrieu Sep 26 '18 at 11:12
  • 4
    $\begingroup$ Indeed, the length extension attack does not at all require that the output is the internal state, but merely that the attacker can obtain the internal state. Any easily invertible transformation to the output can easily be reversed by an attacker. $\endgroup$ – yyyyyyy Sep 26 '18 at 11:16
1
$\begingroup$

The mistake I made is that flipping a bit (or all bits) of the output will still leak the full state of the hash function, after which it is possible to perform a length extension attack by updating more data from the given intermediate state. The bit flip is of course easily reversed by an adversary. Thanks go to fgrieu and yyyyyyy for pointing this out.

Performing a final calculation may still work, but it should of course not allow an attacker to retrieve the state after the last block was compressed. That means that the final operation needs to be one-way as well. This disallows simple instructions such as XOR (with known data) that can be reversed.

$\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.