Would changing number of rounds in last compression prevent length extension attack?

LightBit

1/6/23, 6:49 PM

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?

1 + 4

hash

length-extension

merkle-damgaard

fgrieu

1/6/23, 7:33 PM

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](https://en.wikipedia.org/wiki/One-way_compression_function#Davies%E2%80%93Meyer) compression function of some Merkle-Damgård hash function?

LightBit

1/6/23, 8:41 PM

@fgrieu I had Matyas-Meyer-Oseas in mind.

fgrieu

1/6/23, 8:51 PM

At least [Matyas-Meyer-Oseas](https://en.wikipedia.org/wiki/One-way_compression_function#Matyas%E2%80%93Meyer%E2%80%93Oseas) 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.

LightBit

1/6/23, 9:10 PM

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).

Score:1

Crypto

fgrieu

1/6/23, 7:53 PM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Would changing number of rounds in last compression prevent length extension attack?

TH: การเปลี่ยนจำนวนรอบในการบีบอัดครั้งสุดท้ายจะป้องกันการโจมตีแบบขยายความยาวหรือไม่

RO: Schimbarea numărului de runde în ultima compresie ar preveni atacul de extindere a lungimii?

RU: Предотвратит ли изменение количества раундов в последнем сжатии атаку расширения длины?

VI: Việc thay đổi số vòng trong lần nén cuối cùng có ngăn chặn cuộc tấn công mở rộng độ dài không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.