Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  CodesInChaos Jan 30 '13 at 14:49
1  
@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. –  poncho Jan 30 '13 at 16:09
    
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 –  wu7 Feb 9 '13 at 14:38
    
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. –  CodesInChaos Dec 21 at 18:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.