2
$\begingroup$

Have there ever been some publicized efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction (MD5, SHA1, SHA2, ...)?

$\endgroup$
  • 1
    $\begingroup$ Double-Hashing and truncation? $\endgroup$ – SEJPM Apr 3 at 13:05
  • $\begingroup$ HMAC is the typical construction $\endgroup$ – Natanael Apr 4 at 0:01
6
$\begingroup$

Yes. In this paper, Coron and al. showed that a plain MD construction is secure when it's inputs are prefix-free. They actually proved the indifferentiability of the construction. In other words messages need to be encoded in a prefix-free manner.

Quoting the paper:

A prefix-free code over the alphabet $\{0, 1\}^κ$is an efficiently computable injective function $g: \{0, 1\}^∗ \to (\{0, 1\}^κ)^∗$such that for all $x \neq y$, $g(x)$ is not a prefix of $g(y)$.

One such encoding is given in the paper

Function g1(m): let $N$ be the message length of $m$ in bits. write $m$ as $(m_1, \ldots , m_l)$ where for all $i$, $|m_i| = k$. and with the last block $m_l$ padded with $10^r$. let $g1(m) = (\langle N \rangle, m_1, \ldots , m_l)$ where $\langle N \rangle$ is a $κ$-bit binary encoding of $N$.

$\endgroup$
2
$\begingroup$
  • Fixed output filters like SHA-256d
  • Keyed output filters like HMAC, envelope-MAC, etc.
  • Truncation like SHA-512/256
  • Prefix-free message encoding like length-prefixed
  • Non-MD designs like BLAKE2 with HAIFA, SHA-3 with a sponge
$\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.