# Proving a function is one way hash function

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.

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.

• Thanks for the answer, very well explained, I got it,what i exactly have to prove now Jul 5, 2016 at 1:40

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?

• 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. Jul 5, 2016 at 1:42
• @ArjunLondhey: is there any specific reason you aren't using a standard cryptographical hash function, such as SHA-2? Jul 5, 2016 at 3:21
• 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. Jul 5, 2016 at 3:32
• Sir, can you give me some examples of one-way function that I can use other than standard (MD5,SHA) algorithms. Jul 5, 2016 at 5:02