Reversing a block hash of SHA-1 with known Plaintext?

Question

Is it possible to reverse the hashing of a block in a Datastream fed to an SHA1 if the plaintext for that block is known? If it is not possible (which I assume) does it make attacks to retrieve the state easier?

An example what I'm trying to figure out: The following data is known:

• suffix1
• The result of SHA1(secret + suffix1)
• The length of secret, which happens to be exactly 512 bit (ie a full SHA block)

Now what I'd like to figure out is SHA1(secret + suffix2) (a different known suffix)

(+ means String concatenation)

(suffix1 is known but can not be manipulated a length extension attack is (probably (?)) not possible)

Is this possible? Is there any research on doing this or is it just plain out impossible? If it is possible: Does this also apply to the SHA-2 family?

Thank you!

Answer 1

Recomputing secret from SHA-1(secret || suffix1) (for any known value of suffix) would constitute a preimage attack. No preimage attack faster than luck is currently known for SHA-1 ("luck" works in average effort 2¹⁶⁰ for SHA-1, i.e. totally infeasible). You won't get the secret value.

However, if your goal is to compute SHA-1(secret || suffix2) then that one may be possible, depending on the value of suffix2. It is called the length extension attack. Namely, suffix2 must begin with suffix1, followed by some padding bits which depend on the length of secret || suffix1; after these bits (which you do not choose), you can put whatever data you want. In that sense, suffix2 is partially controlled by the attacker.

Length extension attacks are sufficient to show that SHA-1(secret || data) is a poor MAC, and HMAC should be used instead (all of this applies equally well with the SHA-2 functions, by the way).

Now if you do not want to put any constraint on suffix2, then this is going to be hard. The effect of secret boils down to an unknown 160-bit state at the start of the second block. I don't have time this morning to work this out mathematically, but my intuition is that finding that state value from the output of SHA-1(secret || suffix1) would be equivalent to exploring a cycle in the permutation incarnated by the SHACAL block cipher with suffix1 as key (assuming suffix1 + padding fits in one block). Since SHACAL is supposed to be a "good" block cipher, this permutation should behave as if chosen randomly among the set of possible permutation of a space of size 2¹⁶⁰, meaning that the cycle should have, on average, a length close to 2⁸⁰. This again implies a cost too high to do it in practice.

Note that being able to do what you try to achieve would not contradict the properties of SHA-1 as a "good hash function" (resistance to collisions, preimages and second preimages). It does not mean that we don't care about it, but it highlights why hash functions and random oracles are not exactly the same thing.