0
$\begingroup$

Suppose we have some Merkle–Damgård hash function. Assuming compression function supports it and is equally secure with more rounds.

Would changing number of rounds (for example doubling them) for last block cipher compression prevent length extension attack?

$\endgroup$
4
  • $\begingroup$ In theory, a Merkle-Damgård hash function does not necessarily use rounds. And it's compression function comes in several common structures, none of which with a direct notion of rounds. Do you mean more rounds in some iterated encryption function of the Davies-Meyer compression function of some Merkle-Damgård hash function? $\endgroup$
    – fgrieu
    Sep 6 at 19:33
  • $\begingroup$ @fgrieu I had Matyas-Meyer-Oseas in mind. $\endgroup$
    – LightBit
    Sep 6 at 20:41
  • $\begingroup$ At least Matyas-Meyer-Oseas specifies the XOR (that the counter example in my answer needs to remove), and in that is similar to Davies-Meyer. And the extra block compared to Davies-Meyer seems to further guard against attack. But "more rounds" remains quite vague, even if we assume the block cipher used has rounds. Thus I'd better be safe than sorry and make no certain statement until further precisions. $\endgroup$
    – fgrieu
    Sep 6 at 20:51
  • 1
    $\begingroup$ We can assume block cipher has different round constants for every round. Simply calling block cipher twice I know would not work as it would be the same as adding zeros on message end. Another possibility might be to do $E_0(h) \oplus h$ (on end switch to Davies-Meyer and using all zero key to mask output). $\endgroup$
    – LightBit
    Sep 6 at 21:10
1
$\begingroup$

The question leaves to guess what the compression function is, and how it uses rounds. That being unspecified, no, increasing the number of rounds in the last compression function is not guaranteed to prevent length-extension attack, even if the compression function is changed and rather improved by adding more rounds to it.

Proof by counterexample: modify SHA-512 by

  • removing the exclusive-OR at the end of each compression function, in effect utilizing the block cipher of the Davies-Meyer compression function directly as the compression function;
  • and modifying the key schedule of that cipher so that it repeats after the number of rounds used in the block cipher of the compression function (but that block cipher is otherwise secure)
  • and doubling the number of rounds in that block cipher in the last compression function, reusing the same constants as in the first half

That combination in effect hashes twice the last block of the expanded message, and uses a compression function that's reversible. That leaves the hash theoretically weakened against some attacks, but still unbreakable from all practical standpoints. And that leaves it vulnerable to length-extension attack in some cases. For example, when the unknown input is one message block (128-byte) and we know it's hash, we can compute with certainty the hash of a 3-block (384-byte) input starting as the original, followed by twice the known block equal to the padding block of SHA-512 for 128-byte input.

On the other hand, if the change we make in the last compression function makes it essentially unrelated to the normal compression, yes we are demonstrably safe from the length-extension attack. Changing the constants used at each round of the block cipher of a Davies-Meyer or Matyas-Meyer-Oseas compression function as in SHA-2 (without changing the number of rounds) would do, beyond reasonable doubt. So would doubling the number of rounds and using new constants in the second half. I make no statement about doubling the number of rounds with the same constants.

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