8
$\begingroup$

Suppose, a message M was found so that MD5(M) = S, where S is the initial state of the MD5 function (0x01234567, ...).

Given a hash MD5(m), would this allow computing MD5(M∥m∥padding), where padding is an empty block to get the length right?

$\endgroup$
  • 1
    $\begingroup$ I changed the title to fix the misspelling of Damgård. An å is not the same as an a at all. If you can't type å with your keyboard, use the alternative spelling aa instead. $\endgroup$ – Clearer Aug 5 '17 at 23:26
7
$\begingroup$

Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2.


To see why, it's worth looking at how the MD5 hash (like other similar hash functions based on the Merkle–Damgård construction) works. Specifically, MD5 consists of a compression function $f: \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n$ (where, for MD5, $n = 128$ and $b = 512$), a fixed $n$-bit initial state vector $IV \in \{0,1\}^n$ and a padding scheme for extending an arbitrary input string to a multiple of $b$ bits (and also encoding its length into the padding).

For our purposes, it turns out to be useful to also define the iterated compression function $f^*$ that takes an $n$-bit IV $s_0$ and a sequence of $b$-bit input blocks $(m_1, m_2, m_3, \dots, m_k)$ as input, and returns the $n$-bit output $s_k$, where $s_i = f(s_{i-1}, m_i)$ for $1 \le i \le k$. Then, for any given input message $m$, we have $${\rm MD5}(m) = f^*(IV, m \,\|\, {\rm pad}_m).$$

In particular, the usual MD5 length extension attack lets us, given $H_m = {\rm MD5}(m)$ and the length of some unknown message $m$, compute ${\rm MD5}(m \,\|\, {\rm pad}_m \,\|\, x)$ for any arbitrary suffix $x$ as $f^*(H_m, x \,\|\, {\rm pad}'_x)$, where the modified padding ${\rm pad}'_x$ is the same as the normal MD5 padding for the message $x$, except that the input length encoded in the padding is increased by the length of the prefix $m \,\|\, {\rm pad}_m$.

Now, in your scenario, we have a special message $M$ such that $${\rm MD5}(M) = f^*(IV, M \,\|\, {\rm pad}_M) = IV.$$ Thus, by the construction of the iterated compression function $f^*$, we also know that $$f^*(IV, M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m) = f^*(IV, m \,\|\, {\rm pad}_m) = {\rm MD5}(m).$$

Thus, given ${\rm MD5}(m)$ and the lengths of $M$ and $m$, we can compute ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, x)$ as $f^*({\rm MD5}(m), x \,\|\, {\rm pad}''_x)$, where the modified padding ${\rm pad}''_x$ now encodes the combined length of $M$, ${\rm pad}_M$, $m$, ${\rm pad}_m$ and $x$.

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