7
$\begingroup$

The compression function of SHA-1 when used in Davies-Meyer mode adds its input to the chaining values at the final step. For the first message block, the IV is used as the input and in the next step, the previous block's output (as specified by Merkle-Damgård) is used. These values are fed to the last round of the compression function.

Why would removing the feed-forward part (i.e.,the final step where the input value is added to the result to get the final output) make the hash function insecure? Apart from the fact that the compression function would not satisfy desired randomness properties (being a permutation for each fixed message).

$\endgroup$
10
$\begingroup$

If you remove the feed-forward part, then you reduce the strength of the hash against preimage attacks. We expect a hash with an $N$ bit output to require $O(2^N)$ steps to find a preimage (that is, an input that hashes to a specified value). However, without the feed-forward, we can find a preimage with $O(2^{N/2})$ steps.

Here's why: without the feed-forward, the compression operation is reversible; if you know the output of the compression function and the block of data being hashed, you could compute the input to the compression function.

Here is how this works: suppose we have SHA-256 (to take a concrete example), and we want to find a preimage for a specific value $x$. We consider two block messages (after padding); we construct $2^{128}$ initial blocks $A_i$ and compute what the state $a_i$ of the SHA-256 hash after each such initial block.

We also construct $2^{128}$ final blocks (which include the SHA-256 internal padding) $B_j$ and compute what the state $b_j$ of the SHA-256 hash would be previous to that (assuming that the final state of the SHA-256 hash is $x$.

We scan through the lists $a_i$ and $b_j$ looking for a match; if we find a specific pair $a_i = b_i$, we then know that the message $A_i B_j$ will hash to the value $x$; that's because the initial block $A_i$ will set the SHA-256 state to $a_i$, and then the final block $B_j$ will convert that state $b_j$, which is the same as $a_i$ to the desired final state $x$. Thus, we found a preimage to a 256-bit hash with about $2^{128}$ steps.

In essense, we use an internal collision to find the preimage. Adding the feed-forward makes this attack impossible.

(One note: if you try this attack against SHA-384, you find it takes $2^{256}$ steps, not $2^{192}$ as this analysis would seem to imply. It is still easier than the $2^{384}$ steps would would expect from a 384 bit hash.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ btw. SHA-3 has no feed-forward, but its internal state is big enough to prevent this attack, just like it wouldn't be a problem in SHA-512/256. $\endgroup$ – CodesInChaos Jan 30 '13 at 14:49
  • 2
    $\begingroup$ @CodesInChaos: the question was "why do they do something a Merkle-Damgard hash"; since SHA-3 isn't a M-D hash, how it works doesn't really apply. And, yes, SHA-512/256 avoids the problem; however, that was designed considerably after the SHA-512 compression function; the original reasoning did apply to how the SHA-512 compression function was envisioned to be used. $\endgroup$ – poncho Jan 30 '13 at 16:09
  • $\begingroup$ ok, to simplify, if we look only at 1-block messages, then, with the feed-forward it is not possible to efficiently find pseudo-preimages, whereas without feed-forward this is easily done. then this extends to a regular preimage for 2-block messages as explained above $\endgroup$ – wu7 Feb 9 '13 at 14:38
  • $\begingroup$ MD vs sponge is of little relevance. If the primitive of an iterated hash is reversible the MitM attack applies and you thus need a wide pipe to achieve full preimage resistance. $\endgroup$ – CodesInChaos Dec 21 '14 at 18:33
0
$\begingroup$

There's an additional problem to the preimage attack outlined by poncho.

Namely the security proof for collision resistance for Merkle-Damgard relies on the fact that the compression function itself is collision resistant. If we were to to modify the Davies-Meyer construction from $h(H,m)=F_m(H)\oplus H$ to $h'(H,m)=F_m(H)$ we would lose the collision resistance if we instantiate $F$ with an (ideal) block cipher. And remember that the original point of Davies-Meyer was to turn a block cipher into a compression function suitable for a hash function.

The collision-attack on $h'$ would look as follows if $F$ is a block cipher: Pick any $(H,m)$ you like, compute $F_m(H)=H^+$. Then pick any message block you like, e.g. $m'\neq m$ and compute $H'=F^{-1}_{m'}(H^+)$ (remember that $F$ is a block cipher which is invertible knowing the key). We now have $h'(H,m)=h'(H',m')$ for $m\neq m'$ and thus a collision in the compression function.

Thus the normal security proof wouldn't apply here and one would have to look deeper whether this leads to exploitable collisions or whether the fixed IV and the use of the message as the key-input saves enough unpredictability. Of course all of this is prevented by a simple XOR operation with a known value...

| improve this answer | |
$\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.