Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 28

is, if you have a roomful of at least 23 people, then you have a pretty decent chance that there is at least one
repeated birthday. (This often works well when attempting to demonstrate the birthday paradox principle to the
said roomful of people.) Figure 2-3 shows a plot of the birthday paradox probabilities, giving a good idea of
how the probabilities increase with more samples (in our case, people's birthdays).

Figure 2-3 Plot of birthday paradox probabilities of at least one collision at up to 80 people. The function in-
creases very rapidly after the first few samples are taken, and hit above 50% at about the 23rd person.

We can use the birthday paradox as a tool to use against certain cryptographic algorithms. For example, we
may be concerned with finding two particular plaintexts that result in some certain bit pattern in some (or all) of
the ciphertext. If this is a bit pattern of n bits, we would normally have to acquire 2 n plaintexts and ciphertexts
in order to guarantee having the same ciphertext pattern twice. However, the birthday paradox tells us that, if
we store each of the pairs, we only have to look at about

ciphertexts to expect to find the pattern

twice. (We normally ignore the multiplicative constant in these cases.)
The next section expands one this idea for a certain class of algorithms.

2.1.4 Cryptographic Hashes
Let's discuss a very basic side effect that the birthday paradox has on hashing algorithms, such as MD5 and
SHA-1 [7, 8].
For starters, a hashing algorithm takes as input a (usually large) stream of data and produces a digest (also
called a checksum), which is some unique characteristic of that data. For example, the string all work and
no play , when transmitted using standard ASCII encoding of Latin characters, results in the transmitted bytes
(in hexadecimal):
61 6c 6c 20 77 6f 72 6b 20 61 6e 64 20 6e 6f 20 70 6c 61 79

Wecan calculate asimple checksum ofthis data byperforming normal integer addition ofeach byte together,
and taking only the least significant byte as the result (the last 8 bits). In the previous bytes, this checksum
would be 42.
What does this give us? Well, it's a condensed representation of some parts of the image, with the hope that
any other random message would have a different checksum. This way, if one person receiving a message knew