Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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!

share|improve this question
    
There is no known attack against SHA-1 that would help in determining the value of secret. However, this scheme is vulnerable to length-extension attacks. Knowing SHA-1(s), you can easily find the padding p, and from there is is trivial to calculate the value of SHA-1(s + p + anything), even though you don't know s. –  Stephen Touset Oct 29 '13 at 23:48
    
Thank you. However as I already mentioned I can not modify suffix1 in such a way to include the padding. I'm also not trying to retrieve secret (which is probably rather hard) what I'm trying to find is SHA-1(secret + anything) without special requirements on anything (ie. that is has to start with a SHA-1 padding) –  Patrick Huy Oct 30 '13 at 10:32

1 Answer 1

up vote 4 down vote accepted

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 2160 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 2160, meaning that the cycle should have, on average, a length close to 280. 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.

share|improve this answer
    
Thank you for your detailed answer! If you ever find the time to work out the maths please do. 2**80 really is quite a large number! –  Patrick Huy Oct 30 '13 at 17:13

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.