3
$\begingroup$

My question mainly stems from the following observation of properties of cryptographic hash function:

  1. Preimage resistance: Given $H(x)$, it's hard to find $x$
  2. Second preimage resistance: Given $m1$, it's hard to find another $m2$ such that $H(m1)=H(m2)$
  3. Collision resistance: It's hard to find any two distinct messages $m1$, $m2$ such that $H(m1)=H(m2)$.

It is said that property 3 implies property 2 which implies property 1. I can understand if it is hard to find any two distinct messages $m1$ and $m2$ for $H(m1)=H(m2)$ then it will be hard to find a distinct $m2$ for given $m1$ for $H(m1)=H(m2)$ (property 3 implies property 2). And if I have $m1$ and $H(m1)$ then from property 2 I can say it is hard to get $m2$ from $H(m2)$ if $H(m1)=H(m2)$, and as $H(m2)=H(m1)$ it is hard to get $m1$ from $H(m1)$ as well (property 2 implies property 1).

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

I am asking this because for $m1$ & $m2$ I will get $H(m1)$ & $H(m2)$ respectively and if $H(m1)$ & $H(m2)$ are correlated (not random) and I know $m1$ and $H(m1)$ (prior information) then from changes in output can I know easily changes in input thus know which input produces output? Putting slight differently is it possible to train a hash function from input and output if outputs are not seemingly random so that for given output I will know input?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are the "small changes" from uniformly random inputs? ​ If no, then it'll be quite hard to formalize a non-trivial concept like that. ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 15, 2017 at 20:56
  • $\begingroup$ You've got the implication the wrong way round. If the has is collision resistant, it necessarily has second pre-image resistance - but (for example) SHA1 appears to have second pre-image resistance but a collision has been found. $\endgroup$
    – Martin Bonner supports Monica
    Aug 18, 2017 at 8:50

2 Answers 2

Reset to default
2
$\begingroup$

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

No. Randomness is hard to test and it's easy to use any of the non-secure random number generators to generate random looking output. So anything that is "non-random" is certainly not irreversible because of just that.

Putting slight differently is it possible to train a hash function from input and output if outputs are not seemingly random so that for given output I will know input?

That's kind of the opposite. But if you just take $H'(x) = H(x) | 1$ then it should be clear that $H'(x)$ is as irreversible as $H(x)$, while the output is clearly not random.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hope I understood the question correctly, let me know if I got it backwards. $\endgroup$
    – Maarten Bodewes ♦
    Mar 15, 2017 at 18:38
  • $\begingroup$ so if anything is "random" then it will be irreversible? like I can't know which input generated that output or it will be hard to determine? $\endgroup$
    – user45051
    Mar 16, 2017 at 6:55
  • $\begingroup$ Or if a hash function that is used to search for similar (as opposed to equivalent) data are as continuous as possible then it will be easy for a third party to know the pattern of inputs/search for possible inputs. so if a cryptographic hash function doesn't output seemingly random number it will be easy to know which input generated the output? $\endgroup$
    – user45051
    Mar 16, 2017 at 6:57
  • $\begingroup$ and about the second part, I want to clarify that if I am given only H(m) then from H(m) only it will be hard to get back m, but if I am given some prior information (like a table of messages and their hashes), can I easily reverse engineer (i.e. machine learning algo) the function so that my trained function can now give the message m back from H(m). In my opinion, this condition of seemingly random output should imply irreversibility of hash function but not the other way around. $\endgroup$
    – user45051
    Mar 16, 2017 at 7:06
  • $\begingroup$ It seems to me that you only read what you want to read. You're indicating the exact opposite from what I state in the answer. $\endgroup$
    – Maarten Bodewes ♦
    Mar 16, 2017 at 9:52
0
$\begingroup$

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

I don't think so, if I understand the question correctly. There are a lot of reversible functions where $h(m)$ and $h(m+\delta)$ are uncorrelated. Something like $h(m) = m^e \mod pq$ should satisfy the requirement, but is reversible given $p$ and $q$.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.