What I am trying to understand is shown in all three properties of a secure hash function, I will focus on Preimage attack resistance.

Preimage resistance: given a hash h, it's difficult to find m s.t. H(m)=h

My question is, what does "given" mean in this case?

Does it mean for a randomly selected h from the output space of H, or can it be a specific hash selected by the adversary?

For example, assume a secure hash function H defined as $H: \{0,1\}^*\rightarrow\{0,1\}^n$. We will build a hash function H' that returns $0^n$ when input=0 otherwise returns $H(input)$.

An adversary in that example knows that if the $h=0^n$ then the message could be 0. So in the case that he can select the h he can violate pre-image resistance, otherwise, in the case, the input is randomly selected, since H' is secure, the probability of getting $0^n$ would be negligible and so the property still holds.

The same goes when selecting two messages m1,m2 for 2nd preimage, and collision resistance.


The link @hamidreza posted was really helpful. In the paper, they describe 3 definitions for preimage resistance, called Pre, e(everywhere)Pre, and an (always)Pre.

Pre: in which the adversary is given a hash of a randomly generated message along with the key (randomly generated as well) of the function.

ePre: I didn't quite get it, I think the adversary has |Y| shots to generate a random message and its hash be included in the given set of hashes Y for a specific key (randomly generated).

aPre: similar to the first one but stronger, the adversary can find a key for which he will be able to generate a collision for a hash of a randomly generated message.

So, to answer my question, the adversary doesn't get to choose the hash for any of the suggested definitions. Based on Pre at least, the H' that I defined is pre-image resistant since the chance of picking m=0, or any other m s.t. $H(m)==0^n$ is negligible

Are the definitions correct?

  • 1
    $\begingroup$ Indeed the definition you cite is not good; find a better one, probably from another source. $\endgroup$
    – fkraiem
    Apr 22, 2017 at 10:15
  • $\begingroup$ Do you have any good source? I have checked various definitions, as for example link or link and they all give similar definitions $\endgroup$ Apr 22, 2017 at 10:38
  • 1
    $\begingroup$ Take a look at Rogaway's paper: eprint.iacr.org/2004/035.pdf $\endgroup$
    – Hamidreza
    Apr 22, 2017 at 10:39
  • 2
    $\begingroup$ "Given" means that h is chosen usually uniformly from $\text{{0,1}}^n$. If h was constant in the experiment, and m is a message such that H(m)=h, you have the adversary that simply outputs m and wins the experiment with probability 1. The point of choosing the given image randomly (which is the same reason you need "key" in cryptographic hashing experiments) is to avoid the scenario I've described above. $\endgroup$
    – sel
    Apr 22, 2017 at 13:09


Your Answer

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