Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

First off, please forgive my ignorance because I am not as well versed in cryptography and mathematics as I would like to be. I may say something obviously wrong/dumb; please point it out!

Is there any technique which may reduce the difficulty of recovering plain text from a hash if the attacker knows part of the plain text?

Here is an example. Alice writes this letter:

Dear Bob,
   Run!
Yours Truly,
Alice

Alice sends the plaintext to Bob over channel X and the hash over channel Y.

Eve intercepts the hash but not the plaintext.

Eve knows Alice starts the message with "Dear Bob," and ends with "Yours Truly, Alice". Eve also knows that Alice sends messages in fixed blocks and will pad the body content with whitespace to meet the required block length.

Can Eve use her knowledge of 1)fixed message size and 2)partial plaintext knowledge to reduce the computational difficulty of reversing the hash?

I would appreciate any help on this topic, even if your answer is just "read this whitepaper".

share|improve this question
    
@Kaveh: Probably "cryptographically-secure hash functions." –  Sadeq Dousti May 28 '11 at 14:09
    
"partial plaintext knowledge" sounds to me similar to salt in the context of crypto. –  kasterma May 28 '11 at 17:00
    
@Kaveh: Collision-resistance and one-wayness are orthogonal but related properties. "Cryptographically-secure hash functions" is an umbrella term for both. However, I believe this question is more concerned with one-wayness (i.e. the hardness of finding one preimage). –  Sadeq Dousti May 28 '11 at 19:37
    
@Sadeq, I added a link to wiki page of cryptographically-secure hash functions. –  Kaveh May 29 '11 at 7:28
    
The answer depends upon the hash; the question is ill-specified. What hash function are you using? Alternatively, what can be assumed about the hash function? –  D.W. May 30 '11 at 4:21

2 Answers 2

up vote 8 down vote accepted

For an ideal hash function, the fastest way to compute a first or second preimage is through a brute-force attack. That is, if there's no structural weaknesses in the design of the hash function, your best bet is to mount a brute-force attack.

The knowledge of the message size (n bits) and some parts of it (m bits) will certainly reduce the complexity of finding a preimage under the brute force attack: The worst-case complexity will reduce from 2n to 2n-m.

A space-time trade-off over the brute-force attack is by exploiting rainbow tables. I believe the partial knowledge of the preimage may prove useful in mounting this attack too.

share|improve this answer
    
Only general preimage knowledge can improve the effectiveness of a rainbow table, e.g. we design it to produce only alphanumeric outputs. If the preimage is specifically assumed to start with "Dear Bob," then we will need an entire rainbow table for that particular prefix. I don't mean to nitpick (my answer links to the same article with no explanation). –  Dan Brumleve May 28 '11 at 5:02
    
@Dan: That's the reason I said it "may" prove useful. That is, it is helpful if you know the partial knowledge prior to constructing the rainbow tables. –  Sadeq Dousti May 28 '11 at 7:26
    
Thanks for the answer. –  dss539 Jun 3 '11 at 21:01

If the hash function is secure then it won't help beyond reducing the brute-force search-space. This assumes the existence of one-way functions. If the hash function is not secure, then there are various methods.

share|improve this answer

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.