Is it possible to store N bits of unique combinations, in N-1 bits? If not; why does MD5 get reprimanded for collissions?

Question

Regarding cryptography and the issue of collisions, I posed a question as to whether it was ever possible to store every single possible combination of a bit array of a particular size, in a bit array that was at least one bit smaller, with apodictic certainty that no collision would occur.

The answer given to me by one fellow was no, and he used the following example:

Given 4 bits
0000
It has 16 possible combinations
Try storing 16 possible combinations in 3 bits:
000

While this was seemingly obvious on the smaller scale, I wonder that if you scaled up, whether this would remain true, given that more bits will offer far more flexibility and options ( and yet conversely you requiring more combinations to account for ). I have a hard time imagining it NOT remaining true, however perhaps there is something I am overlooking.

Working under the presumption that this is not possible; Why is it that md5 is reprimanded for generating collisions: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

When frankly given the principle, that literally no hash should be immune to this problem?

Answer 1

Of course, the pigeonhole principle states that colisions are inevitable for hashing algorithms.

The point of hashing algorithms is not to prevent colisions. But to make intentional collisions difficult.

An hashing algorithms becomes considered insecure when it becomes feasible to generate piece of data that results in specific hash. Or to extend piece of data to produce specific hash. Or to produe two pieces of different data which have the same hash. All of those cases are a collision vulnerability.

Answer 2

A hash function maps a larger (potentially infinite) input space into a smaller (usually finite) output space.

As a result, every hash function must have collisions. This is a consequence of the pigeonhole principle. The pigeonhole principle says that if you have number p of pigeons and a number h of pigeon holes, and p > h (i.e. you have more pigeons than pigeon holes), then there must be at least one hole with at least two pigeons in it.

I will not write out the proof for this (Software Engineering Stack Exchange doesn't support LaTeX in answers, unfortunately), but you can easily look up the proof on the web, or even prove it yourself. (A semi-formal proof is not that hard, it is a common high school homework assignment.) But you typically have an intuition for this, and you can try this out in your kitchen or in your office for example: if you have three drawers in your kitchen, take four knives and try to place them into the three drawers in a way that there are no drawers with more than one knife in it. You will quickly see it is impossible, and you can imagine how this scales up with more drawers and more knives. Another common real-life example are airplane seats: if an airline sells more tickets than they have seats, it will be impossible to seat all passengers.

Because the output of a hash function is smaller than its input, this means that there must be at least two inputs which hash to the same output. In fact, for most real-world hash functions, there are infinitely many possible inputs for every single output.

Another important mathematical result is the birthday paradox, which refers to the fact that the probability of collisions grows much faster than people intuitively think. The name comes from a famous problem in probability theory: how big is the probability of two people at a party having the same birthday? From the pigeonhole principle, we know that if there are 367 people at the party, it is absolutely guaranteed that two of them have the same birthday, since there are only 366 days in a year (including February, 29th).

However, it turns out that for as few as 23 people, the probability is already greater than 50%! 99.9% probability of a collision is already reached with 70 people.

However, the question is: are these collisions actually a problem? And if they are, how big of a problem are they? And how likely are they to occur?

We must remember that hash functions can be used for many different purposes.

One purpose hash functions are used for, is fingerprinting. In fingerprinting, we actually want collisions! We want different, but similar inputs to have the same output! For example, if we want to detect copyright violations on YouTube, different videos that contain the same song in different tempos and different keys should actually have the same fingerprint.

We typically do not think of these fingerprinting algorithms as hash functions, but they technically are.

Another category of hash functions are the ones which are used to implement data structures such as hash tables or hash sets. These hash functions include, for example, xxHash, CityHash, or MurmurHash.

For these use cases, collisions are typically not considered to be catastrophic: they don't break anything. They just affect the performance of the data structure. Because of this, historically, not much thought has been given about resistance to adversarial inputs. It was considered that if a hash function had a low probability of collisions for typical inputs, it would be good enough. It was generally assumed that the distribution of data would be essentially random, and that nobody would try to feed specially crafted data into one of these data structures.

This has changed recently, though, with the rise of network-connected applications, the Internet, and the World Wide Web. There was a string of Degradation-of-Service attacks on popular web frameworks in 2011–2014, which were enabled by almost all popular programming languages using weak hash functions in their standard libraries that were never designed to withstand targeted attacks with specially crafted adversarial inputs causing for example hash tables to degenerate into linked lists. Such attacks have now been termed Hash-DoS, and hash functions for hash tables, etc. are generally expected to be resistant against such attacks.

Next up, we have cryptographic hash functions such as MD2 MD4, MD5, MD6, SHA-1, SHA-2, SHA-3, BLAKE, BLAKE3, Skein, RIPEMD, GOST, Tiger, or Whirlpool.

For cryptographic hash functions, we are not only requiring that it should be improbable that hashes accidentally collide, but we also require that it is hard make them deliberately collide. In particular, the security properties, we expect from a modern cryptographic hash function are:

• pre-image resistance: it should be hard to find an input for a given output
• second pre-image resistance: it should be hard to find an input that produces the same output as another given input
• collision resistance: it should be hard to find two inputs that produce the same output
• chosen-prefix collision resistance: if I have two inputs, it should be hard to find a way to modify those inputs such that they produce the same output
• resistance against length extension attacks: a length extension attack allows an attacker to compute hash(message1 + message2) by knowing only hash(message1) and length(message1) for any message2 of their choosing, in other words, an attacker can concatenate arbitrary data to the end of the message and compute the new hash without knowing the original message
• pseudo-randomness: it should be hard to distinguish a pseudo-random number generator based on the hash function from a true random number generator
• avalanche property: any change to one bit of the input should change each output bit with 50% probability

In addition to the properties listed so far, all the hash functions mentioned so far (fingerprints, data hashes, cryptographic hashes) should be fast, don't use lots of memory, should be energy-efficient, and should be easy to implement for a wide variety of architectures.

For cryptographic hashes in particular, they should also be easy to implement without side-channels, they should be easy to implement efficiently in smart cards, microcontrollers, IoT devices, and embedded devices, they should be easy to implement efficiently in hardware, software, ASICs, and FPGAs. And they should be easy to speed up by throwing more resources at them, if needed.

Which brings us to the last category of hash functions: hash functions used for passwords such as Bcrypt, scrypt, PBKDF2, and the currently most recommended one Argon2. There are a couple of related categories: key stretching functions and key derivation functions.

These have an additional important requirement over those for cryptographic hash functions: Their input space is actually rather small, and some inputs are more likely than others. Typically, their inputs are passwords, and passwords are usually only between 6–10 characters long, they only use a subset of the values in the input space (ever seen a password that includes a newline or a backspace?), and they are not randomly distributed (passwords that are English words are more likely, passwords that contain characters which are clustered closely together on the keyboard are more likely, etc.)

This makes them susceptible to brute-force attacks (because of the small input space), dictionary attacks (a variant of a brute force attack where more likely candidates are tried first), and rainbow table attacks.

Because of that, password hashes should be slow. This might not be immediately obvious, but the basic idea is the following: if it takes ten seconds to verify a password, that is not very frustrating to a legitimate user, because you generally only log on to the system very infrequently. E.g. at work, you generally log on in the morning, and then again after lunch, and that's it. If that takes ten seconds, that's not really bad.

But an attacker performing a brute-force search, needs to try billions of passwords. If each of those tries takes ten seconds, it takes the attacker thousands of years to crack a password! Over the years, we have added ever more requirements: a password hash should not only be slow when implemented in software on common CPUs, it should also be impossible to speed up using more resources, more memory, GPUs, parallelism, ASICs, FPGAs, or any combination. And it should be easy to tune the resources based on the desired security level.

In your question, you ask about MD5 being reprimanded. I am not familiar with that term. The two terms I am used to hearing are broken and insecure.

Insecure does not have a formal, mathematical, or technical definition. It is more a social definition. It means that the cryptographic community as a whole thinks that using this algorithm is no longer a good idea. This could be based on different reasons. One reason could be that the algorithm is broken. Or that its source is no longer trusted. (Imagine it became public that one of the authors' children was abducted by an organized crime syndicate during the time the algorithm was designed.) Or that the increase in performance simply has outpaced an older algorithm.

Broken has a more specific, precisely defined meaning: it means that there exists an attack that is faster than brute force. (Or faster than a birthday attack for collision resistance.) In other words, if I can find a collision faster than simply trying all possible inputs, then the algorithm is considered to be broken.

Note that this does not necessarily mean that it is practically unusable: if a brute force search takes a quintillion quintillion quintillion quintillion quintillion years, and I find a way to speed that up by a factor of 1000 to a quadrillion quintillion quintillion quintillion quintillion years, then the algorithm is considered broken nonetheless, but it is not practically useless.

The important concept here is the concept of feasibility: an attack is considered feasible if it can be performed by a competent attacker with reasonable resources in a reasonable amount of time. An attack can become feasible either by computers becoming cheaper and faster, or by an algorithm being broken, or a combination of both.

Algorithms for which a feasible attack exists are definitely also considered insecure.

However, typically, as soon as an attack exists, even if it is completely infeasible at the moment, cryptographers start looking for a replacement. The reason is that history has shown that as soon as one attack is published, more and more attacks follow. Either someone improves the attack, or someone uses techniques from the attack in a new attack, or someone who was working on an attack that didn't quite work out finds some new ideas in the attack, or it could just be that as soon as people know the algorithm is vulnerable, they throw more resources at it. Either way, historically, the very first attack against an algorithm was typically followed by a flurry of further attacks.

Therefore, even if the first published attack is completely infeasible, it won't take long until the algorithm is considered insecure.

So, let's look at MD5.

MD5 is considered broken with respect to pre-image resistance because there exists an attack with complexity 2^123.4 which is faster than brute force (2¹²⁸). This is, however, not a feasible attack. It would still take quadrillions of years.

It is feasible, however, to crack MD5 hashed passwords, not because of this attack but because of the increase in hashing performance and the limited size and entropy of passwords. Cracking a password can be done in minutes.

MD5 is completely broken with respect to collision resistance (2¹⁸) and chosen-prefix collision resistance (2³⁹). This means you can find a collision within seconds even on a middle-class laptop from 2000. A GeForce 8800 from 2006 can find hundreds of collisions per second. This is not just feasible, this is trivial.

In addition to all of the above, MD5 is also vulnerable to a length extension attack.

Answer 3

Cryptographic hashing will for example produce a 256 bit hashcode. If the hashed data is more than 256 bits, then collisions are unavoidable. Now try to find a collision, and you run into a problem. You'll have to hash about 2^128 items to find two that have the same hashcode, if they hashcode is random. And you'd have to remember these 2^128 hashcodes to detect there's a collision; a collision that cannot be detected is as good as no collision.

In cryptography, you would run into a problem if I am capable of deliberately creating two different strings with the same hash code. Even worse, if given an arbitrary string, I can create one with the same hashcode. I can only do that in theory, but not in practice.

Question: If you give everyone on earth a camera, 7 billion, and everyone takes a photo every second, 24/7, and good 256 bit hashcodes are created of every photo, how long until there are two photos taken with the same hashcode? Answer: Too long to worry about it.