Are ideal hashes possible to create?

In a hash function, you map an input of arbitrary length to an output of finite length such that the relationship is one-to-one (or at least that's what you are trying to achieve).

Hence, isn't it impossible to have a perfect hashing algorithm? Aren't MD5, SHA-*, all flawed in this respect?

Is an "ideal hash" impossible to achieve?

-

migrated from stackoverflow.comDec 13 '13 at 6:13

This question came from our site for professional and enthusiast programmers.

If your definition of "ideal hash" is that it has no collisions with an input larger than the output, that's impossible. Pigeonhole principle – CodesInChaos Nov 29 '13 at 11:21
An ideal hash function would not be injective, since this is impossible. With an infinite domain and finite range, the best possible to achieve is a uniform distribution. In this regard, have a look at universal hashing – tylo Dec 13 '13 at 12:47

Of course, since the domain of a hash function is infinite and its range is finite, it cannot possibly be injective, i.e. there is at least one hash with more than one string that is being mapped to it. This is called the pigeonhole argument: if the domain of a function is larger than the set that it maps to, at least two values are mapped to the same thing. (In fact, one can even show quite easily that in the case of infinite domain v finite range there is one hash that has infinitely many input strings associated to it)

So injectivity, or “uniqueness”, if you will, is, of course, a goal one cannot possibly hope to achieve for a hash function. If that is what you call an “ideal hash function”, then that is doomed to fail.

So what can we hope to have in a hash function? There are a number of properties that hash functions should have. A common way to define these properties is to state that certain problems concerning the hash function should be computatinally hard, such as:

• Collision resistance: it should be difficult to find a collision of the hash function f, i.e. to obtain two different values x₁, x₂ such that f(x₁) = f(x₂)
• Second-preimage resistance: for any value, it should be difficult to find another value with the same hash. Formally: for any x₁, it should be difficult to find an x₂ such that f(x₁) = f(x₂)
• Preimage resistance: given a hash, it should be difficult to find a message that has that hash. Formally, given y and some x₁ with f(x₁)=y, it should be difficult to obtain x₂ with f(x₂)=y

(There is also the related notion of a universal one-way hash function, but I shall not explain it here.)

It can be seen that collision resistance implies second-preimage resistance and that again implies preimage resistance. Now, do SHA and MD5 have these properties? Well, nobody really knows. The problem in cryptography is that it is very difficult to prove that a cryptographic scheme is correct. There are many relative security results, i.e. “Scheme A is secure if some assumption holds”, but the only cryptographic scheme that is proven to be secure is the One Time Pad.

In particular, it is not even known whether things such as “safe” (practical, i.e. not OTP) ciphers, good hash functions and so on exist in the first place – essentially, if the (still unresolved) P = NP? question has a positive result, i.e. P = NP, all these ciphers and hash functions are basically worthless.

However, it is widely thought that P does, in fact, not equal NP. Cryptographic primitives such as hash functions and ciphers are designed by people who are very knowledgeable in this area and have to withstand many attempts to break them before they are tentatively declared probably secure.

To come back to MD5, there are a lot of papers that describe efficient attacks on MD5. MD5 is definitely not collision-resistant. SHA-2 still seems to be quite good. But generally, the natural progression is that as hash functions grow older, more flaws and corresponding new attacks are discovered and they are gradually replaced by new hash functions, which were developed with the lessons learnt from the flaws of the old ones in mind.

I just realised this post got a lot longer and more detailed than I had initially planned; nevertheless, I hope it answers your question.

-