2
$\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?

$\endgroup$
  • $\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 '17 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 Aug 18 '17 at 8:50
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.

$\endgroup$
  • $\begingroup$ Hope I understood the question correctly, let me know if I got it backwards. $\endgroup$ – Maarten Bodewes Mar 15 '17 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 '17 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 '17 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 '17 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 '17 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$.

$\endgroup$

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.