3
$\begingroup$

What i am trying to understand is shown in all three properties of secure hash function, i will focus on pre-image resistance.

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

My question is, what does "given" means 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.

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

----------------------EDIT------------------------------

The link @hamidreza posted was really helpful. In the paper they describe 3 definitions for preimage resistance, called Pre, e(verywhere)Pre and a(lways)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 with 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, 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?

$\endgroup$
  • $\begingroup$ Indeed the definition you cite is not good; find a better one, probably from another source. $\endgroup$ – fkraiem Apr 22 '17 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$ – Antonis Paragas Apr 22 '17 at 10:38
  • 1
    $\begingroup$ Take a look at Rogaway's paper: eprint.iacr.org/2004/035.pdf $\endgroup$ – Hamidreza Apr 22 '17 at 10:39
  • $\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 '17 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.