<p>For an ideal hash function, the fastest way to compute a first or second <a href="http://en.wikipedia.org/wiki/Preimage_attack" rel="nofollow">preimage</a> 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.</p>

<p>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 2<sup>n</sup> to 2<sup>n-m</sup>. </p>

<p>A space-time trade-off over the brute-force attack is by exploiting <a href="http://en.wikipedia.org/wiki/Rainbow_table" rel="nofollow">rainbow tables</a>. I believe  the partial knowledge of the preimage may prove useful in mounting this attack too.</p>

CC BY-SA 3.0
2011-05-28T05:02:40.243Z
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
CC BY-SA 3.0
2011-05-28T07:26:37.907Z
@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
CC BY-SA 3.0
2011-05-27T18:43:03.897Z
2011-05-27T18:43:03.897Z
Sadeq Dousti
<p>If the <a href="http://www.senderek.com/SDLH/" rel="nofollow">hash function is secure</a> then it won't help beyond reducing the brute-force search-space.  This assumes the existence of <a href="http://en.wikipedia.org/wiki/One-way_function" rel="nofollow">one-way functions</a>.  If the <a href="http://en.wikipedia.org/wiki/MD5" rel="nofollow">hash function is not secure</a>, then there are <a href="http://en.wikipedia.org/wiki/Differential_cryptanalysis" rel="nofollow">various</a> <a href="http://en.wikipedia.org/wiki/Rainbow_table" rel="nofollow">methods</a>.</p>

CC BY-SA 3.0
2011-05-28T04:47:33.027Z
2011-05-28T04:53:06.457Z
2011-05-28T04:53:06.457Z
Dan Brumleve
<p>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!</p>

<p>Is there any technique which may reduce the difficulty of recovering plain text from a <a href="http://en.wikipedia.org/wiki/Cryptographic_hash_function" rel="nofollow">hash</a> if the attacker knows part of the plain text?</p>

<p>Here is an example.
Alice writes this letter:</p>

<pre><code>Dear Bob,
   Run!
Yours Truly,
Alice
</code></pre>

<p>Alice sends the plaintext to Bob over channel X and the hash over channel Y.</p>

<p>Eve intercepts the hash but not the plaintext.</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2011-05-28T14:09:01.330Z
@Kaveh: Probably "cryptographically-secure hash functions."
Sadeq Dousti
CC BY-SA 3.0
2011-05-28T17:00:17.903Z
"partial plaintext knowledge" sounds to me similar to *salt* in the context of crypto.
kasterma
CC BY-SA 3.0
2011-05-28T19:37:42.557Z
@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
CC BY-SA 3.0
2011-05-29T07:28:43.497Z
@Sadeq, I added a link to wiki page of cryptographically-secure hash functions.
Kaveh
CC BY-SA 3.0
2011-05-30T04:21:14.073Z
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.
<cr.crypto-security><hash-function><cryptographic-attack>
Can one reverse a hash with partial plaintext knowledge?
dss539
# Can one reverse a hash with partial plaintext knowledge?

(Asked by: username_0 on 2011-05-27)

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

**Tags:** cr.crypto-security, hash-function, cryptographic-attack
> **Comments:**
> **username_1**: @Kaveh: Probably "cryptographically-secure hash functions."  
> **username_2**: "partial plaintext knowledge" sounds to me similar to *salt* in the context of crypto.  
> **username_1**: @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).  
> **username_3**: @Sadeq, I added a link to wiki page of cryptographically-secure hash functions.  
> **username_4**: 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?  

---

## 2 answers

### Answer by username_1 on 2011-05-27. Score: 8 | Accepted answer

For an ideal hash function, the fastest way to compute a first or second [preimage](http://en.wikipedia.org/wiki/Preimage_attack) 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](http://en.wikipedia.org/wiki/Rainbow_table). I believe the partial knowledge of the preimage may prove useful in mounting this attack too.

> **Comments:**
> **username_5**: 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).  
> **username_1**: @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.  

---

### Answer by username_5 on 2011-05-28. Score: 2

If the [hash function is secure](http://www.senderek.com/SDLH/) then it won't help beyond reducing the brute-force search-space. This assumes the existence of [one-way functions](http://en.wikipedia.org/wiki/One-way_function). If the [hash function is not secure](http://en.wikipedia.org/wiki/MD5), then there are [various](http://en.wikipedia.org/wiki/Differential_cryptanalysis) [methods](http://en.wikipedia.org/wiki/Rainbow_table).


---

