Are hashing functions designed to be injective where the domain is limited to the codomain?

Question

Using the example of md5, I would like to know if

md5(h₀) == md5(h₁)

for some distinct md5 hashes h₀, h₁.

Are hashing algorithms generally designed to avoid this sort of collision? Do MD5, SHA1, SHA2, etc. behave differently in this regard?

Update:

I believe that I may not have been clear enough.

Given that md5 has only 16 bytes of output, Let's say I restrict my input only to binary strings of exactly 16 bytes in length, so that every h₀, h₁ is a potential output of md5 itself.

In the context of other hashing algorithms, let their corresponding hash lengths be used instead.

The question still remains.

Answer 1

As to your update, your standard cryptographic hash functions (MD5, SHA-1, SHA-2 family, SHA-3) try to approximate random oracles (and do not attempt to be injective). That is they attempt to map any input to an output chosen uniformly at random in your output space (and do this mapping consistently). With overwhelming probability, random oracles will not be injective when the number of possible inputs is significantly larger than the square root of the number of possible outputs, due to the birthday paradox.

For example, if you have a 128-bit hash output (a 16-byte hash with 2¹²⁸ possible outputs) and use a random oracle to hash significantly more than sqrt(2¹²⁸) = 2⁶⁴ inputs, it begins to become overwhelmingly probable that there will be collisions. On the other hand, if you hash significantly fewer than 2⁶⁴ inputs, it will be very unlikely to have a collision if you started with an ideal random oracle. (If you hash around 2⁶⁴ inputs than the chance of being injective is approximately 1/2; there may be a collision or not).

As a specific example, if you hash all 2⁷² possible 9-byte inputs the probability of a random oracle being injective onto a 16-byte space is about exp(-n^2/2m) ≈ 10^-14231, where n = 2⁷² ≈ 4.7 x 10²¹ and m = 2¹²⁸ ≈ 3.4 x 10³⁸. This is incredibly unlikely; roughly equivalent to playing powerball (odds of winning 1 in 292 million) twice a week for 16 years and winning the jackpot each and every time with no losing tickets. And again, this is only for a 9-byte input; with a 15-byte input the probability of being injective is about 10^{-1127492937032632506267955467381579}!

Meanwhile, if you hash all possible 7-byte inputs, there's only 2⁵⁶ of them so with large probability there will be no collisions (that is it will be injective). As this is significantly less than sqrt(2¹²⁸), a random oracle would not be injective with probability with odds of 0.0000076 (about 1 in 130 000 times it would not be injective and the rest of the time it would be injective).

See the probability table on wikipedia for more information.

Granted this is not a proof for any specific hash function; to prove it we would have to generate a specific collision within the input space which would in general is difficult to show.

---

Now if you need an injective function that acts similar to a hash, this is quite simple to achieve by using a block cipher (formally known as a pseudorandom permutation) like AES and choose a random key to encrypt it with. Block ciphers are necessarily both injective and surjective. If a block cipher was not injective, then a person with the key and the decryption function and a block of ciphertext to decrypt with couldn't possibly recover the original block.

The downside of using a block cipher instead of a hash function is that the block cipher requires input of just one fixed length and transforms it into output of the same fixed length. For example, AES can only take a input that is 128-bit and transform it into a 128-bit output. (Yes you could use block cipher modes to transform larger inputs, but still for it to be one-to-one the output size would be the same length as the input). The fact that a hash function can take variable sized inputs and output a fixed size hash makes it ideal for many purposes. The fact that this requirement of hashes to map variable sized inputs taken from a very large input space into a smaller output space means that it will not be a injective by the pigeonhole principle is usually not a problem in practice.

Answer 2

Update:

Still no. Even if you restrict your input space to be the same size as (or smaller than) the output space, there is no guarantee or formal proof that a given hash function will be collision-free (at least, no proof that I'm aware of).

Part of the reason we like cryptographic hash functions is that, as far as we know, they have no discernible patterns. This is a double-edged sword making it almost impossible to make any mathematical analysis of them (and if we could, we would declare them weak and move to something more complex).

You could, I suppose, write a program to check all 2¹²⁸ inputs to MD5 and see for yourself if there are any collisions, but you would need about 10²⁷ 1 terabyte hard drives just to store the lookup table to know when you get a collision.

---

Previous answer

Generally speaking, no hash functions are not injective; they make no guarantees about being collision-free.

All standard hash functions (including the ones you mentioned) take an arbitrary length input and produce a fixed-length output. Take for example SHA-256 with a 256-bit output, I could map the first 2²⁵⁶ inputs to unique outputs, but what about the 2²⁵⁶ + 1 th inupt? It has to collide with something that's already been mapped to - this is known as the Pigeonhole Principle.

More formally, any function whose domain (input space) is larger than its range (output space) can not possibly be injective.

---

As far as I know, the main reason that MD5 was deprecated for cryptographic use is that we know about several pairs of short (128-bit) strings that produce collisions under MD5. See MD5 Collision Demo.

As far as I know, there are no known collisions for any hash in the SHA family (though theoretically we know they must exist by the pigeonhole principle).

---

Aside: This is outside the scope of your question, for interest I'll mention that it's on open problem as to whether hashes in the SHA family are surjective (ie whether every possible output is actually mapped to, or whether there are gaps).

Answer 3

Hash functions are generally used to check the integrity of datas. They allow an user to verify that some input data maps to a given hash value, but if the input data is unknown, it is impossible to reconstruct it by knowing the stored hash value. In a few words I can generate a string which identify a certain type of data with an hash function. Is it possible to generate two equals hashes from two different inputs? The answer is yes, but it is so rare. This situation is called collision. Collisions happen when, members of a very large set (such as all possible computer files) are mapped to a relatively short bit string. Mathematically stated, a collision attack finds two different messages m1 and m2, such that hash(m1) = hash(m2). This is an MD5 collision attack demonstration where the same hash is generated from two different executable files. Another example is the SHA1 hash function which has been substituted with SHA-2 which has less probability to be exploited with a collision attack.