1

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.

3

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 2128 possible outputs) and use a random oracle to hash significantly more than sqrt(2128) = 264 inputs, it begins to become overwhelmingly probable that there will be collisions. On the other hand, if you hash significantly fewer than 264 inputs, it will be very unlikely to have a collision if you started with an ideal random oracle. (If you hash around 264 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 272 possible 9-byte inputs the probability of a random oracle being injective onto a 16-byte space is about exp(-n2/2m) ≈ 10-14231, where n = 272 ≈ 4.7 x 1021 and m = 2128 ≈ 3.4 x 1038. 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 256 of them so with large probability there will be no collisions (that is it will be injective). As this is significantly less than sqrt(2128), 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.

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 2128 inputs to MD5 and see for yourself if there are any collisions, but you would need about 1027 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 2256 inputs to unique outputs, but what about the 2256 + 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).

  • 1
    Minor pedantic point, most cryptographic hash functions are defined with a maximum input length. E.g., md5, sha-1, sha-256 should not accept an input message with more than 2^64 - 1 bits ~ 2.3 million terabytes (so in practice arbitrary length as you said as practical hash inputs are smaller). (sha512 allows 2^128 - 1 bits as input; and sha-3 doesn't have a max input length). See: en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functions (And your argument stands if you allow 257 = 2^8 + 1 bits as input as the pigeonhole principle can show there is at least one collision). – dr jimbob Mar 8 '16 at 19:33
  • I actually didn't know that, thanks. So "... take an effectively arbitrary length input". I think I'll leave the answer as is. – Mike Ounsworth Mar 8 '16 at 19:35
  • The maximum length is mostly because hashing messages above that length with this type of hash is impracticable without some hash function that allows for parallelization. (Things of 2^64 bits is roughly the order of magnitude of facebook or google's total storage in all their datacenters.) The reason is one step of the hash function requires using the length of the message (so if the storing the length requires more than 64/128 bits it could become undefined how to extend; though you could simply take the low-order bits of the length to extend the algorithms to arbitrary length). – dr jimbob Mar 8 '16 at 19:45
  • lol, you must be a theoretician - "I'll just hash the internet with MD5 now, this shouldn't take too long". – Mike Ounsworth Mar 8 '16 at 19:50
  • @MikeOunsworth, 2^64 operations is considered feasible given enough ressources. It wouldn't be cheap, but it would certainly be possible (i.e. rent a whole {EC2;Azure;Google Compute Cloud} data center and wait maybe a year) – SEJPM Mar 8 '16 at 20:22
0

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.

  • 1
    Hashes are used for a lot more than just integrity verification. – Someone Somewhere Mar 8 '16 at 20:12
  • I said "generally used" – Cricco95 Mar 8 '16 at 20:36
  • Every SSL/TLS connection uses a hash to generate keys, as does connecting to a WiFi connection with WPA/WPA2, or logging into any service with hashed passwords (windows account, any online account built right), or practically anything. I expect there are far more passwords hashed or TLS connections started than times people verify file integrity. – Someone Somewhere Mar 8 '16 at 20:42
  • @Cricco95 I am aware of what collisions are. Please note what conditions I have placed upon m1 and m2 in my question. – Tyzoid Mar 8 '16 at 22:01

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.