Paradoxes and the Birthday Attack

July 14, 2013
math cryptography

If Pinocchio says, “My nose will grow now”, what will happen? Think about this carefully and you’ll soon come to realise that you cannot come to a definitive conclusion. If he is telling the truth his nose will not grow, but if his nose does not grow then he is lying and his nose will grow, in which case he was telling the truth. Herein lies a paradox, and for centuries the world’s greatest minds have mentally wrestled with them! I find them fascinating due to the mental anguish they can put you through (I love a challenge) and due to the fact that they can often lead to conclusion you’d think unlikely. So let’s delve into the vast realm of paradoxes!

What is a Paradox?

So what exactly is a paradox? A paradox is:

A seemingly absurd or self-contradictory statement or proposition that when investigated or explained may prove to be well founded or true.

It may take the form of a question, a proposition, an image or other media. In the book, Vicious Circles and Infinity: An Anthology of Paradoxes, Patrick Hughes and George Brecht state that the three descriptive terms which can be used to identify a paradox.

  1. Self reference — There are many propositions which are self-referring, however, on their own there is nothing paradoxical about them, e.g. “This is a sentence”
  2. Contradiction — We expand on rule number one and encompass contradiction into our definition, for example consider the image: Contradiction Paradox This is paradoxical but Hughes and Brecht say this is in a class of “not quite paradoxes”. In order to be a member of the paradox class requires item number three.
  3. Vicious Circularity — Now examine the following, “This statement is false”. If the statement is true, then the statement is false, thus making the statement true. Notice how both this example and Pinocchio’s predicament continually loop in a circle.

Types of Paradox

In, The Ways of Paradox and Other Essays, W.V. Quine distinguishes three classes of paradoxes

  1. Veridical paradoxes are shown to be true despite sounding crazy;
  2. Falsidical paradoxes appear to be false and are shown to false; and
  3. Antinomy paradoxes appear in none of the classes above, and a self-contradictory result is reached through accepted ways of reasoning.

Where are Paradoxes Found?

So now we have a better understanding of what makes up a paradox, but in what fields are paradoxes found? Amazingly paradoxes can be found everywhere. The list of well known paradoxes is vast and spans many different subject areas including:

  • Probability: Montey Hall Paradox:
  • Logic: Socratic paradox “I know that I know nothing at all”;
  • Statistics: Friendship Paradox “Most people’s friends have more friends than they do”;
  • Time: Grandfather Paradox:

The list is large, and spans Biology, Physics, Chemistry, Economics, Politics and History. If you’re interested check out the Wikipedia page which gives an extensive collection!

Now let us consider a specific example of something with a paradoxical nature I stumbled across the other day.

The Birthday Paradox

If there are 23 people in a room, there is a 50% chance that two of them will share a birthday!

This marvel has a name and is known as the Birthday Paradox. It belongs to the Veridical paradoxes class and like many people I initially didn’t believe the claim and had to investigate it further.

The reason for this startling result is quite simple. In day to day life we are used to comparing ourselves to others. The probability of having the same birthday as one other person is 1365 (~0.27%), and if we were to compare our birthday with 23 people we would have 23365 (~6%). This is still a low probability and so we would conclude it is rare to meet someone with the same birthday as our own. However, when you put 23 people in a room and ask them to compare their birthdays with one another we dramatically increase the chance of getting two people sharing a birthday.

In order to calculate the exact probability consider a large wall calendar with 365 empty spaces. The first person in the rooms comes along and places a mark on the wall calendar for when their birthday occurs, they have 365 days to choose from. The next person to walk in only has 364 spaces to place a mark without causing a collision, the third person only has 363 days to place a mark without causing a collision, and so on. If we multiply the probability of each of the 23 people not colliding, i.e. having different birthdays, we get:

$$ \frac{365}{365} \times \frac{364}{365} \times \ldots \times \frac{343}{365} $$

This is the probability of the birthdays not colliding, if we want to determine the probability of people sharing a birthday we subtract this result from 1:

$$ p(23) = 1 - \frac{365}{365} \times \frac{364}{365} \times \ldots \times \frac{343}{365} $$

If we calculate \(p(23)\) we get:

$$ p(23) = 0.5073 $$

Shocking isn’t it. There’s a 50% chance that in a room of 23 people, two people share a birthday! Now let’s generalise. The probability of a person sharing a birthday given a room of \( n \) people is:

$$ p(n) = 1 - \frac{365!}{365^n (365 - n)!} $$

Due to my interest in computer security, let’s link the Birthday Paradox to cryptography.

The Birthday Attack

The reason that the Birthday Paradox is interesting is that it is useful in many different computing fields, including cryptography and hashing algorithms.

For example, assume that we are given a hash function, \( f \). Our aim is to find two inputs, \( x_1 \) and \( x_2 \), such that \( f(x_1) = f(x_2) \). This is known as a collision. In order to find a collision we simply evaluate the function for different randomly chosen input values, until we find a result more than once. Using a method similar to that described in the Birthday Paradox allows this method to be rather efficient.

Consider the function \( f(x) \), which has \( H \) possible outputs. Each of these outputs has equal probability and we want \( H \) to be sufficiently large. We expect to obtain inputs \( x_1 \) and \( x_2 \) such that \( f(x_1) = f(x_2) \) after evaluating the function for \( 1.25 \sqrt{H} \) different arguments on average.

Okay so let us consider a hash of 128-bits. This will yield approximately \( 3.4 \times 10^{38} \) different outputs. If we assume that each of these outputs is just as likely, then it will take approximately \( 2.2 \times 10^{19} \) attempts (known as the birthday bound) to generate a collision using brute force.

So how is this actually applicable to computer security and cryptography? Think digital signatures. A digital signature is “A digital code that can be attached to an electronically transmitted message that uniquely identifies the sender” and most crucially it is susceptible to the birthday attack. Typically Alice will have a message \( m \) which she signs by computing \( f(m) \) where \( f \) is a cryptographic hash function. She would then normally use a secret key to sign \( f(m) \).

Suppose that Trudy wishes to get Bob to sign a fraudulent contract. In order to accomplish her malicious goal, she prepares two contracts, \( m_1 \) and \( m_2 \). She makes a huge number of multiple copies of \( m_1 \) by finding ways in which she can alter the contract without changing its meaning. For example she may go about using a combination of adding extra punctuation, abbreviating words, including extra lines, etc. Trudy also goes about making a number of copies of the fraudulent contract \( m_2 \). Now the clever part occurs. She runs the cryptographic hash function, \( f \), on all copies of \( m_1 \) and \( m_2 \) until she finds a version of the fair contract and fraudulent contract which have the same hash value. Sneaky Trudy now presents the fair version of the contract to Bob to sign, with which she takes the signature and attaches it to the fraudulent contract. We now have ‘proof’ that Bob signed the fraudulent contract!!

While the probabilities of this attack are slightly different to that of the Birthday Paradox (we gain nothing by finding hash collision of two fair contracts or fraudulent contracts) it is still entirely feasible assuming the output length of the hash function is small. In order to avoid this type of attack we need to ensure the output length of the hash function used for a digital signature is large enough such that performing a Birthday Attack becomes computationally infeasible.

So there’s a brief introduction to Paradoxes and the Birthday Attack. I hope I’ve opened your eyes into the awe inspiring world of paradoxes, and have managed to teach you something new along the way.