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,
Yours Truly,

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".

  • $\begingroup$ @Kaveh: Probably "cryptographically-secure hash functions." $\endgroup$ – M.S. Dousti May 28 '11 at 14:09
  • $\begingroup$ "partial plaintext knowledge" sounds to me similar to salt in the context of crypto. $\endgroup$ – kasterma May 28 '11 at 17:00
  • $\begingroup$ @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). $\endgroup$ – M.S. Dousti May 28 '11 at 19:37
  • $\begingroup$ @Sadeq, I added a link to wiki page of cryptographically-secure hash functions. $\endgroup$ – Kaveh May 29 '11 at 7:28
  • $\begingroup$ 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? $\endgroup$ – D.W. May 30 '11 at 4:21

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.

| cite | improve this answer | |
  • $\begingroup$ 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). $\endgroup$ – Dan Brumleve May 28 '11 at 5:02
  • $\begingroup$ @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. $\endgroup$ – M.S. Dousti May 28 '11 at 7:26

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.

| cite | improve this answer | |

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.