ńņš. 7 |

A(i) A(i) [1] A(i+1) A(i+2) A(i+3) A(i+4) A(i+5)

B (i+1) [1]

B (i)

Initial C (i+1) [31]

C (i)

state

D(i+1) [31]

D(i)

E (i+1) [31]

E (i)

Figure 5.1: Propagation of diļ¬erences in a local collision of SHA

these local collisions act on the same bit position with the words W . Let j

denote this bit position. Clearly, according to our previous description of the

local collisions, all in all, three bit positions are involved in the changes and

correction, namely j, j + 5 and j ā’ 2, where bit positions are numbered from 0

to 31 and considered modulo 32. Due to the parallel nature of the expansion,

an expanded bit sequence can be moved around from one bit position to an-

other without any diļ¬culty. However, the construction of local collisions does

not only require to move bit sequence between bit position but also to shift

them between word position. For example, a change on W (i) leads to a ļ¬rst

correction on W (i+1) . Here, we encounter a possible diļ¬culty. Indeed, noth-

ing guarantees that an expanded sequence of bits remains a valid expanded

sequence if we shift it in this way. For example, the sequence:

0000000000000001

0010010110010010

0110110000110001

1101011111011010

0001000010110100

cannot be shifted in that way. Indeed, in order to obey the expansion formula,

it would need to become:

1000000000000000

1001001011001001

0011011000011000

1110101111101101

0000100001011010

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 171

with a one at the beginning. However, half of the possible sequences can

be shifted without problems. In fact, in order to perform the ļ¬ve necessary

corrections, the chosen sequence of changes needs to be shifted 5 times. This

is possible for a fraction 1/32 of expanded bit sequences. An easy way to

formalize this is to run the expansion backward and to require that the ļ¬ve

bits in the negative position are zeros. Equivalently, this adds ļ¬ve linear

conditions on the 16 input bits of the expansion.

For any such sequence of bits, putting together the corresponding local col-

lisions gives an interesting diļ¬erential pattern for linearized SHA-0. However,

this pattern need not be a collision. Indeed, if a local collision starts in one of

the 5 last rounds, it cannot be canceled in time. In that case, we only obtain

a pseudo-collision. To get a collision for linearized SHA-0, an additional

constraint is needed. There should be no local collision remaining active in

the ļ¬nal round, thus we need to choose the local collision positions according

to a sequence of bits with ļ¬ve zeros in the ļ¬ve last positions. To satisfy this,

we need to add ļ¬ve more linear conditions.

When we enforce the conditions of having ļ¬ve zeros in the negative positions

and ļ¬ve in the ļ¬nal positions, there remain 63 non-zero bit sequences that

can be used to introduce local collisions in a way that is consistent with

the message expansion. Some of these possible sequences are described in

Table 5.16; the complete table is available on the bookā™s website.

Let Ī“ be any sequence on 80 bits from Table 5.16. Denote by Ī“ (i) the i-th

bit of Ī“, with the convention that the sequence in the table are numbered from

0 to 79. In addition, when i is a negative integer from ā’5 to ā’1, let Ī“ (i) = 0.

Given Ī“ together with a bit position j, we can construct an 16-word vector ā

in the kernel of the linearized SHA-0 by letting:

ā(i) = ROLj (Ī“ (i) ) ā• ROLj+5 (Ī“ (iā’1) ) ā• ROLj (Ī“ (iā’2) ) ā• ROLjā’2 (Ī“ (iā’3) ) ā•

ROLjā’2 (Ī“ (iā’4) ) ā• ROLjā’2 (Ī“ (iā’5) ), for all 0 ā¤ i ā¤ 15. (5.9)

Due to the care we took to construct ā, Equation 5.9 also holds after expan-

sion for ā(i) with 16 ā¤ i ā¤ 79. It is clear that for any 16-word message W ,

the linearized SHA-0 hashes of W and W ā• ā form a collision.

5.4.3 Adding non-linearity

Once the linear algebra collision attack on linearized SHA-0 is written in the

sparse form of Section 5.4.2, we can try to use it as a probabilistic collision

attack on the real SHA-0 hash algorithm. As before, given a sequence of 80

bits Ī“ from Table 5.16 and a bit position j, we construct a vector ā and then

consider pairs of messages (W, W ā•ā). For such a pair, a collision may occur in

two diļ¬erent ways. It may occur by wild chance after two extremely diļ¬erent

computations or it may result from a nice case where the two computations

follow essentially the same relationship as in the linearized case. The ļ¬rst

type of collision is not interesting for us because we do not get any control

Ā© 2009 by Taylor and Francis Group, LLC

172 Algorithmic Cryptanalysis

00010000000100100000001000011011011111101101001000010101001010100010111001100000

00100010000000101111011000111000000101000100010010010011101100110000111110000000

00110010000100001111010000100011011010101001011010000110100110010010000111100000

10100101000001111100111100110001111111011011110000110001010101110100101000000000

10110101000101011100110100101010100000110110111000100100011111010110010001100000

10000111000001010011100100001001111010011111100010100010111001000100010110000000

10010111000101110011101100010010100101110010101010110111110011100110101111100000

01100000100100110001001110111011100101000100100010011110001100101000010011100000

01110000100000010001000110100000111010101001101010001011000110001010101010000000

01000010100100011110010110000011100000000000110000001101100000011000101101100000

01010010100000111110011110011000111111101101111000011000101010111010010100000000

11000101100101001101110010001010011010011111010010101111011001011100111011100000

11010101100001101101111010010001000101110010011010111010010011111110000010000000

11100111100101100010101010110010011111011011000000111100110101101100000101100000

11110111100001000010100010101001000000110110001000101001111111001110111100000000

10001100010001100011110011111101100000101101001100111101000000101001100010000000

10011100010101000011111011100110111111000000000100101000001010001011011011100000

10101110010001001100101011000101100101101001011110101110101100011001011100000000

10111110010101101100100011011110111010000100010110111011100110111011100101100000

00101001010000011111001111001100011111110110111100001100010101011101001010000000

00111001010100111111000111010111000000011011110100011001011111111111110011100000

00001011010000110000010111110100011010110010101110011111111001101101110100000000

00011011010100010000011111101111000101011111100110001010110011001111001101100000

11101100110101010010111101000110000101101001101110100011001100000001110001100000

11111100110001110010110101011101011010000100100110110110000110100011001000000000

11001110110101111101100101111110000000101101111100110000100000110001001111100000

11011110110001011101101101100101011111000000110100100101101010010011110110000000

01001001110100101110000001110111111010110010011110010010011001110101011001100000

01011001110000001110001001101100100101011111010110000111010011010111100000000000

01101011110100000001011001001111111111110110001100000001110101000101100111100000

01111011110000100001010001010100100000011011000100010100111111100111011110000000

01100100001000011110100001000110110101010010110100001101001100100100001111000000

01110100001100111110101001011101101010111111111100011000000110000110110110100000

01000110001000110001111001111110110000010110100110011110100000010100110001000000

01010110001100010001110001100101101111111011101110001011101010110110001000100000

11000001001001100010011101110111001010001001000100111100011001010000100111000000

11010001001101000010010101101100010101100100001100101001010011110010011110100000

11100011001001001101000101001111001111001101010110101111110101100000011001000000

11110011001101101101001101010100010000100000011110111010111111000010100000100000

00000100101100101111101111111101010000010110010110010011000000001100011100100000

00010100101000001111100111100110001111111011011110000110001010101110100101000000

00100110101100000000110111000101010101010010000100000000101100111100100010100000

00110110101000100000111111011110001010111111001100010101100110011110011011000000

.

.

.

00011111111000111111110000010010010101001001110000011001110011000011010001000000

Table 5.16: Possible expanded bit sequences for local collisions

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 173

compared to a random independent message pair. The second type of collision

is much nicer and we now want to study this case.

In order to ļ¬nd a colliding pair (W, W ā• ā), we proceed in two phases.

First, we choose a good value for the diļ¬erence ā in order to maximize the

probability of success. After that, we search for a good value of W . In

order to choose a good diļ¬erence ā, we need to analyze the sources of non-

linearity in SHA-0 and consider how to minimize their impact. There are two

sources of non-linearity in SHA-0, additions modulo 232 and the functions from

Table 5.15. Clearly, the impact of the functions does not depend on the bit

position j, since they operate in parallel on the bit positions. On the contrary,

for the modular addition, not all bit positions are equivalent. Indeed, when

adding two numbers X and Y , it is easy to see that changes on the high order

bits of both numbers never aļ¬ect the value of the sum X + Y (mod 232 ) in

a non-linear manner. On the other hand, when changing the value of some

lower order bits of X and Y , the corresponding bit of X + Y (mod 232 ) is

aļ¬ected in a linear way, but the next bits of the sum may be modiļ¬ed non-

linearly. To give an example, when we modify the low order bit of X, we

either add or subtract 1 from X. When changing this bit both in X and Y , if

one change corresponds to an addition and the other to a subtraction, X + Y

does not change. Otherwise, the value of X + Y changes by either 2 or ā’2.

This carry to the next bit value is a non-linear change. If in addition the

carry propagates, other bits may also be aļ¬ected in the binary representation

of X + Y .

As a consequence, to build a good value for the diļ¬erence ā, we roughly

need to minimize the total number of individual bit changes occurring during

the computation, in order to limit the risk of encountering carries. We also

need to have a large fraction of the diļ¬erences located on the high order bit in

order to take advantage of the linearity of the high order bit in additions. To

satisfy these two conditions, the basic idea is to choose a low weight element

in Table 5.16 and use it as a locator to insert local collisions on bit position 1.

Indeed, we know that such local collisions are going to involve changes on bit

positions 1, 6 and 31. Moreover, bit position 31, which corresponds to high

order bits occurs more frequently than the others. Indeed, a change on bit

position 1 at round i requires one correction on each of the bit positions 1

and 6, but three corrections on bit 31. Note the weight of the elements in

Table 5.16 is only a rough indicator. In order to choose the best possible

locations to insert the local collisions, it is necessary to analyze the propaga-

tion of changes within SHA-0 computations in more details. We now give this

detailed analysis.

5.4.3.1 Propagation of changes in SHA-0

In order to study the propagation of changes throughout SHA-0, we are

going to analyze each of the non-linear functions that occur here. There

are three such functions to consider: addition modulo 232 on a bit position

Ā© 2009 by Taylor and Francis Group, LLC

174 Algorithmic Cryptanalysis

< 31 and the IF and MAJ functions. Indeed, addition on the high order

bit and the XOR function both behave linearly. For each function, we not

only need to consider the presence or not of a change on each input bit but

also the direction of the change. In the tables given in this section, we use

the following notations, 0 represents a bit equal to 0 that does not change,

1 represents a bit equal to 1 that does not change, ā‘ represents of bit that

changes from 0 to 1 and ā“ represents of bit that changes from 1 to 0.

With this notation, describing the case by case behavior for each function on

three bits is quite simple. They are given in Tables 5.17, 5.19 and 5.20. In the

case of addition, we only give the details for an addition of three summands

but we also indicate the behavior of the carry bit. It is, of course, possible to

perform the same analysis for more summands. However, in the case of SHA-0,

this simpliļ¬ed analysis is suļ¬cient to understand the probabilistic behavior

of local collisions.

With these three tables in mind, it is easy to understand the behavior of

a single, stand-alone local collision. The ļ¬rst action of this local collision is

to insert a diļ¬erence on bit 1 of W (i) . To simplify the analysis, it is useful

to assume that we know the direction of the bit change. For example, let

us assume that the changing bit goes from 0 to 1. Following the notation

of Tables 5.17 to 5.20, it is a ā‘ transition. As in the linear case described

in Section 5.4.2.1, this change directly aļ¬ects bit 1 of A(i+1) . Looking at

Table 5.20, we see that two main cases are possible. If there are no unwanted

carries, then bit 1 of A(i+1) is also a ā‘ and all other bits of A(i+1) are constants.

Otherwise, bit 1 of A(i+1) is a ā“ and bit 2 no longer is a constant. Note that

the carry eļ¬ect may propagate further and aļ¬ect more bits. Assuming that

the inputs of the addition are random values, we can see that the nice case

where no bad carry occurs happens with probability 1/2. Once the ā‘ change

is in A(i+1) , it is involved (after rotation) in the computation of A(i+2) . Since

we are considering a local collision, another change is also present on bit 6

of W (i+2) . Looking again at the table, we see that when both changes are ā‘,

they never cancel each other. Thus, we need to make sure that the correction

present on bit 6 of W (i+2) is a ā“, in which case it always correctly performs

the correction. In the next round, the ā‘ change is on bit 1 B (i+2) and involved

in the computation of A(i+3) , together with the correction located on bit 1 of

W (i+2) . This change undergoes two non-linear processes; ļ¬rst it goes through

one of the three functions IF, XOR or MAJ, then it enters the addition.

Looking at the three functions, we see that a total of three diļ¬erent behaviors

may occur. The change may vanish, it may remain unchanged or it may be

reversed into a ā“. Note that with XOR, the change never vanishes. With MAJ,

it is never reversed. With IF, all three behaviors are possible. If the change

vanishes, then the correction never occurs correctly and the local collision

fails. With IF or MAJ, this occurs with probability 1/2. Concerning the

direction of the change, we need to consider two cases. When going through

MAJ, the ā‘ is never reversed, thus if we make sure that the correction on

bit 1 of W (i+2) is a ā“, the addition also behaves nicely, assuming that the

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 175

x = 0 y = 0 y = 1 y =ā‘ y =ā“ x = 1 y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā“

z=0 0 0 0 0 z=0 0 1

ā‘ ā“

z=1 0 1 z=1 1 1 1 1

ā‘ ā‘ ā‘ ā‘

z =ā‘ 0 0 z =ā‘ 1 1

ā“ ā“ ā“ ā“

z =ā“ 0 0 z =ā“ 1 1

x =ā‘ y = 0 y = 1 y =ā‘ y =ā“ x =ā“ y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā‘ ā“ ā“

z=0 0 0 z=0 0 0

ā‘ ā‘ ā“ ā“

z=1 1 1 z=1 1 1

ā‘ ā‘ ā‘ ā‘ ā‘ ā“

z =ā‘ z =ā‘ 0 1

ā‘ ā“ ā“ ā“ ā“ ā“

z =ā“ 0 1 z =ā“

Table 5.17: Case by case behavior of MAJ(x, y, z)

x = 0 y = 0 y = 1 y =ā‘ y =ā“ x = 1 y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā“ ā“ ā‘

z=0 0 1 z=0 1 0

ā‘ ā“ ā“ ā‘

z=1 1 0 z=1 0 1

ā‘ ā“ ā“ ā‘

z =ā‘ 0 1 z =ā‘ 1 0

ā“ ā‘ ā‘ ā“

z =ā“ 1 0 z =ā“ 0 1

x =ā‘ y = 0 y = 1 y =ā‘ y =ā“ x =ā“ y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā“ ā“ ā‘

z=0 0 1 z=0 1 0

ā“ ā‘ ā‘ ā“

z=1 1 0 z=1 0 1

ā‘ ā“ ā“ ā‘

z =ā‘ 0 1 z =ā‘ 1 0

ā“ ā‘ ā‘ ā“

z =ā“ 1 0 z =ā“ 0 1

Table 5.18: Case by case behavior of XOR(x, y, z)

x = 0 y = 0 y = 1 y =ā‘ y =ā“ x = 1 y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā“

z=0 0 0 0 0 z=0 0 1

ā‘ ā“

z=1 1 1 1 1 z=1 0 1

ā‘ ā‘ ā‘ ā‘ ā‘ ā“

z =ā‘ z =ā‘ 0 1

ā“ ā“ ā“ ā“ ā‘ ā“

z =ā“ z =ā“ 0 1

x =ā‘ y = 0 y = 1 y =ā‘ y =ā“ x =ā“ y = 0 y = 1 y =ā‘ y =ā“

ā‘ ā‘ ā“ ā“

z=0 0 0 z=0 0 0

ā“ ā“ ā‘ ā‘

z=1 1 1 z=1 1 1

ā‘ ā‘ ā‘ ā‘

z =ā‘ 0 0 z =ā‘ 1 1

ā“ ā“ ā“ ā“

z =ā“ 1 1 z =ā“ 0 0

Table 5.19: Case by case behavior of IF(x, y, z)

Ā© 2009 by Taylor and Francis Group, LLC

176 Algorithmic Cryptanalysis

x = 0 y = 0 y = 1 y =ā‘ y =ā“ x = 1 y = 0 y = 1 y =ā‘ y =ā“

0ā‘ 0ā“ ā‘ā“ ā“ā‘

z=0 00 01 z=0 01 10

ā‘ā“ ā“ā‘ 1ā‘ 1ā“

z=1 01 10 z=1 10 11

0ā‘ ā‘ā“ ā‘0 ā‘ā“ 1ā‘ ā‘1

z =ā‘ 01 z =ā‘ 10

0ā“ ā“ā‘ ā“0 ā“ā‘ 1ā“ ā“1

z =ā“ 01 z =ā“ 10

x =ā‘ y = 0 y = 1 y =ā‘ y =ā“ x =ā“ y = 0 y = 1 y =ā‘ y =ā“

0ā‘ ā‘ā“ ā‘0 ā“ ā“ā‘ ā“0

z=0 01 z=0 01

ā‘ā“ 1ā‘ ā‘1 ā“ā‘ 1ā“ ā“1

z=1 10 z=1 10

z =ā‘ 0 ā‘ 0 ā‘1 ā‘ā‘ ā‘ā“ ā‘ā“ ā“ā‘

z =ā‘ 01 10

ā‘ā“ ā“ā‘ ā“0 ā“1 ā“ā‘ ā“ā“

z =ā“ 01 10 z =ā“

Table 5.20: Case by case behavior of ADD(x, y, z) (carry bit on left)

change does not vanish. With IF or XOR, we do not know in advance if the

change remains a ā‘ or becomes a ā“, thus we do not care about the direction of

the change on bit 1 of W (i+2) , the addition cancels the two with probability

1/2. Summing up, we see that the computation of A(i+3) works out correctly

with probability 1/4 when the function is an IF, with probability 1/2 due to

the possibility of vanishing changes when it is a MAJ and with probability

1/2 due to the possibility of reversing changes when it is a XOR. The next

correction concerns bit 31 of A(i+4) . Since it involves the high order bit of

addition, no carry propagation is possible. Thus, at this point, we do not care

whether the change is preserved or reversed, as long as it does not vanish.

Thus, there is a probability of good correction of 1/2 with IF and MAJ, while

the correction is always correct with XOR. The fourth correction on bit 31 of

A(i+5) behaves exactly in the same way. Finally, the ļ¬nal correction on bit

31 of A(i+6) is always correctly cancelled by the correction bit present on bit

31 of W (i+5) .

Thanks to this analysis, it is possible to compute for any given round po-

sition i, the probability of successfully applying a single local collision at this

round. However, this calls for several comments. First, we need to make sure

in advance that where needed the correction bits are indeed of type ā“ to com-

pensate for the initial change ā‘. Second, this probability is correct when the

computation of the local collision is uncontrolled, i.e., when all values that

enter the computation, with the exception of the correction bits, are consid-

ered to be random. As we will see later, when it is possible to choose (some

of) the input values, then it is possible to greatly improve this probability.

5.4.3.1.1 Superposing several local collisions The above analysis is

not complete because it only considers isolated local collisions that do not

interfere with each other. However, looking at Table 5.16, we see that none

of the candidates for placing the local collisions can guarantee that they are

always isolated from each other. As a consequence, we need to understand

the interaction between interleaved local collisions. Two cases need to be

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 177

considered. On one hand, when two such local collisions only act on diļ¬erent

bits, it is safe to assume that the individual probability of success are preserved

and simply need to be multiplied together to obtain the total probability. On

the other hand, when two local collisions impact the same bit of some word

in A, the exact behavior is quite complicated and each of the functions IF,

XOR and MAJ is a speciļ¬c case.

To analyze these interactions, let us determine the relative positions of

interfering pairs of local collisions. Assume we are superposing two local

collisions respectively starting on A(i1 ) and A(i2 ) , with i1 < i2 . Note that

when i2 > i1 + 5, the local collisions are clearly not overlapping. Thus, there

are ļ¬ve cases to consider. For each case, there is an interaction for each

round where the two local collisions act on the same bit. For example, when

i2 = i1 + 1, we see that at round i1 + 1 the ļ¬rst collision acts on bit 6,

the second on bit 1 and that they do not interfere. At round i1 + 2, they

respectively act on bits 1 and 6. At round i1 + 3, they act on bits 31 and 1.

At rounds i1 + 4 and i1 + 5, they both act on bits 31 and do interfere. We

summarize all the possible interactions in Table 5.21. We see in this table

that there are only four possible cases of interaction:

ā¢ When i2 = i1 + 2, there is an interaction on bit 1 in round i2 . On mes-

sage word W (i2 ) , we see that the two local collisions both modify bit 1,

as a consequence, their interaction leaves this bit ļ¬xed. Thus, we need

to consider the consequence of a single diļ¬erence on bit 1 of B (i2 ) . If this

diļ¬erence does not propagate through the function f (i2 ) , then the second

local collision is not correctly inserted in round i2 and the corresponding

corrections in later rounds fail. When f (i2 ) is a MAJ function, the direc-

tion ā‘ or ā“ of the change is preserved. This information should be used

when determining the direction of the corrections for the second local

collision. With IF or XOR, the direction may change and we can choose

between two sets of possibilities for the corrections. Of course, once we

have chosen to consider that the direction is preserved (or changed), any

message pair that behaves diļ¬erently encounters miscorrection at some

later round.

We can now compare the probability of success with two interacting

local collisions and the probability of two independent local collisions

one in round i1 and one in round i2 . With two independent collisions,

the ļ¬rst succeeds when the perturbation correctly goes through f , i.e.,

with probability 1/2 with XOR or MAJ and 1/4 with IF; the second

succeeds if there is no carry, i.e., with probability 1/2. With two inter-

acting collisions, the probabilities are allocated slightly diļ¬erently, but

the overall contribution is left unchanged. Thus, this type of interaction

does not deeply aļ¬ect the construction of a collision path.

ā¢ When i2 = i1 +1, there is an interaction on bit 31 in round i1 +4 = i2 +3.

On message word W (i1 +4) , the corrections cancel each other. Thus,

Ā© 2009 by Taylor and Francis Group, LLC

178 Algorithmic Cryptanalysis

Round number

i2 ā’ i1 i1 + 1 i1 + 2 i1 + 3 i1 + 4 i1 + 5

1 6=1 1=6 31 = 1 31 31

2 ā” 1 31 = 6 31 = 1 31

3 ā” ā” 31 = 1 31 = 6 31 = 1

4 ā” ā” ā” 31 = 1 31 = 6

5 ā” ā” ā” ā” 31 = 1

Table 5.21: Interferences of overlapping local collisions

we have two changes on bit 31, one in D(i1 +4) , the other in C (i2 +3) .

Note that the two exponents are equal; they are written diļ¬erently to

emphasize that the ļ¬rst change corresponds to the ļ¬rst collision and the

second to the second one. With the XOR function, these two changes

cancel each other, which is the desired behavior. With MAJ, the two

changes cancel if and only if one is a ā‘ and the other a ā“. Since this

can be controlled in advance when choosing the direction of changes in

the collision path, this improves the probability of success compared to

independent collisions. With IF, since bit 31 of B cannot belong to any

local collision, it should be seen as a constant. This constant controls

which of the two changes is going through the IF function, but in any

case, one change always goes through. Thus, with two adjacent local

collisions that share an IF function, it is never possible to construct a

correct collision path that follows our linear model. This imposes a new

constraint on the construction of collision paths.

ā¢ When i2 = i1 + 1, there is a possibility of interaction on bit 31 in round

i1 +5 = i2 +4. In fact, this is not a real interaction, because the function

f is only applied to one of the two changes and the changes are then

linearly combined by addition on the high order bit. Once again, the

global cost of the interacting collisions is the same as the cost of two

independent local collisions.

ā¢ When i2 = i1 +2, there is an interaction on bit 31 in round i1 +5 = i2 +3.

As in the previous case, this interaction does not modify the probability

of success. Note that this case may be combined with the second case to

yield an interaction of three consecutive local collisions with i2 = i1 + 1

and i3 = i1 + 2 on bit 31 of round i1 + 5. In that case, the probability of

success is modiļ¬ed as in the second case where the interaction between

the second and third cases is concerned, while the ļ¬rst local collision is

essentially independent of the other two at this round. Remember that

with such a triple, the ļ¬rst two local collisions also interact at round

i1 + 4.

Taking all these considerations into account, we ļ¬nd that two diļ¬erential

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 179

paths for SHA-0 which are almost equally good, these two paths are described

by the following disturbance vectors:

0001000000010010000000100001101101111110

1101001000010101001010100010111001100000

and

0010001000000010111101100011100000010100

0100010010010011101100110000111110000000

In order to compute the exact cost of the cryptanalytic attack associated

with these disturbance vectors and to determine which of these two vectors

is the best one, it is necessary to explain with more details how these vectors

are used in practical attacks. This is the goal of the next section.

5.4.4 Searching for collision instances

The above analysis shows that there exists a large number of message block

pairs that collide after following our diļ¬erential path. However, this does not

suļ¬ce to build a collision search attack. In addition, we need to ļ¬nd an eļ¬-

cient way to construct such message pairs. This is done using a guided brute

force approach. This approach is a kind of brute force, because we try message

pairs again and again until a collision is found, it is guided because we use

the known properties of the collision path to make the search more eļ¬cient

and faster. Several techniques are used for this purpose. Two basic tech-

niques were described in [CJ98], others were introduced later in [WYY05a],

[WYY05b], [BC04] and [BCJ+ 05].

5.4.4.1 Early abort

In a basic implementation of the attack, a possible approach would be for

each message pair to compute the compression function completely for both

messages. Of course, this would work but requires two complete evaluations of

the compression function for each message pair. To improve this, we can use

our extensive knowledge of the diļ¬erential path. For each intermediate step

in the computation of the compression function, the diļ¬erential path essen-

tially speciļ¬es the value of the XOR of the computed A(i) for each message.

In this context, an early abort strategy consists of checking at each step of

the computation that the eļ¬ective value of the XOR is compatible with the

diļ¬erential path. If this is not the case, it does not mean that the two message

blocks cannot collide, only that if they collide, they do so in a non-controllable

manner. As a consequence, the probability of collision for the pair is very low

and it is not worth pursuing the computation. Thus, as soon as the message

blocks stray from their intended path, we abort the computation.

Ā© 2009 by Taylor and Francis Group, LLC

180 Algorithmic Cryptanalysis

5.4.4.2 Partial backtrack

One of the most important optimizations to search for a diļ¬erential colli-

sion in the SHA-0 family is to remark that constructing messages conformant

with the diļ¬erential path during the ļ¬rst 16 rounds essentially comes for free.

Indeed, during these rounds, if the current message pair is incompatible with

the diļ¬erential path, instead of restarting from scratch, we can instead back-

track for a few rounds in order to modify the register whose value prevents

the conditions of the diļ¬erential path to be satisļ¬ed. Using this approach,

it is easy to ļ¬nd message pairs which conform to the diļ¬erential up to the

start of round 15. In fact, remarking that both disturbance vectors given at

the end of Section 5.4.3 have a diļ¬erence inserted in round 14, we can make

the analysis more precise. For this diļ¬erence to be corrected properly, the

following conditions need to be satisļ¬ed:

ā¢ The diļ¬erence in round 14 should be inserted without carry. This can

be easily satisļ¬ed by backtracking by a single round.

ā¢ The second correction in round 16 should be performed correctly. Since

the non-linear function in round 16 is an IF, this implies that the bits in

position 1 of C (16) and D(16) should be opposite, to make sure that the

diļ¬erence propagates through the IF function. Moreover, we can make

sure that it propagates in the right direction by enforcing speciļ¬c values

for these bits. Note that C (16) and D(16) are rotated copies of A(14) and

A(13) . As a consequence, the condition can be ensured before choosing

W (14) .

ā¢ To perform the third correction in round 17, we need to make sure that

bit 31 of B (17) is a 1. This can be ensured by a correct choice of the

high order bit of W (15) .

ā¢ With this basic analysis, the fourth correction in round 18 is the ļ¬rst

one that cannot be simply enforced in advanced. Indeed this condition

is controlled by bit 31 of B (18) , i.e., of A(17) . As a consequence, the

probability associated with the diļ¬erence in round 14 is only 1/2. Using

a slightly more complicated analysis, we see that, with high probability4 ,

this bit can be changed to the correct value by modifying bit 26 of W (15) ,

thus aļ¬ecting A(16) and, indirectly, A(17) .

The second disturbance vector also has diļ¬erences inserted in rounds 16 to 19.

It is clear that an analysis similar to the one we performed for the diļ¬erence of

round 14 allows us to prearrange a fraction of these conditions. Due to these

prearranged conditions, the second disturbance vector becomes more eļ¬cient

than the ļ¬rst one for the diļ¬erential attack on SHA-0.

4 This may fail when changing bit 26 induces a carry which propagates up to round 31.

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 181

5.4.4.3 Neutral bits and message modiļ¬cations

Looking at the diļ¬erence paths induced by a disturbance vector in SHA-0

and at the conditions that are necessary for these paths, we see that most

bits of the inner state, i.e., most bits of A, are not directly involved in these

conditions. For example, if we modify a single bit in the middle of register A

at some round, this change is not going to aļ¬ect the diļ¬erential path immedi-

ately. Of course, after enough rounds, the change propagates throughout the

registers and aļ¬ects the path. The basic idea of neutral bits [BCJ+ 05] is, given

a message pair compatible with a ļ¬xed diļ¬erential path up to some round, to

identify bit positions where A can be modiļ¬ed without immediately aļ¬ecting

the diļ¬erential path. Since A can be modiļ¬ed by changing the corresponding

message word, it is possible to perform this change by ļ¬‚ipping a bit at the

same position in the message word. Such bit positions are called neutral bits

for the message pair. We speak of a neutral bit up to round r when we want

to emphasize the range of rounds we are considering. There are two kinds

of neutral bits that can be encountered, simple neutral bits and composite

neutral bits. A simple neutral bit corresponds to a single bit position, usually

located in one of the ļ¬nal rounds, say between round 12 and round 15. A

composite neutral bit consists of several bit positions which need to be ļ¬‚ipped

together in order to preserve conformance. A more careful analysis shows that

a composite neutral bit behaves like a kind of local collision, inserts a change

and corrects it, often in a non-linear way, for a limited number of rounds.

Another important property of neutral bits is obtained when considering

several neutral bits at the same time. Two neutral bits, either simple or

composite, are said to be pairwise independent when the four pairs of messages

consisting of an original pair, the pair with one neutral bit ļ¬‚ipped, the pair

with the other bit ļ¬‚ipped and the pair with both neutral bit ļ¬‚ipped all conform

to the diļ¬erential path up to round r. This property of pairwise independence

reļ¬‚ects the fact that the changes eļ¬ected by ļ¬‚ipping the two neutral bits

involve bit position which can only interact through rare long range carries.

An important heuristic fact is that given n neutral bits, such that each pair

of these neutral bits are pairwise independent up to round r, a large fraction

of the 2n pairs of messages obtained by ļ¬‚ipping an arbitrary subset of the

neutral bits also conform to the diļ¬erential path up to round r. In practice,

this works very well up to r around 22.

To summarize, the raw eļ¬ect of large set of pairwise independent neutral

bits is to give a shortcut during the search for a valid message pair. Thanks

to this shortcut, the number of message pairs to be tested can be estimated

by counting the probability of success from round 22ā“24 instead of round 19.

Boomerang attacks

Neutral bits, as deļ¬ned above, occur naturally in message pairs. From

time to time, some composite neutral bits with a very long range are encoun-

tered. However, this event is unfrequent and we cannot count on the natural

Ā© 2009 by Taylor and Francis Group, LLC

182 Algorithmic Cryptanalysis

occurrence of these long range neutral bits. The idea of the boomerang5 at-

tack [JP07] for hash functions is to construct speciļ¬c diļ¬erential paths that

embed a few of these long range neutral bits. This idea requires the use of

sophisticated diļ¬erential paths relying on non-linear behavior during the IF

rounds, as introduced in [WYY05a, WYY05b]. It was used in [MP08] to

derive the fastest known diļ¬erential attack against SHA-0.

Message modiļ¬cations

Another approach to bypass the probabilistic cost of a few rounds after

round 16 when searching for a message pair is the use of message modiļ¬ca-

tion and advanced message modiļ¬cation techniques introduced in [WYY05a,

WYY05b]. The basic idea is given a message pair to identify the ļ¬rst un-

satisļ¬ed condition which prevents the message pair from conforming to the

diļ¬erential path. Once this condition is found, the message modiļ¬cation tech-

nique consists of ļ¬‚ipping a few bits of messages. These bits are chosen to make

sure that, with high probability, ļ¬‚ipping them preserves conformance up to

the ļ¬rst failure and reverse the value of the ļ¬rst non-conforming bit. Very

roughly, it can be seen as a kind of neutral bit, whose ļ¬rst non-neutral eļ¬ect

is used as a correction.

5.5 Brute force and parallel computers

Brute force attacks can be very easily implemented using parallel comput-

ers. Indeed, they are of the embarrassingly parallel kind: it suļ¬ces to launch

n copies of the same program, each searching in a fraction of the space of

possible keys (or message pairs for the diļ¬erential attack on SHA) to speed up

the computation by a factor of n. Despite its extreme simplicity, this basic

remark should never be forgotten when evaluating the security of a cryptosys-

tem. A brute force attack whose computational cost is at the boundary of

feasible computations is much easier to implement and run than a sophisti-

cated computation with roughly the same cost.

A new trend in parallel computation is the use of powerful graphic pro-

cessor units for general purpose computations. It is interesting to note that

brute force computations can easily be implemented on such cards. As a con-

sequence, reports of practical brute force attacks on graphic processors should

be expected in the near future. In the same vein, people are also considering

the use of video game consoles, since they oļ¬er very good performance/price

ratios.

5 This

name is due to similarity with the boomerang attack for block ciphers introduced by

Wagner [Wag99].

Ā© 2009 by Taylor and Francis Group, LLC

Brute force cryptanalysis 183

Exercises

1. To better understand the ļ¬gures involved in brute force cryptanalysis,

compute, assuming that trying one key costs one CPU cycle, the total

number of keys that can be tried during a year using your personal

computer, using all computers in a university or company, and using all

computers on earth.

2. Using the Moebius transform of Chapter 9, compute expressions for each

bit of each S-box of DES as polynomials over F2 . Count the number of

operations (XOR and AND) needed to compute each S-box. Compare

with the number of operations given in [Kwa00].

3. Historically, monoalphabetic substitution ciphers have frequently been

encounted. Assuming an alphabet with 26 letters, count the number of

keys. Is a monoalphabetic substitution cipher vulnerable to a simple

minded brute force attack which simply tries all possible keys.

4h . When considering brute force attacks, the rapid increase of computing

power through time needs to be taken into account. Assume that you

are given ļ¬ve years to attack through brute force an instance of a cryp-

tosystem on 64 bits. How you would proceed to minimize the cost?

Assume that the cost of computing power follows a geometric evolution

which divides the cost of trying a single key by two during a one-year

period.

5h . One important diļ¬culty with automated brute force attacks is the need

for a stopping condition, i.e., for a criterion which can be used to distin-

guish the correct key. Find a possible stopping condition to decrypt a

DES ciphertext, assuming an english plaintext written using the ASCII

code.

6h . Assume that you need to write an encryption program but are, for

external reasons, limited to small encryption keys, say on 40 bits. How

would you proceed to build a system with as much security as possible?

Do not forget that the key limit only applies to keys, not to any auxiliary

data used during the encryption, as long as this data can be recovered

from the ciphertext.

7. Write an exhaustive search algorithm for placing n tokens on a n Ć— n

grid and make sure that there never are two tokens on the same row,

column or diagonal. What is the cost of your approach as a function of

n? What values are achievable?

ā¢ Improve your algorithm to make sure before placing a new token

that it does not conļ¬‚ict with previous tokens.

Ā© 2009 by Taylor and Francis Group, LLC

184 Algorithmic Cryptanalysis

This chapter can also be a source for projects, a few examples are:

i. Program a bitslice implementation of DES, dedicated to brute force.

Compare the speed of your implementation with available libraries that

contain fast implementations of DES encryption. Port this program to

a graphic processor unit.

ii. Write an implementation of the basic SHA-0 attack described in this

chapter. Improve your implementation using advanced attacks available

in the literature.

iii. Write a toolkit for brute force cryptanalysis against historical cryptosys-

tem.

Ā© 2009 by Taylor and Francis Group, LLC

Chapter 6

The birthday paradox: Sorting or

not?

The birthday paradox is a ubiquitous paradigm in cryptography. In some

sense, it can be seen as an eļ¬cient probabilistic variation on the pigeonhole

principle. Recall that the pigeonhole principle is a very general rule, that says

that, given n disjoint classes of objects and a set of N objects, if N > n then

there is at least one class containing two or more objects. In this context, we

say that the two objects collide in the same class or simply that we have a

collision. Using this terminology, the pigeonhole principle simply states that

given n classes, with at least n + 1 objects, a collision always occurs. In

a probabilistic context, assuming that objects are equiprobably distributed

among classes, it is natural to ask: How many objects do we need to have a

collision with probability greater than one half?

The answer to this question is the core of the birthday paradox, it is a

paradox in the sense that it does not ļ¬t the common sense answer. With n

classes, it is not necessary to have n/2 objects, much less are needed. May be

ā

surprisingly, the correct answer is of the order of n.

The consequences of the birthday paradox in cryptography are uncountable;

they are encountered in public and secret key cryptography, in cryptanalysis

and provable security and impacts all subtopics of cryptography from the

study of stream ciphers to number theory. For this reason, we devote this

chapter and the next two to the study of the birthday paradox. The three

chapters diļ¬er by the amount of memory used by their respective algorithms.

In the present chapter, we consider algorithms that use a lot of memory,

of the same order as their running time. In the next chapter, we focus on

algorithms that use a small amount of memory. The third chapter on birthday

paradox techniques describes the intermediate case and presents algorithms

with medium memory requirements.

185

Ā© 2009 by Taylor and Francis Group, LLC

186 Algorithmic Cryptanalysis

6.1 Introductory example: Birthday attacks on modes

of operation

To illustrate the importance of the birthday paradox in cryptography and

show that it is the key to understanding the security of many cryptographic

protocols, we study the case of modes of operations for block ciphers. As

explained in Chapter 1, a mode of operation for a block cipher is a way to

extend the domain of the block cipher and allow it to encrypt and/or authen-

ticate messages of varying length instead of blocks of ļ¬xed length. Another

essential feature of modes of operation is that they use block ciphers as black

boxes. Thus, a given mode can be used with many diļ¬erent block ciphers.

As a consequence, it is useful to study the security of the mode of operation

independently of the underlying block cipher. The standard proof technique

used to perform this study is to consider the mode of operation when used

in conjunction with a truly random permutation. With this idealization, two

types of results can be derived. On the one hand, given a mode of operation,

we can describe attacks which work with all block ciphers. They are called

generic attacks and give an upper bound on the security of the mode of op-

eration. On the other hand, it is also possible to give lower bounds by writing

security proofs which show that when used in conjunction with a secure block

cipher the mode of operation is secure. The study of security proof is out-

side of the scope of this book. The interested reader can refer to one of the

numerous research papers on this topic such as [BR06].

In this section, we are going to consider attacks on two basic modes of

operation, Cipher Block Chaining (CBC) including its authentication version

called CBC-MAC and Counter mode (CTR). More precisely, we are going

to study the security of these modes by describing generic chosen message

distinguishing attacks, as described in Chapter 1.

6.1.1 Security of CBC encryption and CBC-MAC

In order to start the study of the security of CBC encryption and CBC-

MAC, we ļ¬rst address the motivation behind the slight diļ¬erences between

the two modes and explain why these diļ¬erences are essential to the security.

For this purpose, we need to use the notion of forgery recalled in Chapter 1.

Initial value. First, recall that one of the essential diļ¬erences between CBC

encryption and CBC-MAC is the fact that the former needs an IV , while the

latter needs no IV . We already know that without an IV , CBC encryp-

tion becomes deterministic and thus cannot be secure against chosen message

distinguishers. It is thus natural to ask what happens to CBC-MAC, when

used with an IV . Clearly, in order to allow the message recipient to verify

the MAC tag, the IV used when creating the authentication tag needs to be

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 187

transmitted along with the message. Thus, the attacker knows the chosen

IV value. Assume that this IV value is used as the starting intermediate

ciphertext block C (0) . Then, the intermediate block C (1) is obtained from the

plaintext block P (1) by encrypting C (0) ā• P (1) . Since both values C (0) and

P (1) are known to the attacker, he can easily create a diļ¬erent message with

the same authentication tag by xoring any value of his choice with both C (0)

and P (1) . This allows him to change the ļ¬rst message block to any value of

his choice.

If the IV is used as a plaintext block, this attack does not work; how-

ever, this simply corresponds to authenticating using the ordinary CBC-MAC

without IV , a message extended by adding a random ļ¬rst block. As a conse-

quence, this is more costly than CBC-MAC without an IV and does not add

any security.

Intermediate values. Releasing intermediate values during the MAC com-

putation would be both costly and insecure. The cost part is obvious since this

modiļ¬cation would make the authentication tag much longer. The insecurity

part can be seen using variations on the above attack on initial values.

Final block. In order to see that CBC-MAC is insecure if the ļ¬nal block

is not reencrypted, let us consider the following simple attack. The adversary

ļ¬rst queries the CBC-MAC of a single block message. Clearly, in that case,

assuming that the underlying block cipher is modeled by the random permu-

tation Ī , the authentication tag is t = Ī (P (1) ). Given this tag, the adversary

can immediately assert that the authentication tag of the two-block message

P (1) (P (1) ā• t) is also t. We let the reader verify this fact in Exercise 2. This

attack and variations on it can be performed only if messages of varying length

are accepted by the MAC computations/veriļ¬cations algorithms. When con-

sidering messages of a ļ¬xed length, CBC-MAC without a ļ¬nal block becomes

secure1 .

6.1.1.1 Birthday attacks on CBC encryption and CBC-MAC

After seeing the simple attacks that explain the diļ¬erences between CBC

encryption and CBC-MAC, we are now ready to consider the security of these

modes and its relation with the birthday paradox. For simplicity, it is easier

to start with the security of CBC-MAC because this mode is deterministic

and the attack is thus easier to follow. Assuming that we play the attackerā™s

role, in order to build a forgery on CBC-MAC, we ļ¬rst ask authentication

tag for many (diļ¬erent) two-block messages. Each message Mi is formed of

(1) (2)

the blocks Mi and Mi , the corresponding authentication tag is ti . Assume

1 Up to the birthday paradox bound.

Ā© 2009 by Taylor and Francis Group, LLC

188 Algorithmic Cryptanalysis

that making these queries, we ļ¬nd that the tags ti and tj of two diļ¬erent mes-

sages are equal. At this point we make an additional query, by asking for the

authentication tag t of a message obtained by completing Mi by an arbitrary

sequel S. We then assert that the authentication tag of Mj completed by the

same sequel S is also t. This comes from the fact that CBC-MAC computa-

tions propagate equalities between intermediate ciphertext blocks as long as

the message blocks are also equal. As a consequence, as soon as two authen-

tication tags are seen to be equal, forgery becomes an easy matter. Since this

is exactly the deļ¬nition of a collision between authentication tags, it shows

that the (non) existence of collisions is crucial to the security of CBC-MAC

authentication. Such an attack which relies on the existence of collisions is

often called a birthday attack, by reference to the birthday paradox.

Similarly, CBC encryption is also vulnerable to birthday attacks. More

precisely, if an attacker observes a collision between two encrypted blocks, he

gains some partial information about the corresponding plaintext blocks. For

simplicity of exposition, let us consider a single message M , with blocks M (i) .

If we have equality between the two blocks of ciphertext C (i) and C (j) we

also have equality between the corresponding inputs to the block cipher, i.e.,

between M (i) ā• C (iā’1) and M (j) ā• C (jā’1) . As the consequence, the attacker

learns the value of M (i) ā• M (j) . This remark is easily transformed into a

chosen message distinguishing attack (see Exercise 3).

6.1.1.2 Birthday attacks and the counter mode

The security of the counter mode is also an interesting example. At ļ¬rst,

it seems completely immune to birthday attacks. Indeed, since the pseudo-

random sequence is obtained by encrypting diļ¬erent values, no collision may

occur. More precisely, starting from an initial value and incrementing it, we

may not loop back to the initial value until all possible values of the b-bit

block have been considered. Since there are 2b diļ¬erent values2 , this is well

beyond the birthday paradox bound.

However, when considering the encryption of multiple messages, matters

become more complicated. Indeed, we should avoid reusing the same counter

values between messages. A simple solution is to memorize the current value

after encrypting a message and to restart from here for the next message.

However, in some practical scenarios, this solution which requires an encrypt-

ing device with memory is not possible. In that case, a frequently encountered

alternative is to choose a random initial value for each message. Of course,

with this solution, collisions between initial values lead to attacks and the

birthday paradox comes back into play.

More surprisingly, as distinguishing attacks go, even memorizing the counter

value is not enough to avoid the birthday paradox. Again playing the at-

2 Forcompleteness, note that if the incrementation is done using a LFSR, the all zero block

should be excluded and there are āonlyā 2b ā’ 1 values to be considered.

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 189

tackerā™s role, we go directly to the challenge step and submit two long random

messages M0 and M1 of the same length L (measured in blocks). We obtain

the encryption C of either M0 and M1 . By xoring C with M0 we get a ļ¬rst

candidate for the pseudo-random stream used during encryption. By xoring

C with M1 we get a second candidate. By construction, there can be no colli-

sion between blocks within the correct candidate. However, nothing prevents

random collisions to occur in the incorrect one. As a consequence, if the ad-

versary observes a collision in one of the two pseudo-random candidates, he

knows for sure which of M0 and M1 was encrypted and he can announce it.

Otherwise, he tosses a random coin and announces the corresponding guess.

Clearly, if the probability of collision in the incorrect pseudo-random candi-

date is non-negligible, the adversary gains a non-negligible advantage. It is

interesting to note that this distinguisher is not really based on a property of

the counter mode itself but rather on the fact that the mode is constructed

on a permutation. If the block cipher or random permutation is replaced by

a (pseudo) random function the distinguisher vanishes. However, this would

not remove the need to memorize counter values. Moreover, in practice, a

counter mode based on a pseudo-random function is a rarely seen construc-

tion in cryptography. The main reason probably being that block ciphers are

standardized and thus more readily available to developers.

6.2 Analysis of birthday paradox bounds

Since the mere existence of collisions can be essential to the security of

cryptographic algorithms and protocols, it is important to estimate the prob-

ability of having collisions within sets3 of random objects, before considering

the algorithmic issue of eļ¬ectively and eļ¬ciently ļ¬nding such collisions. Of

course, the exact probability depends on the distribution of these random ob-

jects. If they are generated from distinct values by application of a random

permutation or equivalently if they are randomly drawn without replacement

from a set, no collision may occur and the probability of having a collision is

zero. On the other hand, the probability for twins to have the same birthday

is almost one (see Exercise 4).

The easiest case to analyze is the case of objects taken uniformly at random

from a given set (with replacement). In this context, two parameters need

to be considered, the number of randomly drawn objects N and the size

of the set N . In order to determine the probability of collision, we may

ļ¬rst consider a simple heuristic method. Among N objects, we can build

3 Ormore precisely multisets: by deļ¬nition a set may only contain a single copy of a given

object. This abuse of language is frequently encountered and we simply follow the tradition.

Ā© 2009 by Taylor and Francis Group, LLC

190 Algorithmic Cryptanalysis

N (N ā’ 1)/2 pairs. Moreover, for any pair, the probability of collision is N ā’1 .

Assuming independence between pairs, we have an average estimated number

of collisions equal to:

N (N ā’ 1)

.

2N

This simple heuristic analysis already points to a threshold for collisions

ā

around N ā N . However, this analysis is not satisfying for several rea-

sons. First, it incorrectly assumes independence between pairs of objects in

the random set. Second, it does not give a probability of collision but instead

estimates the expected number of collisions within a multiset.

Our goal in the sequel is to make the analysis more precise. In this analysis,

we denote the probability of having at least one collision in a randomly chosen

set of N elements among N by CollN . Let us ļ¬rst start by giving an upper

N

bound. For convenience, we assume that the drawing order of elements in the

random set has been kept. In that case, we have a random list and can access

each element by its rank from 1 to N . Element i is denoted by Xi . For any

pair (i, j), the probability of having Xi = Xj is N ā’1 . If any pair collides,

then of course, there is a collision in the set. Since the probability of a union

of events is always upper bounded by the sum of the probability of individual

events, regardless of independence we ļ¬nd that:

N Ā· (N ā’ 1)

1

CollN ā¤ = . (6.1)

N

N 2N

Pairs(i,j)

ā

N the probability of collision is low.

This directly implies that when N

This fact is routinely used in security proofs, when showing that no birthday

attack is applicable.

Should the reader want more than an upper bound, the easiest approach is

to compute the probability of the reverse event, i.e., the probability to get no

collisions when drawing N elements among N . This probability is exactly:

N ā’1

N ā’i N!

=N . (6.2)

N N Ā· (N ā’ N )!

i=0

Then, using Stirling formula or even better upper and lower bounds derived

from the Stirling series, we can get a very precise estimate for the desired

probability.

6.2.1 Generalizations

In some cryptographic contexts, it is interesting to generalize the analy-

sis. One important generalization is the existence of collisions between two

diļ¬erent sets. Another frequently encountered issue is the existence of mul-

ticollisions, i.e., the existence of 3, 4 or more random elements sharing a

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 191

common value. For these generalizations, we only make a simpliļ¬ed heuristic

analysis based on the expected number of (multi)collisions assuming indepen-

dence. This simpliļ¬ed analysis can be reļ¬ned to give upper and lower bounds

as in the case of collisions. However, in most cases, this is not necessary and

the simple estimate suļ¬ces.

Collisions between two sets. In this generalization, we are given two

subsets, each obtained by drawing at random without replacement from a

large set. We denote by N1 and N2 the respective cardinality of the subset

and by N the cardinality of the set. By construction, there is no collision

within any single subset and we are interested by collisions between elements

of the ļ¬rst set and elements of the second one. Since N1 Ā· N2 pairs of elements

can be constructed, the expected number of collisions is:

N1 Ā· N2

.

N

When the two subsets are of the same size N1 = N2 = N , this expected

number of collisions lies between the expectation we had for a single subset of

N elements and the expectation for a subset of size 2N . Note that considering

a subset of size 2N is quite natural, since it is the size of the union of the two

considered subsets.

Multicollisions. For multicollisions, as for collisions, two subcases may be

considered. Either we have a single subset and search for diļ¬erent elements

with the same value. Or we have diļ¬erent subsets and want an element

common to all. In short, a multicollision involving elements is called a -

multicollision. Making our usual heuristic analysis under an independence

hypothesis, we ļ¬nd that the expected number of -multicollisions in a subset

of size N chosen among N elements is:

N +1ā’i N

i=1

ā . (6.3)

! Ā· N ā’1 ā’1

!Ā·N

For a -multicollisions between subset of respective sizes N1 Ā· Ā· Ā· N we ļ¬nd

an expected number equal to:

i=1 Ni

N ā’1

From these expected numbers, assuming that remains small enough to

N ( ā’1)/ the probability of -

neglect the ! factor, we ļ¬nd that for N

multicollisions within a subset remains small.

Non-uniform statistical distributions. Up to this point, when looking

for collisions, we assumed a uniform random distribution for the would-be

Ā© 2009 by Taylor and Francis Group, LLC

192 Algorithmic Cryptanalysis

colliding objects. In practice, this is not always the case and we may in some

cases be looking for collisions under other statistical distributions. Assuming

that the random objects remain independent from each other, the probability

of collisions is always larger with a non-uniform distribution. This comes

from the higher probability of collision within a single pair of randomly drawn

objects. Indeed, assume that we draw at random among N values and that

value i is taken with probability pi then the probability of collision is:

N

p2 . (6.4)

i

i=1

N

Under the additional condition i=1 pi = 1 this probability is maximized

when all pi values are equal to 1/N . A more precise analysis of collisions in

hash functions is presented for the unbalanced case in [BK04].

Finally, when the objects are not drawn independently from each other, we

cannot say much about collisions. Depending on the precise details, collisions

may either be more frequent or vanish completely. In the non-independent

case, a speciļ¬c analysis is required for each speciļ¬c problem.

6.3 Finding collisions

A natural algorithm question given a list of elements is to check whether

this list contains a collision or not. The ļ¬rst idea that comes to mind is to

consider all pairs of elements in the list and to test for equality. This approach

involves two intricated loops and requires N Ā·(N ā’1)/2 tests. For cryptanalytic

purposes, this algorithm is dreadful, because it takes back the edge that the

existence of collisions gave us. As a consequence, we need better algorithms

for this purpose. Ideally, we would like to obtain a linear time algorithm.

However, unless non-standard assumptions are made about the computing

device, it is not known how to solve this problem.

Still, there are several algorithmic techniques that allow us to ļ¬nd collisions

in quasi-linear time, i.e., with O(N log N ) operations for a list of N elements.

These techniques involve sorting, hashing, balanced trees or a mix of those.

Before delving into the algorithmic details, let us discuss why these tech-

niques are helpful to ļ¬nd collisions.

Collisions ļ¬nding by sorting. If we can sort eļ¬ciently, then the problem

of ļ¬nding collisions or multi-collisions is reduced to the easier problem of

ļ¬nding collisions within a sorted list. Of course, sorting ļ¬rst requires a total

order on the values we are considering. However, for the purpose of collision

ļ¬nding, the precise choice of this order is irrelevant, the only property we need

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 193

is shared by all orders: equal elements are necessarily neighbors in a sorted

list. As a consequence, ļ¬nding a collision in a sorted list is very simple, it

suļ¬ces to read the list in order and compare each element with its immediate

successor. If there are collisions in the list, we necessarily ļ¬nd some. However,

as stated the algorithm may miss some collisions. Assume that we have a triple

of equal elements. After sorting, they can be found in positions i, i + 1 and

i + 2. The method described above locates the collision in the pair (i, i + 1), it

also detects the collision (i+ 1, i+ 2). However, it misses the collision (i, i+2).

Fixing this problem is easy: when a ļ¬rst collision is detected for some value,

say in (i, i + 1), it suļ¬ces to scan the list forward until a diļ¬erent element is

detected. After this scanning, we know that all elements in the range [i, i + Ī“]

are equal. Generating the corresponding Ī“ Ā· (Ī“ + 1)/2 collisions is easily done.

Algorithm 6.1 fully describes the way to generate all collisions in a sorted list.

Algorithm 6.1 Generating all collisions in a sorted list

Require: Input a sorted array X of N elements

for i from 1 to n ā’ 1 do

if X[i] = X[i + 1] then

Assert: First collision detected for the value X[i]

Let Ī“ = 1

while i + Ī“ < n and X[i] = X[i + Ī“ + 1] do

Increment Ī“

end while

for j from 0 to Ī“ ā’ 1 do

for k from j + 1 to Ī“ do

Print ā˜Collision between positions i + j and i + kā™

end for

end for

Let i āā’ i + Ī“ (to skip over the values equal to X[i])

end if

end for

Since the order chosen for sorting does not aļ¬ect this collision ļ¬nding al-

gorithm, it is not necessary to have a naturally ordered set to ļ¬nd collisions.

If the set is not naturally ordered, a simple way to go is to view the binary

representation of the elements in the set as the number encoded by the same

binary string and then to sort these numbers. This order is meaningless, in

the sense that it is not in any way related to the semantics of the elements.

However, it suļ¬ces to ļ¬nd collisions.

Collisions ļ¬nding by sorting one of two lists. When looking for colli-

sions between two lists, i.e., for common elements, several methods are pos-

Ā© 2009 by Taylor and Francis Group, LLC

194 Algorithmic Cryptanalysis

sible. The ļ¬rst idea is to re-use the technique we used in the single list case.

Simply merge both lists, while associating to each value a tag that remembers

its original list. Then sort and look for collisions in the merge lists. Only

keep the collisions involving one element from each original list. Of course,

this approach is not optimal and has several drawbacks. In particular, the

fact that an additional bit of memory is required to keep track of the original

list is extremely cumbersome. Instead, it is much better to devise a speciļ¬c

method. The next idea probably is to sort both lists and then to look for

collisions in the sorted lists. To illustrate the technique used to look up the

collisions, imagine that the sorted lists are written on two sheets of paper. Put

your left index at the top of one list and your right index at the top of the

other. At each step of the comparison, move down by one position the ļ¬nger

corresponding to the smallest of the two elements. If at any time the elements

below both ļ¬ngers are equal, this detects a collision. This basic procedure is

going to be used as part of the merge sort Algorithm 6.7, so we do not write

down for now. Finally, the best way to proceed is to break the symmetry

between the two lists, just sorting one of then, preferably the shortest one.

Once this is done, take elements of the other lists one by one and try to locate

them in the sorted list. If we ļ¬nd any one of them, we have a collision. The

advantage of this approach is that we only need to store the shortest list in

main memory, the other one can be read from disk during the collision search.

The method can even be used when the second list is not available at the

start of the computation but produced online after that. In a cryptanalytic

setting, this can be extremely useful, for example, the second list could be

obtained by observing ciphertext blocks during an encrypted communication.

The key fact which makes this technique eļ¬cient is that ļ¬nding an element

in a sorted list can be done eļ¬ciently using a dichotomy search, given as

Algorithm 6.2. This way of searching needs about log2 N operations to ļ¬nd

an element within a sorted list of N elements. Moreover, if the element is

not present in the sorted list, the algorithm can return the position where it

would ļ¬t: at the start, at the end or at some place between two consecutive

elements.

Collisions ļ¬nding without sorting. In order to better understand why

it is possible to detect collisions without sorting, let us perform a thought

experiment, using a non-standard computer architecture. This non-standard

computer has access to a very large amount of direct access memory, initialized

for free to a special value ā„ upon start-up. With such a computer, it is possible

to have a memory size not bounded by the running time. Note that with

Turing machines this is not possible because they do not oļ¬er direct access to

the memory but only sequential access. With a conventional computer, it is

not possible either since the memory initialization never comes for free. On our

hypothetical computer, ļ¬nding collisions is very simple. For each element Xi

in the list, interpret Xi as a number, view this number as a memory address,

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 195

Algorithm 6.2 Dichotomy search

Require: Input an array X of N elements and a value Y

Let start āā’ 1

Let end āā’ N

if Y < X[1] then

Output ā˜Y not in list, its place is at the startā™

end if

if Y > X[N ] then

Output ā˜Y not in list, its place is at the endā™

end if

if Y = X[N ] then

Output ā˜Y is in list, in position N ā™

end if

while start + 1 < end do

Assert: We have X[start] ā¤ Y < X[end]

Let mid āā’ start+end

2

if Y < X[mid] then

end āā’ mid

else

start āā’ mid

end if

end while

if Y = X[start] then

Output ā˜Y is in list, in position startā™

else

Output ā˜Y not in list, its place is right after position startā™

end if

Ā© 2009 by Taylor and Francis Group, LLC

196 Algorithmic Cryptanalysis

check that the address is non-initialized and then write i at this address. If

an already initialized address is encountered, then we have found a collision

between Xi and Xj (assuming that the address contained the value j). Of

course, this approach is not feasible; however, sorting through hashing can

be seen as a practical way of implementing it. Also, ļ¬nding collisions with a

balanced tree can depending on the point-of-view be considered either as a

hidden sort or as another implementation of the large memory machine.

6.3.1 Sort algorithms

Sorting is widely encountered in computer science. In particular, it is one of

the favorite problems of computer science teachers. The main reason proba-

bly is that good sorting algorithms are more eļ¬cient than would be expected

by the uninitiated, very elegant and tough to understand. They are also

optimal at least when considered as generic algorithms. In this section, we

ļ¬rst present an overview of some sort algorithms before considering imple-

mentation issues. The overview is further divided into two parts. The ļ¬rst

part contains quadratic, asymptotically uneļ¬cient, algorithms. The second

describes asymptotically fast algorithms. The selection of sort algorithms

presented here is somewhat arbitrary and based on simplicity and usefulness

criteria. Many more sort algorithms do exist, such as comb sort, or smooth

sort. They are not included in this selection.

6.3.1.1 Quadratic algorithms for sorting

6.3.1.1.1 Bubble sort. Bubble sort is probably the conceptually simpler

of all sort algorithms. It starts from an unsorted list of elements, looks at

the current list to see if any pair of consecutive elements is in an incorrect

order and repeats this step until no badly ordered pair can be found. To

ļ¬nd out badly ordered pair, the bubble sort simply scans the list of elements

starting at the beginning and going straight to the end of the list. This is

called a pass on the list. It then performs successive passes, until a full pass

without a swap occurs, at which point the algorithm stops. It is easy to check

that if a pass has nothing to do, then each element is smaller than the next,

thus by transitivity the list is fully ordered. In order to bound the running

time of the bubble sort, it is useful to remark that after the ļ¬rst pass, the

largest element in the list has been moved into place at the end of the list.

After two passes, the largest two elements are in place and so on . . . As a

consequence, there is a growing tail in each pass that never performs any swap.

We can take advantage of this fact and write a slightly improved bubble sort

as Algorithm 6.3. The running time of this algorithm measured in number of

comparisons is at most 1 + 2 + Ā· Ā· Ā· + (n ā’ 1) = n(n ā’ 1)/2.

6.3.1.1.2 Selection sort. Selection sort is a way of sorting which is built

on a simpler procedure: ļ¬nding a minimal element in a list. From this simple

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 197

Algorithm 6.3 Bubble sort

Require: Input an array X of N elements

for pass from 1 to N ā’ 1 do

Let Active āā’ false

for i from 1 to N ā’ pass do

if X[i] > X[i + 1] then

Assert: Incorrectly order pair found

Let Active āā’ true

Exchange X[i] and X[i + 1]

end if

end for

if Active = false then

Abort loop

end if

end for

Output sorted array X

Algorithm 6.4 Find minimal element

Require: Input an array X[start Ā· Ā· Ā· end]

Let mini āā’ start

for i from start + 1 to end do

if X[i] < X[mini] then

Let mini āā’ i

end if

end for

Output position of smallest element, i.e., mini

Ā© 2009 by Taylor and Francis Group, LLC

198 Algorithmic Cryptanalysis

procedure, sorting is easy: the ļ¬rst element in the sorted list is the minimal

element and sorting the remaining elements can be done by repeating the same

idea. Of course, by symmetry, it is also possible to ļ¬nd a maximal element

and sort by placing the largest element at the end of the list. Since the time to

ļ¬nd an element is linear in the size of the list N , selection sort, which requires

N such passes, is a quadratic algorithm. The search for a minimal element is

given as Algorithm 6.4 and the selection sort as Algorithm 6.5.

Algorithm 6.5 Selection sort

Require: Input an array X of N elements

for pass from 1 to n ā’ 1 do

Find the position i of the minimum element in X[pass Ā· Ā· Ā· n].

Swap X[i] and X[pass]

end for

Output sorted array X

6.3.1.1.3 Insertion sort. A well-known sort algorithm in the real life is

the way we proceed to sort cards. The basic idea is simple: put the unsorted

cards in a stack, draw one card at a time from the stack and place it in

your hand. Each time a card is to be placed, locate the correct position

among the already sorted cards in your hand and insert it there. In computer

science, this is called insertion sort. In order to perform this algorithm, we

need to eļ¬ciently locate the right position in the already sorted list using the

dichotomy search of Algorithm 6.2. We also need to be able to insert the new

element in the correct position quickly. Surprisingly, this apparently simple

step is the catch which makes insertion sort uneļ¬cient. The reason is that in

general a new element needs to be inserted somewhere in the middle of the

list. Since there is no room at that place, we need to make some, without

disordering the list. With cards, it is easy, when you insert one, the others

move to let it ļ¬t in. With elements in an array, we need to move them one

by one to make room. On average, for each insertion, half the elements in

the list need to be displaced. Thus each insertion requires linear time and the

insertion sort, given by Algorithm 6.6, is quadratic.

6.3.1.2 Fast algorithms for sorting

Beyond their purpose, all fast sort algorithms that we present here but one

have a common point. Except heap sort, all of them are recursive algorithms

based on the divide and conquer approach. Using a linear time transforma-

tion called a stage, they reduce the problem of sorting a list to the problem

of sorting two smaller lists of roughly half-size. Of course, once we reach

Ā© 2009 by Taylor and Francis Group, LLC

The birthday paradox: Sorting or not? 199

Algorithm 6.6 Insertion sort

Require: Input an array X of N elements

for i from 2 to N do

Assert: List from 1 to i ā’ 1 is sorted

Let Y āā’ X[i]

Using dichotomy, ļ¬nd the correct place k for Y in X[1 Ā· Ā· Ā· i ā’ 1] (The end

position is encoded by i).

for j from i down to k + 1 do

Let X[j] āā’ X[j ā’ 1]

end for

Let X[k] āā’ Y

end for

Output sorted array X

extremely small lists of zero or one element we stop. As a consequence, the

number of stages is limited by the number of integer divisions by two that

can be performed, i.e., log2 N . Since the stages take linear time, this yields

algorithms with complexity O(N log N ).

ńņš. 7 |