# Why does Birthday attack work only with random messages and not with chosen messages?

Considering unkeyed hashing functions, I studied that the birthday attack can only work generating random messages and not with messages chosen from the attacker, but I didn't understand why. For example if there is a trade contract between two parties A and B where A states to sell a warehouse to B for 10.000 dollars, and the attacker (e.g. A) wants to modify this document and insert 100.000 instead of 10.000 dollars (I denote this document with D), why can A not generate a huge number of possible modified documents (for instance modifying space, dots, commas, etc. of D) and trying to find a collision between all possible modified documents and the original document?

• You will find a collision between two of your modified documents but you don't get to choose which. However the collision is useless if neither of those documents is the original one. It only works if you can generate them in advance, so that once you have your collision, then you can submit one of the colliding ones as the "original". Jan 17 '18 at 22:05
• The premise of this question is wrong. It doesn't matter what the messages are, as long as they are distinct. There are some super common misconceptions about hash functions, similar to this one, promoted across the web. It's unfortunate when someone learns from one of those sources. Especially since misconceptions are sort of viral. One person who learns some wrong info may one day teach multiple other people bad info. :-/ Mar 7 '20 at 20:09

Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired. I can prepare $2^{n/2}$ letters of the first kind and $2^{n/2}$ letters of the second kind, and then we expect there to be a collision between a message of the first kind with a message of the second kind. Note also that it's not hard to prepare such letters. All you need is a number of ways of replace enough words. For example, consider "[Mr. | Dr. | Prof.] [Yehuda | Y.] Lindell was employed as a [security | cryptography] consultant in our [company | organization]." This sentence can be written 3 x 2 x 2 x 2 =24 different ways (and this is just one short sentence).

I would also like to note that it's even possible to carry out a low memory birthday attack on meaningful messages. But, I'll leave working that out to you as an exercise.

For example if there is a trade contract between two parties A and B ... why can A not generate a huge number of possible modified documents (for instance modifying space, dots, commas, etc. of D) and trying to find a collision between all possible modified documents and the original document?

Whether the birthday attack applies depends on whether A can select the original document.

If he can, what he can do is generate $N$ versions of the document, generate $N$ versions of the evil document, and see which pair hashes to the same value. There are $N^2$ pairs, and so, with an $n$ bit hash function, there is a probability around $N^2 2^{-n}$ that there is a benign document and an evil document with the same hash. If there exists such a pair, he then presents the benign document for $B$ to agree to, and now he has the evil document with the same signature. Cryptographers call this attack a "collision attack"; as the attacker is looking for a "collision"; that is, two messages that hash to the same value.

On the other hand, if A has no control over the good document, this doesn't work. He can, of course, create $N$ evil documents and see if there is one with the same hash as the good one, however that will happen with probability $N 2^{-n}$, which is significantly smaller if $N$ is large (and we don't use the term "birthday attack" for this). Cryptographers call this attack a "second preimage attack", that is, find a second message that hashes to the same value as a given one. It appears to be a much harder attack to perform this a "collision attack".

Also, you stated:

Considering unkeyed hashing functions, I studied that the birthday attack can only work generating random messages and not with messages chosen from the attacker, but I didn't understand why.

Actually, when the attacker generates his messages during the attack, of course he can select those messages to make sense (and not just consist of random looking bits).

• ok, but collision attack is birthday attack? Does collision attack use the property of Birthday paradox? Jan 17 '18 at 17:42
• yes. If one of the colliding messages is fixed beforehand, you are attempting a "second-preimage attack" where the birthday paradox does not help you. Jan 17 '18 at 17:48
• ok, but If I have to consider the traditional birthday attack that uses the Birthday paradox, what is the classical scenario? If A knows the original contract, can A generate only a linear number of evil contract with respect to the number of authentication tags (I mean 1.774 |authentication tags|$^{1/2}$ considering the birthday paradox) and then having a probability greater than 50% to find a colliding pair (that is, one of the evil contracts generated may have the same authentication tag of the original contract)? Jan 17 '18 at 18:06
• @alex_the_great: the classic scenario with the birthday paradox is that A is able to generate a large number of original contracts, and select which one is actually signed. It sounds like that's not the scenario that you're talking about, and hence the birthday paradox doesn't really apply Jan 17 '18 at 18:26

No, the birthday attack cannot work when there is a set document which must be part of the collision.

The reason for this is one of the conditions of the Birthday Paradox. In the Birthday Paradox, we have a room of n people, and we want to know the probability that two people share a common birthday. It is very important to note that we do not care which two people share a birthday. Say you are in a room of n many people, and you all try and see if there are two people with a common birthday among you. The probability that you will find someone with the same birthday as yourself is n/365.25 (because of Feb 29 in a leap year). Similarly, the probability that someone shares the birthday with me is also n/365.25, as it is for each other person. The birthday paradox works when we count up the collective probabilities, and account for any double-ups in our counting, as explained here.

When we care about the specific person who has the same birthday, and ask "what is the probability that somebody shares a birthday with you?" we are limiting the number of comparisons made, and thereby limiting the probability of finding a match. In this case, the probability is only n/365.25.

Similarly, when we care about the specific date, and ask "what is the probability that somebody has a birthday on 4 July?", the probability is also n/365.25.

Now, in a collision attack, we do not care which two messages produce the same hash. We have a collection of messages, which may or may not be related, and we ask if there are two messages with the same output. This is just like asking if there are any two people with the same birthday. In this case, the Birthday Paradox applies, and we can use the birthday attack.

In a preimage attack, we are given a hash value H, and asked to find a message X which produces H as a hash value. This is just like asking "find me someone whose birthday is 4 July". The birthday paradox does not apply here, and hence the birthday attack does not apply.

In a second preimage attack, we given a message X, and asked to find a second message Y which produces the same hash value. This is just like asking "find me someone who has the same birthday as yourself". Because your birthday is fixed, there is only the probability that someone shares a birthday with you, or they don't. There is no collective counting going on as in the case of the Birthday Paradox, and therefore, the birthday attack does not apply to your situation.

Hope this helps!