How are the weaknesses of the Merkle–Damgård construction (i.e. the Herding attack, multicollisions, length extension, expandable messages) avoided in the sponge construction?

  • $\begingroup$ The significance of this question is that a sponge is used in SHA-3 / Keccak. $\endgroup$
    – Nayuki
    May 15 '17 at 0:13
  • 2
    $\begingroup$ I'm not a native English speaker, but to me, the current title seems to indicate that a sponge construction is a type of Merkle-Damgård construction. Not sure how I would rephrase it though. $\endgroup$
    – pipe
    May 15 '17 at 0:25

There's two ways to answer this. One would be to go over the individual M-D weaknesses you list and show why the sponge construction is resistant to them. For example, if you consider length extension, the attacker knows:

  • The permutation $F$, capacity $c$, bitrate $r$ and padding rule used in the sponge instance;
  • The length of a message $m$ and its hash output $h$, but not the content of $m$. For simplicity, we'll assume the output length is $r$.

To perform a length extension, the attacker has to guess the content of the $c$ capacity bits, and test each guess against some sort of oracle that will tell them whether they hit the correct $c$-bit combination.

The other, more general way to answer is to remark that the sponge construction is random oracle indifferentiable. This means that any attack that distinguishes a random oracle from a random sponge can only succeed with negligible probability. As the sponge functions page puts it:

One could exhaustively list all the properties that a hash function should resist to and assign them resistance levels. Alternatively, claiming the security of a concrete function with regard to a model means comparing the success probability of an attack on the concrete function against that on the model. This allows compact security claims, which address all the possible properties at once, including future requirements not foreseen in an exhaustive list.


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.