# How to determine if a Hash function is preimage resistant?

So I'm trying to solve this problem. There are of course more but I'm trying to figure out how would I even solve this first one in order to do the rest. Any hints or help in the steps would be appreciated. I'm literally out of ideas.

• Hint: your main options are, for each hash function considered, to A) prove that $H_i$ is not preimage resistant, by exhibiting (an algorithm that finds) a collision, that is $(x_0,y_0)$ and $(x_1,y_1)$ with $H_i(x_0,y_0)=H_i(x_1,y_1)$; in the process (algorithm) that finds $(x_0,y_0)$ and $(x_1,y_1)$ it can be be used $E$ and $E^{-1}$ as a black box. B) prove that $H_i$ is preimage resistant, by proving that any algorithm that finds a collision (as in A) could be turned into an algorithm that breaks $E$ (that is distinguishes it from an ideal cipher). – fgrieu Oct 15 '18 at 6:07

The only chance you have here is either:

• show that it is not preimage-resistant, i.e. how you could, given a value $$h$$ find a preimage $$(x,y)$$ with $$H(x,y) = h$$. Using the structure of the hash-function might help here.

• reduce the preimage-resistance to some property of its constituents, here the block cipher. So, show that if you have some machine (function) $$\tilde H_1$$ which, for an input $$h$$ gives you a preimage $$(x,y) = \tilde H_1(h)$$ with $$H_1(x,y) = h$$, you can construct a machine which violates some of the properties of an ideal block cipher (like allowing to find a key or plaintext from ciphertext, or something similar – look for your definition of ideal block cipher). (This likely won't work for $$H_1$$, but might work for some of the other ones.)

For all of the non-broken real-world hash functions, unfortunately we can't do any of those, because we don't have ideal ciphers.

$$H_1 (x,y) = E_y(y) \oplus x$$

Hint;

$$H_1( E_y(y) \oplus x ,y)= ?$$

More Hint;

$$H_1( E_y(y) \oplus x ,y)= E_y(y) \oplus E_y(y) \oplus x = x$$

conclusion?

• -1 This is not a complete answer and would probably be better written as a comment, as fgrieu has done for example. While hints may be useful to a single person, they are decidedly not useful to others who may visit this site with the same question and do not want just a hint. – forest Oct 16 '18 at 22:33
• @forest On the other hand, we are not a homework service, so arguably we should not provide full answers to such homework problems. – fkraiem Oct 17 '18 at 2:55
• @fkraiem We do answer questions even if they are homework questions, if they are well-researched. If they are not, then the correct course of action is to close the question, not to write a comment as an answer. – forest Oct 17 '18 at 3:07