3
$\begingroup$

I am working on a project which computes the hash of the given input, I have to prove that the function is pre-image resistant that is given an output we cannot get back to the input.

While proving the function to be pre-image resistant. The function that I am using has a property that for every output there are more than one possible input. In other words, I have proved my function is many to one function. Is it sufficient to show that we cannot calculate the inverse of the function because it is a many to one function and not a one-one function.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The inverse cannot be calculated, you're right. However, in can be guessed.

In many scenarios, for example cracking hashed password, it's enough for the attacker to know a set of possible inputs which result in certain output (of course if their number is reliable) instead of one certain value.

So if the one-to-many function is weak, given the output $y$ the attacker can calculate $x_1,x_2,...,x_n$ such that for each $x_i$ $H(x_i)=y$ and try them one by one.

Concluding - it's not enough to show that it's one-to-many function. You must also show that finding the set mentioned above is computationaly hard for your function.

PS. You might wonder why $n$ can't be so big that trying all possible inputs resulting in a certain output will be impossible. This would cause another weakness - low collision resistance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer, very well explained, I got it,what i exactly have to prove now $\endgroup$
    – Arjun Londhey
    Jul 5, 2016 at 1:40
2
$\begingroup$

Is it sufficient to show that we cannot calculate the inverse of the function because it is a many to one function and not a one-one function.

It would depend on what you need your function for, but by the standard definition of pre-image resistant, no, it's not sufficient. In the standard definition, it must be infeasible, given $x$, to find any $y$ such that $H(y) = x$; it need not be the specific $y$ that you had in mind.

Also.

I have to prove that the function is pre-image resistant that is given an output we cannot get back to the input.

It depends on what you mean by proof; however if you mean "proof it mathematically without making any unproven assumptions about the difficulty of an underlying problem", we currently cannot prove that any specific function is pre-image resistant. In fact, we can't even prove that there exists a pre-image resistant efficiently computable function. So, we either:

  • Rely on a function that we can prove is secure assuming some underlying problem (such as factoring) is hard, or

  • Rely on a function that we have no proof for, but has been studied by clever people, and they couldn't find anything.

(For hash functions, #2 is far more common).

BTW: if you were able to prove that every output has multiple possible preimages; that implies some mathematical symmetry to the function; is it possible that that symmetry could be used to find preimages?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the reply sir,Actually i am trying to design my own hash function using genetic algorithm.Until now I have only proved my function to be many-to-ne function,but now I guess I have to prove that getting the possible inputs is also hard. $\endgroup$
    – Arjun Londhey
    Jul 5, 2016 at 1:42
  • $\begingroup$ @ArjunLondhey: is there any specific reason you aren't using a standard cryptographical hash function, such as SHA-2? $\endgroup$
    – poncho
    Jul 5, 2016 at 3:21
  • $\begingroup$ Sir, I am doing a research course in cryptography where I am trying to propose a method where we can use genetic algorithm to produce hash output which is faster than existing method.It is in initial stage right now. $\endgroup$
    – Arjun Londhey
    Jul 5, 2016 at 3:32
  • $\begingroup$ Sir, can you give me some examples of one-way function that I can use other than standard (MD5,SHA) algorithms. $\endgroup$
    – Arjun Londhey
    Jul 5, 2016 at 5:02

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.