1
$\begingroup$

One-way property: computationally infeasible to find data mapping to specific hash

The definition above is a little vague, if we have h(x) = floor(log(x)), finding "some" x that gives a hash value is easy, however, deterministically finding the actual x value that has led to the output is impossible. Do such hash functions have the one-way property?

$\endgroup$
  • $\begingroup$ The definition you quote is more than a little vague. You will find correct definitions in any good crypto textbook. $\endgroup$ – fkraiem Sep 17 '18 at 11:52
  • $\begingroup$ You mean, Pre-image resistance : computationally infeasible to find the reverse image of a given hash value. $\endgroup$ – kelalaka Sep 17 '18 at 12:12
1
$\begingroup$

If you can find “some” value, mapping to a specific hash, that would mean it’s not really a one-way hash function.

$\endgroup$
2
$\begingroup$

Your function is too easy. Given an hash value $h$, calculate $b^h$ and $b^{h+1}-1$, where b is the base of your logarithm.

Any value between $b^h$ and $b^{h+1}-1$ will be pre-image.

$\endgroup$
  • 1
    $\begingroup$ Yes. Thus $x\to h(x)=\left\lfloor\log_b(x)\right\rfloor$ is not one way, because it is computationally feasible to find data mapping to a specific hash. The question's definition is correct, if a little imprecise. $\endgroup$ – fgrieu Sep 17 '18 at 12:19
  • $\begingroup$ Yes, it is easy. I just wanted to give an example of something that is reversible, but not uniquely. The question is if the attacker is lost among a large number of candidates, is it still a one-way function? $\endgroup$ – Farzad Vertigo Sep 17 '18 at 12:38
  • $\begingroup$ He is no lost, all of the values are correct in the sense of the attacker, even for you. Think about the usual hash based password protection. All of the pre-images are valid passwords to login. $\endgroup$ – kelalaka Sep 17 '18 at 12:49

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.