2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ @Kaveh: Probably "cryptographically-secure hash functions." $\endgroup$
    – Sadeq Dousti
    Commented May 28, 2011 at 14:09
  • $\begingroup$ "partial plaintext knowledge" sounds to me similar to salt in the context of crypto. $\endgroup$
    – kasterma
    Commented May 28, 2011 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$
    – Sadeq Dousti
    Commented May 28, 2011 at 19:37
  • $\begingroup$ @Sadeq, I added a link to wiki page of cryptographically-secure hash functions. $\endgroup$
    – Kaveh
    Commented May 29, 2011 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.
    Commented May 30, 2011 at 4:21

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 28, 2011 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$
    – Sadeq Dousti
    Commented May 28, 2011 at 7:26
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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