<<

. 7
( 18)



>>

W (i) [1] W (i+1) [6] W (i+2) [1] W (i+3) [31] W (i+4) [31] W (i+5) [31]

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
( 18)



>>