So I'm trying to solve this problem. enter image description here

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.

  • 2
    $\begingroup$ 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). $\endgroup$ – 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$


$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$


  • $\begingroup$ -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. $\endgroup$ – forest Oct 16 '18 at 22:33
  • $\begingroup$ @forest On the other hand, we are not a homework service, so arguably we should not provide full answers to such homework problems. $\endgroup$ – fkraiem Oct 17 '18 at 2:55
  • $\begingroup$ @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. $\endgroup$ – forest Oct 17 '18 at 3:07

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.