Chosen-prefix Collisions for MD5
and Applications
Marc Stevens1 , Arjen Lenstra2 and Benne de Weger3
1
CWI, Amsterdam, The Netherlands
EPFL IC LACAL, Station 14, CH-1015 Lausanne, Switzerland,and Alcatel-Lucent Bell Laboratories
3
EiPSI, Faculty of Mathematics and Computer Science, TU Eindhoven
P.O. Box 513, 5600 MB Eindhoven, The Netherlands
2

Abstract. We present a novel, automated way to find differential paths
for MD5. As an application we have shown how, at an approximate
expected cost of 239 calls to the MD5 compression function, for any
two chosen message prefixes P and P 0 , suffixes S and S 0 can be constructed such that the concatenated values P kS and P 0 kS 0 collide underMD5. The practical attack potential of this construction of chosen-prefix
collisions is of greater concern than the MD5-collisions that were published before. This is illustrated by a pair of MD5-based X.509 certificates one of which was signed by a commercial Certification Authority(CA) as a legitimate website certificate, while the other one is a certificate for a rogue CA that is entirely under our control (cf. http://
www.win.tue.nl/hashclash/rogue-ca/). Other examples, such as MD5colliding executables, are presented as well. More details can be foundon http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/.

1

Introduction

In August 2004 at the rump session of the annual Crypto conference in Santa
Barbara, Xiaoyun Wang (cf. [30]) presented a pair of two-block messages thatcollide under MD5 using the standard initial value for the chaining variable(in this paper the chaining variable will be denoted by IHV, for Intermediate
Hash Value). The details of the construction were presented by Wang and Yu
in [33]. It describes a manually found differential path for MD5 and how it allows
computation of a new collision in a few hours of CPU time.
Although Wang’s random looking collision blocks by themselves do not poseany danger, it was shown in [14] and [21] how those original collisions can beused to mislead integrity checking software. Furthermore, it was immediately
clear that the collision finding method works not just for the standard initialvalue, but for any value of the chaining variable. This freedom to choose the
IHV allowed several authors to use the construction for slightly more ulterior
purposes, e.g. by inserting both collision blocks in different Postscript documentsthat collide under MD5 (cf. [7]).

Although none of these developments spoke in favor of continued usage ofMD5, the abuse potential of these types of collisions was limited. Initially, serious
misuse was believed to be prevented by the lack of control over the contents of thecollision blocks. In [18] it was shown, however, that for any pair of meaninglessdata (M, M 0 ) a suffix T can easily be found such that both concatenations
M kT and M 0 kT are fully meaningful. This allows the following construction.
First, for any meaningful common prefix P , collision blocks (M, M 0 ) may beconstructed using Wang’s approach such that P kM and P kM 0 collide underMD5. Even though P kM and P kM 0 can be expected to be partially meaningless,an appendage T can subsequently be calculated such that both P kM kT and
P kM 0 kT are fully meaningful. Furthermore, due to the incremental structureof MD5, they also still collide under MD5. This shows that the argument that
Wang’s MD5-collisions are mostly harmless because of their lack of structure is inprinciple invalid. The above construction allowed the realization of two different
X.509 certificates with identical Distinguished Names and identical MD5-based
signatures but different public keys (cf. [18]). Though undesirable, such pairs ofcertificates do not affect anyone’s security.
Threatening abuse scenarios did not emerge due to another, more severe limitation, namely that both documents must have identical IHVs at the point where
the collision blocks are inserted. Because this requirement is most naturally fulfilled by making the documents identical up to that point, we call such collisions
identical-prefix collisions. In the above example, P would be the identical prefix.
The most important contribution of this paper is the removal of the identicalprefix condition to attain MD5 collisions. We show how any pair of IHVs can bemade to collide under MD5 by appending properly chosen collision blocks. Moreprecisely, we show how, for any two chosen message prefixes P and P 0 , suffixes
S and S 0 can be constructed such that the concatenated values P kS and P 0 kS 0
collide under MD5. Such collisions will be called chosen-prefix collisions (thoughdifferent-prefix collisions would have been appropriate as well). Our construction
is based on a birthdaying technique combined with a novel, automated way tofind differential paths for MD5. It has an approximate expected cost of 239 calls
to the MD5 compression function. In practical terms, this translates to abouta day on a standard quad-core PC per chosen-prefix collision. This is a notable
improvement over 6 months on thousands of PCs as we reported earlier in theconference version [28] of this paper.
Chosen-prefix collisions have a greater threat potential than identical-prefix
ones. Using the diamond construction from Kelsey and Kohno (cf. [15]) alongwith chosen-prefix collisions, any number of documents of one’s choice can bemade to collide after extending them with relatively short and innocuously looking appendages that can easily remain hidden to the unsuspicious reader whenpopular document formats (such as PDF, Postscript, or MS Word) are used. We
illustrate this in Section 4.3 with a Nostradamus attack: 12 different but MD5colliding PDF files, each predicting a different winner of the 2008 US Presidential
elections, where the common hash serves as commitment to our prediction of theoutcome. Our prediction was correct.
2

Similarly, chosen-prefix collisions can be used to mislead, for instance, download integrity verification of code signing schemes, by appending collision blocks
to executables. Details, and how it improves upon previous such constructions,can be found in Section 4.4.
The killer application of MD5-collisions, however, would target the core of
the Public Key Infrastructure (PKI) and truly undermine its security (cf. Section 4.1 of [28]). The most obvious way to realize this would be by constructing
colliding certificates, i.e., certificates for which the to-be-signed parts have thesame cryptographic hash and therefore the same digital signature. This is undesirable, because the signature of one of the to-be-signed parts, as provided by a
Certification Authority (CA), is also a valid signature for the other to-be-signed
part. Thus, this gives rise to a pair of certificates, one of which is legitimate, but
the other one is a rogue certificate.
A truly security undermining construction of colliding certificates however
seemed to be out of reach. As mentioned in the conference version [28] of thispaper, chosen-prefix collisions allow us to construct two X.509 certificates withdifferent Distinguished Names and different public keys, but identical MD5-based
signatures. This improves upon the construction from [18] mentioned above, but
is hardly more threatening due to two problems. In the first place, we need fullcontrol over the prefixes of the certificates’ to-be-signed parts, to be able tocalculate the collision blocks. When using a ‘real life’ CA, however, that CA has
final control over the contents of one of the to-be-signed parts: in particular,
it inserts a serial number and a validity period. Furthermore, our construction
as in [28] results in 8192-bit RSA moduli, which is quite a bit longer than the2048-bit upper bound that is enforced by some CAs.
It was pointed out to us by three of our coauthors on [29] that there arecircumstances where, with sufficiently high probability, the first of these two
problems can be circumvented. Naively, one would expect that a somewhat more
extensive search would suffice to address the remaining problem of reducing thelength of the RSA moduli to a generally acceptable 2048 bits. Substantially more
extensive improvements to all stages of the chosen-prefix construction from [28]were required, though. This is a nice illustration of scientific progress being driven
by practical applications. Also, more computational power had to be brought tobear to deal with the timing restrictions of reliably predicting the CA’s contribution. Ultimately this led to the rogue CA certificate mentioned in the abstract,
generated in about a day on a cluster of 215 PlayStation 3 game consoles. Fromthe heartwarming industry reception of our rogue CA construction, which isfurther described in Section 4.2, it must be concluded that we finally managed
to present a sufficiently convincing argument to discontinue usage of MD5 fordigital signature applications.
The possibility of chosen-prefix collisions was mentioned already in [9, Section 4.2 case 1] and, in the context of SHA-1, in [4] and on http://www.iaik.
tugraz.at/content/research/krypto/sha1/. This paper is an updated version of [28], incorporating the improvements mentioned above and as describedin [27] and [29]. The main improvements are a new family of differential paths,
3

a more powerful birthdaying procedure which reduces the overall complexity
from 250 to 239 MD5 compression function calls and introduces flexibility inthe birthdaying complexity to allow for variability in the expected number ofnear-collision blocks, a time-memory trade-off, a much improved implementation exploiting the wide variety of features of a cluster of PlayStation 3 game
consoles, and the new applications mentioned above.
Section 2 gives a high level overview of our method to construct chosen-prefix
collisions. Section 3 presents the method in full detail. The three proof of concept
applications are presented in Section 4.
Another application of our automated differential path finding method is a
speedup of the identical-prefix collision attack by Wang et al. In combination
with the idea of tunnels from Klima [17] collisions can be found in 225 MD5compression function calls, see [27]. Source and binary code for this improvement is available on http://www.win.tue.nl/hashclash/). Note that Xie, Liuand Feng [34] used a different method for identical-prefix collisions, reaching acomplexity of 221 MD5 compression function calls, and that in the meantime
identical-prefix collisions for MD5 can be found in 216 MD5 compression function calls [29]. This new identical-prefix collision attack is used in Section 3.10 toconstruct very short chosen-prefix collisions with complexity of about 253.2 MD5compressions, where the collision-causing suffixes are only 596 bits long insteadof several thousands of bits.

2

Chosen-prefix collisions for MD5, overview

Given two arbitrarily chosen messages, we first apply padding to the shorterof the two, if any, to make their lengths equal. This is unavoidable, because
Merkle-Damgård strengthening, involving the message length, is applied after
the last message block has been compressed by MD5. We impose the additional
requirement that both resulting messages are a specific number of bits (such as
64 or 96) short of a whole number of blocks. In principle this can be avoided, but
it leads to an efficient method that allows relatively easy presentation. All theserequirements can easily be met, also in applications with stringent formatting
restrictions.
Given this message pair, we modify a suggestion by Xiaoyun Wang (private
communication) by finding a pair of k-bit values that, when appended to the lastincomplete message blocks, results in a specific form of difference vector between
the IHVs after application of the MD5 compression function to the extended
message pair. Finding the k-bit appendages can be done using a birthdaying
procedure.
The specific form of difference vector between the IHVs that is aimed for
during the birthday search is such that the difference pattern can relatively easily
be removed compared to the more or less random difference pattern one may
expect given two arbitrarily chosen prefixes. Removing the difference pattern isdone by further appending to the messages a sequence of near-collision blocks.
Each pair of near-collision blocks targets a specific subpattern of the remaining4

differences. For each such subpattern we use an automated, improved version of
Wang’s original approach to construct a new differential path, as described indetail in Section 3 below, and subsequently use the differential path to constructa pair of near-collision blocks. Appending those blocks to the two messages
results in a new difference vector between the new IHVs from which the targeted
subpattern has been eliminated compared to the previous difference vector. The
construction continues as long as differences exist.
How the various steps involved in this construction are carried out and how
their parameters are tuned depends on what needs to be optimized. Extensive
birthdaying can be used to create difference patterns that require a small numberof pairs of near-collision blocks. When combined with a properly chosen large
family of differential paths, a single pair of near-collison blocks suffices to complete the collision right away. However, it may make the actual near-collision
block construction quite challenging, which leads to the intuitively expected
result that finding very short chosen-prefix collision-causing appendages is relatively costly. On the other side of the spectrum, fast birthdaying combined witha smaller family of differential paths leads to the need for many successive pairsof near-collision blocks, each of which can quickly be found: if one is willing toaccept long chosen-prefix collision-causing appendages, the overall construction
can be done quite fast. Between the two extremes almost everything can be varied: number of near-collision blocks, their construction time given the differential
path, time to find the full differential path, birthdaying time, birthdaying spacerequirements, etc., leading to a very wide variety of ‘optimal’ choices.
The next section contains the details of the various steps in this process, andhow the steps are best glued together depending on the circumstances. Application scenarios that impose different restrictions on the chosen-prefix collisions
are then presented in Section 4.

3

Chosen-prefix collision construction for MD5, details

In this section we fix some notation in Section 3.1 and give a description of MD5
in Section 3.2. In Section 3.3 an outline of the chosen-prefix collision construction
is given; this includes a short description of the birthday search referred to in
Section 2, the further details of which can be found in Section 3.4. Differential
paths are introduced in Section 3.5 and Sections 3.6.1 through 3.6.6 describe how
to construct partial and full differential paths. Collision finding — the search for
actual near-collision blocks that satisfy a given differential path — is treatedin Section 3.7 and an optional differential path preprocessing step to improve
collision finding is presented in Section 3.7.3. Section 3.8 gives some details of our
implementations and the complexity analysis is treated in Section 3.9. Finally,
we present a practical chosen-prefix collision attack using a single near-collision
block in Section 3.10.
53.1

Preliminaries

MD5 operates on 32-bit words (v31 v30 . . . v0 ) with vi ∈ {0, 1}, that are identified
P31
with elements v = i=0 vi 2i of Z/232 Z and referred to as 32-bit integers. In thispaper we switch freely between these representations.
A binary signed digit representation (BSDR) for a 32-bit word X is definedas (ki )31
i=0 , where31
XX=
2i ki , ki ∈ {−1, 0, +1}.
i=0Many different BSDRs exist for any non-zero X. The weight of a BSDR isthe number of non-zero ki ’s. A particularly useful BSDR is the Non-AdjacentForm (NAF), where no two non-zero ki ’s are adjacent. The NAF is not uniquesince we work modulo 232 (making k31 = +1 equivalent to k31 = −1), but
uniqueness of the NAF can be enforced by choosing k31 ∈ {0, +1}. Among the
BSDRs of an integer, the NAF has minimal weight (cf. [5]). It can easily be
P31icomputed as NAF(n) = (ai − bi )31
i=0 where ai , bi ∈ {0, 1} such thati=0 ai 2 =P
31
n + b n2 c mod 232 and i=0 bi 2i = b n2 c .
Integers are denoted in hexadecimal as, for instance, 1E16 and in binary as
000111102 . For bitstrings X and Y we use the following notation:– X ∧ Y is the bitwise AND of X and Y ;– X ∨ Y is the bitwise OR of X and Y ;– X ⊕ Y is the bitwise XOR of X and Y ;– X is the bitwise complement of X;
for X, Y ∈ Z/232 Z:– X[i] is the i-th bit of the regular binary representation of X;– X + Y resp. X − Y is the addition resp. subtraction modulo 232 ;– RL(X, n) (resp. RR(X, n)) is the cyclic left (resp. right) rotation of X by n
bit positions:
RL(10100100 . . . 000000012 , 5) = 100 . . . 00000001101002 ;and for a 32-digit BSDR X:– X[[i]] is the i-th signed bit of X;– RL(X, n) (resp. RR(X, n)) is the cyclic left (resp. right) rotation of X by npositions.
– w(X) is the weight of X.
For chosen message prefixes P and P 0 we seek suffixes S and S 0 such thatthe messages P kS and P 0 kS 0 collide under MD5. In this paper any variable
X related to the message P kS or its MD5 calculation, may have a corresponding variable X 0 related to the message P 0 kS 0 or its MD5 calculation. Furthermore, for such a ‘matched’ variable X ∈ Z/232 Z we define δX = X 0 − X and∆X = (X 0 [i] − X[i])31
i=0 , which is a BSDR of δX. For a matched variable Z
that consist of tuples of 32-bit integers, say Z = (z1 , z2 , . . .), we define δZ as(δz1 , δz2 , . . .).
6

3.2

Description of MD5

3.2.1 MD5 overview
MD5 works as follows, cf. [25]:1. Padding. Pad the message: first a ‘1’-bit, next the least number of ‘0’ bits
to make the bitlength equal to 448 mod 512, and finally the bitlength of theoriginal unpadded message as a 64-bit little-endian integer. As a result the
total bitlength of the padded message is 512N for a positive integer N .
2. Partitioning. Partition the padded message into N consecutive 512-bit blocks
M1 , M2 , . . . , MN .
3. Processing. To hash a message consisting of N blocks, MD5 goes throughN + 1 states IHVi , for 0 ≤ i ≤ N , called the intermediate hash values. Eachintermediate hash value IHVi consists of four 32-bit words ai , bi , ci , di . For
i = 0 these are fixed public values:(a0 , b0 , c0 , d0 ) = (6745230116 , EFCDAB8916 , 98BADCFE16 , 1032547616 ).
For i = 1, 2, . . . , N intermediate hash value IHVi is computed using the MD5compression function described in detail below:
IHVi = MD5Compress(IHVi−1 , Mi ).
4. Output. The resulting hash value is the last intermediate hash value IHVN ,expressed as the concatenation of the hexadecimal byte strings of the fourwords aN , bN , cN , dN , converted back from their little-endian representation.
3.2.2 MD5 compression function
The input for the compression function MD5Compress(IHV, B) consists of anintermediate hash value IHV = (a, b, c, d) and a 512-bit message block B. The
compression function consists of 64 steps (numbered 0 to 63), split into four
consecutive rounds of 16 steps each. Each step t uses modular additions, a left
rotation, and a non-linear function ft , and involves an Addition Constant ACt
and a Rotation Constant RCt . These are defined as follows (see also Table A-1
in Appendix A):

ACt = 232 |sin(t + 1)| , 0 ≤ t < 64,
(7, 12, 17, 22) for t = 0, 4, 8, 12,(5, 9, 14, 20) for t = 16, 20, 24, 28,(RCt , RCt+1 , RCt+2 , RCt+3 ) =(4, 11, 16, 23) for t = 32, 36, 40, 44,
(6, 10, 15, 21) for t = 48, 52, 56, 60.
The non-linear function ft depends on the round:F (X, Y, Z) = (X ∧ Y ) ⊕ (X ∧ Z) for 0 ≤ t < 16,
G(X, Y, Z) = (Z ∧ X) ⊕ (Z ∧ Y ) for 16 ≤ t < 32,ft (X, Y, Z) =
H(X, Y, Z) = X ⊕ Y ⊕ Z
for 32 ≤ t < 48,
I(X, Y, Z) = Y ⊕ (X ∨ Z)
for 48 ≤ t < 64.
7(1)

The message block B is partitioned into sixteen consecutive 32-bit words m0 ,m1 , . . ., m15 (with little-endian byte ordering), and expanded to 64 words Wt ,for 0 ≤ t < 64, of 32 bits each (see also Table A-1 in Appendix A):mt
for 0 ≤ t < 16,m
for 16 ≤ t < 32,(1+5t) mod 16
Wt =m(5+3t) mod 16 for 32 ≤ t < 48,
m(7t) mod 16
for 48 ≤ t < 64.
We follow the description of the MD5 compression function from [12] because its‘unrolling’ of the cyclic state facilitates the analysis. For each step t the compression function algorithm maintains a working register with 4 state words Qt , Qt−1 ,Qt−2 and Qt−3 and calculates a new state word Qt+1 . With (Q0 , Q−1 , Q−2 , Q−3 ) =(b, c, d, a), for t = 0, 1, . . . , 63 in succession Qt+1 is calculated as follows:= ft (Qt , Qt−1 , Qt−2 ),

 Ft

T
= Ft + Qt−3 + ACt + Wt ,
t
(2)
R t
= RL(Tt , RCt ),
Qt+1 = Qt + Rt .
After all steps are computed, the resulting state words are added to the intermediate hash value and returned as output:
MD5Compress(IHV, B) = (a + Q61 , b + Q64 , c + Q63 , d + Q62 ).
3.3

(3)

Outline of the collision construction

A chosen-prefix collision for MD5 is a pair of messages M and M 0 that consistof arbitrarily chosen prefixes P and P 0 (not necessarily of the same length),
together with constructed suffixes S and S 0 , such that M = P kS, M 0 = P 0 kS 0 ,and MD5(M ) = MD5(M 0 ). The suffixes consist of three parts: padding bitstrings
Sr , Sr0 , followed by ‘birthday’ bitstrings Sb , Sb0 both of bitlength 64 + k, where0 ≤ k ≤ 32 is a parameter, followed by bitstrings Sc , Sc0 each consisting of asequence of near-collision blocks. The padding bitstrings are chosen such thatthe bitlengths of P kSr and P 0 kSr0 are both equal to 512n − 64 − k for a positive
integer n. The birthday bitstrings Sb , Sb0 are determined in such a way thatapplication of the MD5 compression function to P kSr kSb and P 0 kSr0 kSb0 resultsin IHVn and IHV0n , respectively and in the notation from Section 3.2.1, for which
δIHVn has a certain desirable property that is explained below.
The idea is to eliminate the difference δIHVn in r consecutive steps, for000some r, by writing Sc = Sc,1 kSc,2 k . . . kSc,r and Sc0 = Sc,1
kSc,2
k . . . kSc,rfor r
0
pairs of near-collision blocks (Sc,j , Sc,j ) for 1 ≤ j ≤ r. For each pair of near0
collision blocks (Sc,j , Sc,j
) we need to construct a differential path (see Section 3.5 for an informal definition of this term) such that the difference vector
δIHVn+j has lower weight than δIHVn+j−1 , until after r pairs we have reachedδIHVn+r = (0, 0, 0, 0).
8

Table 3-1. Family of partial differential paths using δm11 = ±2p−10 mod 32 .
t

δQt

31
32
33
34

∓2p−10 mod 3200035 − 60

0

61
62
63
64

δFt

δWt

δTt

δRt RCt

0 ±2p−10 mod 32

0

0

0

0

0

0
p−10 mod 32

0 ±2
0
0

0
±2p
±2p

0
0

±2

p−10 mod 32

0
0

±2
0
0

16
·
p

10
15
21

±2p
P 0
p+21+λ mod 32+ w
λ=0 sλ 2Here s0 , . . . , sw0 ∈ {−1, 0, +1} and w0 = min(w, 31 − p) for a fixed w ≥ 0.
Interesting values for the parameter w are between 2 and 5.

Fix some j and let Sc,j consist of 32-bit words mi , for 0 ≤ i < 16. We fix
fifteen of the δmi as 0 and allow only δm11 to be ±2p−10 mod 32 with as yet
unspecified p with 0 ≤ p < 32 (note the slight abuse of notation, since we define
message block differences without specifying the message blocks themselves).
This was suggested by Xiaoyun Wang because with this type of message difference the number of bitconditions over the final two and a half rounds can be kept
low, which turns out to be helpful while constructing collisions. For steps t = 34
up to t = 61 the differential path is fully determined by δm11 as illustrated inTable 3-1. The greater variability for the steps not specified in Table 3-1 does
not need to be fixed at this point. In the last two steps there is a greater degreeof freedom specified by the integer w ≥ 0 that determines which and how many
IHV differences can be eliminated per pair of near-collision blocks. A larger w allows more eliminations by means of additional differential paths. The latter have,
however, a smaller chance to be satisfied because they depend on more (and thus
less likely) carry propagations in ∆Q62 and ∆Q63 . This effect contributes to thecomplexity of finding the near-collision blocks satisfying the differential paths.
Varying w therefore leads to a trade-off between fewer near-collision blocks andincreased complexity to find them.
0This entire construction of the pair of near-collision blocks (Sc,j , Sc,j
) willbe done in a fully automated way based on the choice of w and the values of
IHVn+j−1 and IHV0n+j−1 as specified. It follows from equation (3) and the rows
for t ≥ 61 in Table 3-1 that a differential path with δm11 = ±2p−10 mod 32 would
add a tuplew0X± 0, 2p +sλ 2p+21+λ mod 32 , 2p , 2p 
λ=0

to δIHVn+j−1 , with notation as in Table 3-1. This is set forth in more detailbelow. A sequence of such tuples is too restrictive to eliminate arbitrary δIHVn :9although differences in the b component can be handled using a number of nearcollision block pairs, only identical differences can be removed from the c and dcomponents and the a-component differences are not affected at all. We therefore
make sure that δIHVn has the desirable property, as referred to above, that it
can be eliminated using these tuples. This is done in the birthdaying step where
birthday bitstrings Sb and Sb0 are determined such that δIHVn = (0, δb, δc, δc)for some δb and δc. A δIHVn of this form corresponds to a collision (a, c − d) =(a0 , c0 − d0 ) between IHVn = (a, b, c, d) and IHV0n = (a0 , b0 , c0 , d0 ). With a search
space of only 64 bits, such a collision can easily be found. Since the number ofnear-collision block pairs and the effort required to find them depends in parton the number of bit differences between δb and δc, it may pay off to lower that
number at the cost of extending the birthday search space. For instance, for any
k with 0 ≤ k ≤ 32, a collision (a, c − d, c − b mod 2k ) = (a0 , c0 − d0 , c0 − b0 mod 2k )with a (64 + k)-bit search space results in δc − δb ≡ 0 mod 2k and thus, on
average, just (32 − k)/3 bit differences between δbsuch Sb
qand δc. Determining√ 32+(k/2)
π 64+k0= π2
calls
and Sb can be expected to require on the order of 2 2 2
to the MD5 compression function. More on the birthday search in Section 3.4.

Fig. 1. Above: δIHVs for the colliding certificates with different DistinguishedNames. Below: δIHVs for the colliding website certificate and the rogue CA
certificate.

In the conference version [28] of this paper we used only the differential paths
with δQ64 = ±2p . This forced us to use the harder to satisfy constraint δIHVn =(0, δc, δc, δc)√ with a search space consisting of 96 bits and an expected birthdaying cost of π248 MD5 compression function calls, which is the same as choosing
k = 32 above. The top part of Figure 1 visualizes the corresponding construction of near-collision blocks for our colliding certificate example from [28]. The
horizontal lines represent the NAFs of δIHVi for i = 0, 1, . . . , 21. Because in thisexample P kSr kSb consists of 4 blocks (i.e., n = 4), three identical groups of bit
differences are left at i = 4. As shown in Figure 1 each of these groups consistsof 8 bits. The bits in each group of eight are eliminated simultaneously with thecorresponding bits in the other groups of eight by 8 pairs of near-collision blocks,
10

so that at i = 12 a full collision is reached. The blocks after that are identical
for the two messages, so that the collision is retained.
The lower part of Figure 1 visualizes the improved construction as used forthe example from Section 4.2. In that example P kSr kSb consists of 8 blocks (i.e.,n = 8) and results in a difference vector δIHVn of the form (0, δb, δc, δc). For
any reasonable w, e.g., w = 2, we then select a sequence of differential paths
from the family given in Table 3-1 to eliminate δIHVn . For this example, 3 pairsof near-collision blocks sufficed to reach a collision. In the next paragraphs weshow how this can be done for general δIHVP
n of the form (0, δb, δc,Pδc).
Let, for any such difference vector, δc = i ki 2i and δb − δc = i li 2i , where31(ki )31i=0 and (li )i=0 are NAFs. If δc 6= 0, let i be such that ki 6= 0. Using a
differential path from Table 3-1 with δm11 = −ki 2i−10 mod 32 we can eliminate
the difference ki 2i in δc and δd and simultaneously change δb byiki 2 +

0
i+21+w
Xmod 32lλ 2λ ,

λ=i+21 mod 32

where w0 = min(w, 31 − i). Here one needs to be careful that each non-zero lλis eliminated only once in the case when multiple i’s allow the elimination of lλ .
Doing this for all non-zero ki ’s in the NAF of δc will result in a difference vector(0, δ b̂, 0, 0) where δ b̂ may be different from δb, and where the weight w(NAF(δ b̂))P31
may be smaller or larger than w(NAF(δb)). More precisely, δ b̂ = λ=0 eλ lλ 2λ ,where eλ = 0 if there exist indices i and j with 0 ≤ j ≤ min(w, 31 − i) such thatki = ±1 and λ = 21 + i + j mod 32 and eλ = 1 otherwise.
The bits in δ b̂ can be eliminated as follows. Let (ˆli )31
i=0 = NAF(δ b̂) and let j be
Pj+w0such that ˆlj = ±1 and j − 21 mod 32 is minimal. Then the difference i=j ˆli 2i
with w0 = min(w, 31 − (j − 21 mod 32)) can be eliminated from δ b̂ using δm11 =2j−31 mod 32 , which introduces a new difference 2j−21 mod 32 in δb, δc and δd. Thislatter difference is eliminated using δm11 = −2j−31 mod 32 , which then leads to a
new difference vector (0, δb, 0, 0) with w(NAF(δb)) < w(NAF(δ b̂)). The process
is repeated until all differences have been eliminated.
Algorithm 3-1 summarizes the construction of pairs of near-collision blocks
set forth above. The details of the construction are described in the sections
below.
3.4

Birthday search

A birthday search on a search space V is generally performed as in [22] by iterating a properly chosen deterministic function f : V → V and by assumingthat the points pof V thus visited form a ‘random walk’, also called a trail. Afterapproximately π|V |/2 iterations one may expect to have encountered a collision, i.e., different points x and y such that f (x) = f (y). Because the entire
trail can in practice not be stored and to take advantage of parallelism, different pseudo-random walks are generated, of which only the startpoints, lengths,
and endpoints are kept. The endpoints are ‘distinguished points’, points with11

Algorithm 3-1 Construction of pairs of near-collision blocks.
Given n-block P kSr kSb and P 0 kSr0 kSb0 , the corresponding resulting IHVn and IHV0n ,and a value for w, a pair of bitstrings Sc , Sc0 is constructed consisting of sequencesof near-collision blocks such that M = P kSr kSb kSc and M 0 = P 0 kSr0 kSb0 kSc0 satisfy
MD5(M ) = MD5(M 0 ). This is done by performing in succession steps 1, 2 and 3
below.
1. Let j = 0 and let Sc and Sc0 be two bitstrings of length zero.
2. Let δIHVn+j = (0, δb, δc, δc). If δc = 0 then proceed to step 3. Let (ki )31
i=0 =
NAF(δc) and (li )31
i=0 = NAF(δb − δc). Choose any i for which ki 6= 0 and let
w0 = min(w, 31 − i). Perform steps (a) through (f):(a) Increase j by 1.
(b) Let δSc,j = (δm0 , δm1 , . . . , δm15 ) with δm11 = −ki 2i−10 mod 32 and δmt = 0
for 0 ≤ t < 16 and t 6= 11.
(c) Given δIHVn+j−1 = IHV0n+j−1 − IHVn+j−1 and δSc,j , construct a few differential paths based on Table 3-1 with
0
i+21+w
Xmod 32

δQ61 = 0, δQ64 = −ki 2i −lλ 2λ , δQ63 = δQ62 = −ki 2i .

λ=i+21 mod 32

How this is done is described in Sections 3.5 and 3.6.
0
= Sc,j + δSc,j that satisfy one of the con(d) Find message blocks Sc,j and Sc,jstructed differential paths. How this is done is described in Section 3.7. If
proper message blocks cannot be found, back up to step (c) to find moredifferential paths.
(e) Compute IHVn+j = MD5Compress(IHVn+j−1 , Sc,j ),00
IHV0n+j = MD5Compress(IHV0n+j−1 , Sc,j), and append Sc,j and Sc,jto Sc
0and Sc , respectively.
(f) Repeat step 2
3. Let δIHVn+j = (0, δ b̂, 0, 0). If δ b̂ = 0 then terminate. Let (li )31
i=0 = NAF(δ b̂).
Choose i such that li 6= 0 and i − 21 mod 32 is minimal and let w0 = min(w, 31 −(i − 21 mod 32)). Perform steps (a) through (e) as above with δm11 = 2i−31 mod 32
as opposed to δm11 = −ki 2i−10 mod 32 in step (b) and in steps (c) and (d) with
δQ61 = 0, δQ64 = 2

i−21 mod 32

−

i+w0X
mod 32lλ 2λ , δQ63 = δQ62 = 2i−21 mod 32 .

λ=i

Perform steps (a) through (e) again with δm11 = −2i−31 mod 32 in step (b) andδQ61 = 0, δQ64 = δQ63 = δQ62 = −2i−21 mod 32
in steps (c) and (d). Repeat step 3.

12

an easily recognizable bitpattern depending on |V |, available storage and othercharacteristics. The average length of a walk is inversely proportional to thefraction of distinguished points in V . Because intersecting walks share their endpoints, they can easily be detected. The collision point can then be recomputed
given the startpoints and lengths of the two colliding walks. The expected cost(i.e., number of evaluations of f ) to generate the walks is denoted by Ctr andthe expected cost of the recomputation to determine collision points is denotedby Ccoll .
In our case the search space V and iteration function f depend on an integer
parameter k ∈ {0, 1, 2, . . . , 32} as explained in Section 3.3. The birthday collisionthat we try to find, however, needs to satisfy several additional conditions thatcannot be captured by V , f , or k: the prefixes associated with x and y in abirthday collision f (x) = f (y) must be different, and the required number ofpairs of near-collision blocks may be at most r when allowing differential paths
with parameter w. The probability that a collision satisfies all requirements
depends not only on the choice of r and w, but also on the value for k, and isdenoted by pr,k,w . As a consequence, on average 1/pr,k,w birthday collisions haveto be found.

Table 3-2. Expected birthday costs for k = 0.
k=0
r
16
15
14
13
12
11
10
9
8
7
6
5
4

p

w=0
Ctr
M

p

w=1
Ctr
M

p

w=2
Ctr
M

p

w=3
Ctr
M

5.9 35.27 1MB 1.75 33.2 1MB 1.01 32.83 1MB
1. 32.83 1MB
7.2 35.92 1MB 2.39 33.52 1MB 1.06 32.86 1MB
1. 32.83 1MB
8.71 36.68 1MB 3.37 34.01 1MB 1.27 32.96 1MB 1.04 32.84 1MB
10.45 37.55 1MB 4.73 34.69 1MB 1.78 33.22 1MB
1.2 32.93 1MB
12.45 38.55 1MB 6.53 35.59 1MB 2.78 33.71 1MB 1.66 33.16 1MB
14.72 39.68 2MB 8.77 36.71 1MB 4.34 34.5 1MB 2.61 33.63 1MB
17.28 40.97 11MB 11.47 38.06 1MB 6.54 35.6 1MB 4.18 34.42 1MB
20.16 42.4 79MB 14.62 39.64 2MB 9.38 37.02 1MB 6.46 35.56 1MB
23.39 44.02 732MB 18.21 41.43 21MB 12.88 38.76 1MB 9.52 37.09 1MB
26.82 45.73 8GB 22.2 43.43 323MB 17.02 40.83 9MB 13.4 39.02 1MB
31.2 47.92 161GB 26.73 45.69 8GB 21.78 43.22 241MB 18.14 41.4 20MB
35. 49.83 3TB 31.2 47.92 161GB 27.13 45.89 10GB 23.74 44.2 938MB
34. 49.33 2TB 30.19 47.42 81GB

The columns p, Ctr and M denote the values of − log2 (pr,k,w ), log2 (Ctr (r, k, w)) and theminimum required memory M such that Ccoll (r, k, w, M ) ≤ Ctr (r, k, w), respectively.
See Appendix C for more extensive tables. The values for pr,k,w were estimated from
Algorithm 3-1.

Assuming that M bytes of memory are available and that a single trail requires 28 bytes of storage (namely 96 bits for the start- and endpoint each, and32 for the length), this leads to the following expressions for the birthday search13

costs:s
Ctr (r, k, w) =π · |V |,2pr,k,w

Ccoll (r, k, w, M ) =2.5 · 28 · Ctr (r, k, w),
pr,k,w · M

where |V | = 264+k , and the factor 2.5 is explained in Section 3 of [22].
For M = 70/pr,k,w as given in the last column of Table 3-2 and in the more
extensive tables in Appendix C, the two costs are equal, and the overall expectedbirthday costs becomes 2Ctr (r, k, w). However, if the cost at run time of finding
the trails exceeds the expected cost by a factor λ, then the cost to determine theresulting birthday collisions can be expected to increase by a factor λ2 . Hence,in practice it is advisable to choose M considerably larger. For  ≤ 1, using
M = 70/(pr,k,w · ) bytes of memory will result in Ccoll ≈  · Ctr and the expected
overall birthday search cost will be about (1 + ) · Ctr (r, k, w) MD5 compressions.
3.5

Differential paths and bitconditions

In step (e) of Algorithm 3-1, MD5Compress is applied to the respective intermediate hash values IHV and IHV0 and message blocks B and B 0 . Here, IHV
and IHV0 were constructed in such a way that δIHV has a specific structure, as
set forth above. Furthermore, the blocks B and B 0 were constructed such that
δB has a pre-specified low-weight value (cf. step (b) of Algorithm 3-1) and suchthat throughout the 64 steps of both calls to MD5Compress the propagation ofdifferences between corresponding variables follows a specific precise description,
as determined in step (c) of Algorithm 3-1. In this section we describe how thisdescription, which is called a differential path for MD5Compress, is determinedbased on IHV, IHV0 and δB. According to equations (2),= ft (Q0t , Q0t−1 , Q0t−2 ) − ft (Qt , Qt−1 , Qt−2 ),

δFt

δT
= δFt + δQt−3 + δWt ,
t
(4)
δRt
= RL(Tt0 , RCt ) − RL(Tt , RCt ), andδQt+1 = δQt + δRt .
It follows that neither δFt nor δRt is uniquely determined given the input differences (δQt , δQt−1 , δQt−2 ) and δTt , respectively. Therefore a more flexible tool isrequired to describe in a succinct way a valid propagation of differences, startingfrom IHV = (Q−3 , Q0 , Q−1 , Q−2 ), IHV0 = (Q0−3 , Q00 , Q0−1 , Q0−2 ) and δB and,in our case, resulting in the desired final differences (δQ61 , δQ62 , δQ63 , δQ64 ) as
defined in Table 3-1 and as targeted by step (c) of Algorithm 3-1.
3.5.1 Bitconditions
0
Differential paths are described using bitconditions qt = (qt [i])31
i=0 on (Qt , Qt ),0where each bitcondition qt [i] specifies a restriction on the bits Qt [i] and Qt [i]possibly including values of other bits Ql [i]. As we will show in this section,
we can specify the values of δQt , δFt for all t using bitconditions on (Qt , Q0t ),14

which also determine δTt and δRt = δQt+1 − δQt according to the difference
equations (4). Thus, a differential path can be seen as a 68 × 32 matrix (qt )64
t=−3
of bitconditions. In general, the first four rows (qt )0t=−3 are fully determined by
the values of IHV and IHV0 . Furthermore, in our specific case where δB consistsof just δm11 = ±2d , the final 34 rows (qt )64
t=31 correspond to Table 3-1 and oneof the choices made in step (c) of Algorithm 3-1.
Table 3-3. Differential bitconditions
qt [i] condition on (Qt [i], Q0t [i]) ki.
Qt [i] = Q0t [i]0+
Qt [i] = 0, Q0t [i] = 1 +1
Qt [i] = 1, Q0t [i] = 0 −1Pi
δQt = 31i=0 2 ki and ∆Qt = (ki ).

Table 3-4. Boolean function bitconditions
qt [i]
condition on (Qt [i], Q0t [i])direct/indirect direction0
Qt [i] = Q0t [i] = 0
direct1
Qt [i] = Q0t [i] = 1
direct^Qt [i] = Q0t [i] = Qt−1 [i]indirectbackwardv
Qt [i] = Q0t [i] = Qt+1 [i]indirectforward!
Qt [i] = Q0t [i] = Qt−1 [i]indirectbackwardy
Qt [i] = Q0t [i] = Qt+1 [i]indirectforwardm
Qt [i] = Q0t [i] = Qt−2 [i]indirectbackwardw
Qt [i] = Q0t [i] = Qt+2 [i]indirectforward#Qt [i] = Q0t [i] = Qt−2 [i]indirectbackwardh
Qt [i] = Q0t [i] = Qt+2 [i]indirectforward? Qt [i] = Q0t [i] ∧ (Qt [i] = 1 ∨ Qt−2 [i] = 0)
indirectbackward
q Qt [i] = Q0t [i] ∧ (Qt+2 [i] = 1 ∨ Qt [i] = 0)
indirectforward

Bitconditions are denoted using symbols such as 0, 1, +, -, ^, . . ., as defined inTables 3-3 and 3-4, to facilitate the representation of a differential path. A direct
bitcondition qt [i] does not involve any other indices than t and i, whereas anindirect bitcondition involves one of the row indices t±1 or t±2 as well. Table 33 lists differential bitconditions qt [i], which are direct bitconditions that specify
the value ki = Q0t [i] − Qt [i]. A full row of differential bitconditions qt = (ki )31
i=0
P31
fixes a BSDR of δQt = i=0 2i ki . Table 3-4 lists boolean function bitconditions,which are direct or indirect. They are used to resolve a possible ambiguity in∆Ft [[i]] = ft (Q0t [i], Q0t−1 [i], Q0t−2 [i]) − ft (Qt [i], Qt−1 [i], Qt−2 [i]) ∈ {−1, 0, +1}
that may be caused by different possible values for Qj [i], Q0j [i] given differential
bitconditions qj [i]. As an example, for t = 0 and (qt [i], qt−1 [i], qt−2 [i]) = (., +, -)15

(cf. Table 3-3) there is an ambiguity:
if Qt [i] = Q0t [i] = 0 then ∆Ft [[i]] = ft (0, 1, 0) − ft (0, 0, 1) = −1,
but if Qt [i] = Q0t [i] = 1 then ∆Ft [[i]] = ft (1, 1, 0) − ft (1, 0, 1) = +1.
To resolve this ambiguity the triple of bitconditions (.,+,-) can be replaced by(0,+,-) or (1,+,-) for the two cases given above, respectively.
All boolean function bitconditions include the constant bitcondition Qt [i] =Q0t [i], so boolean function bitconditions do not affect δQt . Furthermore, theindirect boolean function bitconditions never involve bitconditions + or -, sincethose bitconditions can always be replaced by one of the direct ones ., 0 or 1. For
the indirect bitconditions we distinguish between ‘forward’ and ‘backward’ ones,
because that makes it easier to resolve an ambiguity later on in our step-wise
approach. In a valid (partial) differential path one can easily convert forward
bitconditions into backward bitconditions and vice versa.
When all δQt and δFt have been determined by bitconditions then also δTtand δRt = δQt+1 − δQt can be determined, which together describe the bitwiserotation of δTt in each step. This does, however, not imply that the left rotateof δTt over RCt positions is equal to δRt or with what probability that happens.
See also Section 3.6.4.
The differential paths we constructed for several of our examples can be foundat http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/.
3.6

Differential path construction

The basic idea to construct a differential path is to construct a partial lower
differential path over steps t = 0, 1, . . . , 11 and a partial upper differential pathover steps t = 63, 62, . . . , 16, so that the Qi involved in the partial paths meetbut do not overlap. Given the two partial paths, we try to connect them over theremaining 4 steps into one full differential path which hopefully succeeds withsome non-negligible probability. Using many lower and upper differential paths
and trying to connect each combination of a lower and an upper differential
path will eventually result in full differential paths. Constructing the partial
lower path can be done by starting with bitconditions q−3 , q−2 , q−1 , q0 that areequivalent to the values of IHV, IHV0 and then extend this step by step. Similarly
the partial upper path can be constructed by extending the partial paths in
Table 3-1 step by step. In both constructions the transitions between the steps
must be compatible with the targeted message difference δB. To summarize,
step (c) of Algorithm 3-1 in Section 3.3 consists of the following substeps:
c.1 Given IHV and IHV0 , determine the corresponding bitconditions (qi )0i=−3 .
c.2 Generate partial lower differential paths by extending (qi )0i=−3 forward up
to step t = 11. This is explained in Sections 3.6.1 - 3.6.4.
c.3 Generate partial upper differential paths by extending the path specified
by Table 3-1 backward from t = 31 down to t = 16. This is explained in
Section 3.6.5.
16

c.4 Try to connect all pairs of lower and upper differential paths over t =12, 13, 14, 15 to generate as many full differential paths as possible given
the outcome of the two previous steps. This is explained in Section 3.6.6.
3.6.1 Extending differential paths forward
In general, when constructing a differential path one must first fix the message
block differences δm0 , . . . , δm15 . In our particular case this is achieved by the
choice of δSc,j in step (b) of Algorithm 3-1. Suppose we have a partial differential
path consisting of at least bitconditions qt−1 and qt−2 and that the differences
δQt and δQt−3 are known. In step c.2 of Algorithm 3-1, we want to extend thispartial differential path forward with step t resulting in the difference δQt+1 ,bitconditions qt , and additional bitconditions qt−1 , qt−2 (cf. Section 3.6).
We assume that all indirect bitconditions in qt−1 and qt−2 are forward andinvolve only bits of Qt−1 . If we already have qt as opposed to just the value δQt(e.g. q0 resulting from given values IHV, IHV0 ), then we can skip Section 3.6.2
and continue at Section 3.6.3.
3.6.2 Carry propagation
First we select bitconditions qt based on the value δQt . Since we want to construct differential paths with as few bitconditions as possible, but also want tobe able to randomize the process, any low weight BSDR (such as the NAF) of
δQt may be chosen, which then translates into a possible choice for qt as in
Table 3-3. For instance, with δQt = 28 , we may choose qt [8] = ‘+’, or qt [8] = ‘-’and qt [9] = ‘+’ (with in either case all other qt [i] = ‘.’).
3.6.3 Boolean function
For some i, let (a, b, c) = (qt [i], qt−1 [i], qt−2 [i]) be any triple of bitconditions
such that all indirect bitconditions involve only Qt [i], Qt−1 [i] or Qt−2 [i]. For any
such triple (a, b, c) let Uabc denote the set of tuples of values (x, x0 , y, y 0 , z, z 0 ) =(Qt [i], Q0t [i], Qt−1 [i], Q0t−1 [i], Qt−2 [i], Q0t−2 [i]) satisfying it:Uabc = (x, x0 , y, y 0 , z, z 0 ) ∈ {0, 1}6 satisfies bitconditions (a, b, c) .
The cardinality of Uabc indicates the amount of freedom left by (a, b, c). Triples(a, b, c) for which Uabc = ∅ cannot be part of a valid differential path and arethus of no interest. The set of all triples (a, b, c) as above and with Uabc 6= ∅ isdenoted by Ft .
Each (a, b, c) ∈ Ft induces a set Vabc of possible boolean function differences∆Ft [[i]] = ft (x0 , y 0 , z 0 ) − ft (x, y, z):Vabc = {ft (x0 , y 0 , z 0 ) − ft (x, y, z) | (x, x0 , y, y 0 , z, z 0 ) ∈ Uabc } ⊂ {−1, 0, +1}.
A triple (d, e, f ) ∈ Ft with |Vdef | = 1 leaves no ambiguity in ∆Ft [[i]] and istherefore called a solution. Let St ⊂ Ft be the set of solutions.
17For arbitrary (a, b, c) ∈ Ft and for each g ∈ Vabc , we define Wabc,g as thesubset of St consisting of all solutions that are compatible with (a, b, c) and thathave g as boolean function difference:
Wabc,g = {(d, e, f ) ∈ St | Udef ⊂ Uabc ∧ Vdef = {g}} .
For each g ∈ Vabc there is always a triple (d, e, f ) ∈ Wabc,g consisting of direct
bitconditions 01+- that suffices, i.e., fixes a certain tuple in Uabc . This implies
that Wabc,g 6= ∅. Despite this fact, we are specifically interested in bitconditions (d, e, f ) ∈ Wabc,g that maximize |Udef | as such bitconditions maximize theamount of freedom in the bits of Qt , Qt−1 , Qt−2 while fully determining ∆Ft [[i]].
The direct and forward (resp. backward) boolean function bitconditions werechosen such that for all t, i and (a, b, c) ∈ Ft and for all g ∈ Vabc there exists a
triple (d, e, f ) ∈ Wabc,g consisting only of direct and forward (resp. backward)
bitconditions such that{(x, x0 , y, y 0 , z, z 0 ) ∈ Uabc | ft (x0 , y 0 , z 0 ) − ft (x, y, z) = g} = Udef .
These boolean function bitconditions allow one to resolve an ambiguity in an
optimal way in the sense that they are sufficient and necessary.
If the triple (d, e, f ) is not unique, then for simplicity we prefer direct overindirect bitconditions and short indirect bitconditions (vy^!) over long indirect ones (whqm#?). For given t, bitconditions (a, b, c), and g ∈ Vabc we define
F C(t, abc, g) = (d, e, f ) as the preferred triple (d, e, f ) consisting of direct andforward bitconditions. Similarly, we define BC(t, abc, g) as the preferred triple
consisting of direct and backward bitconditions. These functions are easily determined and should be precomputed. They have been tabulated in Appendix B
in Tables B-1, B-2, B-3 and B-4 grouped according to the four different round
functions F, G, H, I, and per table for all 27 possible triples (a, b, c) of differential
bitconditions.
P31 i
To determine the differences δFt =i=0 2 gi we proceed as follows. For
i = 0, 1, 2, . . . , 31 we assume that we have valid bitconditions (a, b, c) = (qt [i],qt−1 [i], qt−2 [i]) where only c may be indirect. If it is, it must involve Qt−1 [i].
Therefore (a, b, c) ∈ Ft . If |Vabc | = 1, then there is no ambiguity and {gi } = Vabc .
Otherwise, if |Vabc | > 1, then we choose gi arbitrarily from Vabc and we resolve
the ambiguity by replacing bitconditions (a, b, c) by F C(t, abc, gi ). Once all gi
and thus δFt have been determined, δTt is determined as δFt + δQt−3 + δWt .
Note that in the next step t+1 our assumptions hold again, since a is a direct
bitcondition and if b is indirect then it is forward and involves a. Bitconditions
a and b may be new compared to the previous step, namely if the triple (a, b, c)
was replaced by F C(t, abc, gi ).
3.6.4 Bitwise rotation
The integer δTt as just determined does not uniquely determine δRt = RL(Tt0 , n)−RL(Tt , n), where n = RCt (cf. difference equations (4)). In this section we show
how to find the most likely δRt that corresponds to a given δTt , i.e., the v forwhich |{X ∈ Z/232 Z | v = RL(X + δTt , n) − RL(X, n)}| is maximized
18

Any BSDR (k31 , . . . , k32−n , k31−n , . . . , k0 ) of δTt gives rise to a candidate δRtgiven by the BSDR RL((ki ), n) = (k31−n , . . . , k0 , k31 , . . . , k32−n ). Two BSDRs(ki ) and (li ) of δTt result in the same δRt if
31−n
X

2 i ki =

i=0

31−n
X

2i li

and

i=0

31
X

2i ki =

i=32−n31
X

2 i li .

i=32−nThis suggests the following approach. We define a partition as a pair (α, β) of
integers such that α + β = δTt mod 232 , |α| < 232−n , |β| < 232 and 232−n |β. For
any partition (α, β), values ki ∈ {0, ±1} for 0 ≤ i < 32 can be found such that
α=

31−n
X

i

2 ki

and β =

i=031
X

2i ki .

(5)i=32−nWith α + β = δTt mod 232 it follows that (ki ) is a BSDR of δTt . Conversely,with (5) any BSDR (ki ) of δTt defines a partition, which we denote (ki ) ≡ (α, β).
The rotation of a partition (α, β) is defined as
RL((α, β), n) = (2n α + 2n−32 β mod 232 ).
If (ki ) ≡ (α, β), this matches RL((ki ), n). The latter, as seen above, is a candidate
δRt , and we find that different partitions give rise to different δRt candidates.
Thus, to find the most likely δRt , we definep(α,β) = P r[RL((α, β), n) = RL(X + δTt , n) − RL(X, n)]where X ranges over the 32-bit words, and show how p(α,β) can be calculated.
Let x = δTt mod 232−n and y = (δTt − x) mod 232 with 0 ≤ x < 232−n and
0 ≤ y < 232 . This gives rise to at most 4 partitions:• (α, β) = (x, y);• (α, β) = (x, y − 232 ),if y 6= 0;• (α, β) = (x − 232−n , y + 232−n mod 232 ),if x 6= 0;• (α, β) = (x − 232−n , (y + 232−n mod 232 ) − 232 ), if x 6= 0 ∧ y + 232−n 6= 232 .
Because these are all possible partitions, we find that δTt leads to at most 4
different possibilities for δRt . It remains to determine p(α,β) for the above partitions. For each of the 4 possibilities this is done by counting the number of
32-bit words X such that the BSDR defined by ki = (X + δTt )[i] − X[i] satisfies(ki ) ≡ (α, β). Considering the (32−n) low-order bits, the probability that a given
P31−n
α satisfies α = i=0 ki follows from the number r of Y ’s with 0 ≤ Y < 232−nsuch that 0 ≤ α + Y < 232−n : if α < 0 then r = 232−n + α and if α ≥ 0then r = 232−n − α. Hence r = 232−n − |α| out of 232−n Y’s. Now assuming
P31−n
α = i=0 ki , there is no carry to the high-order bits and the same argument
can be used for β/232−n . Hence, we concludep(α,β) =232−n − |α| 232 − |β|232−n − |α| 2n − |β|2n−32
·
=
·
.
232−n
2n
232−n
232
19

Note that these probabilities, corresponding to the at most 4 partitions above,
indeed add up to 1.
We have shown that all δRt that are compatible with a given δTt can easily be determined, including the probabilities that they occur. In Algorithm 31 we choose a partition (α, β) for which p(α,β) is maximal and take δRt =RL((α, β), n). A more straightforward approach (as previously used in practice)would be to use δRt = RL(NAF(δTt ), n). This is in many cases the most likely
choice, and matches our desire to minimize the number of differences in δQt
and therefore also in δTt and δRt . Given δRt , we finally determine δQt+1 as
δQt + δRt .
3.6.5 Extending differential paths backward
Having dealt with the forward extension of step c.2 of Algorithm 3-1 in Sections 3.6.2, 3.6.3 and 3.6.4, we now consider the backward extension of step c.3of Algorithm 3-1 (cf. Section 3.6). The backward construction follows the same
approach as the forward one. Our description relies on the notation introducedin Section 3.6.3.
Suppose we have a partial differential path consisting of at least bitconditions qt and qt−1 and that the differences δQt+1 and δQt−2 are known. In stepc.3 of Algorithm 3-1 we want to extend this partial differential path backwardwith step t resulting in the difference δQt−3 , bitconditions qt−2 , and additional
bitconditions qt , qt−1 . We assume that all indirect bitconditions in qt and qt−1
are backward and only involve bits of Qt−1 .
We choose a low weight BSDR (such as the NAF) of δQt−2 , which thentranslates into a possible choice for qt−2 as in Table 3-3.
P31
As in the last two paragraphs of Section 3.6.3, the differences δFt = i=0 2i gi
are determined by assuming for i = 0, 1, . . . , 31 that we have valid bitconditions(a, b, c) = (qt [i], qt−1 [i], qt−2 [i]) where only a may be indirect. If it is, it must
involve Qt−1 [i]. Therefore (a, b, c) ∈ Ft . If |Vabc | = 1, then there is no ambiguityand {gi } = Vabc . Otherwise, if |Vabc | > 1, then we choose gi arbitrarily from Vabc
and we resolve the ambiguity by replacing bitconditions (a, b, c) by BC(t, abc, gi ).
To rotate δRt = δQt+1 − δQt over n = 32 − RCt bits, we may follow theframework as set forth in Section 3.6.4 with the roles of δRt and δTt reversed:choose a partition (α, β) (of δRt as opposed to δTt ) with maximal probability anddetermine δTt = RL((α, β), n). Finally, we determine δQt−3 = δTt − δFt − δWt
to extend our partial differential path backward with step t. Note that here
also (i.e., as in the last paragraph of Section 3.6.3) in the next step t − 1 ourassumptions hold again, since c is a direct bitcondition and if b is indirect thenit is backward and involves c (where b and c are new if (a, b, c) was replaced by
BC(t, abc, gi )).
3.6.6 Constructing full differential paths
Construction of a full differential path can be done as follows. Assume that forsome δQ−3 and bitconditions q−2 , q−1 , q0 the forward construction as describedin Sections 3.6.1, 3.6.2, 3.6.3, and 3.6.4 has been carried out up to step t =20

11 (cf. step c.2 in Section 3.6). Furthermore, assume that for some δQ64 andbitconditions q63 , q62 , q61 the backward construction as described in Section 3.6.5
has been carried out down to step t = 16 (cf. step c.3 in Section 3.6). For eachcombination of forward and backward partial differential paths thus found, thisleads to bitconditions q−2 , q−1 , . . . , q11 , q14 , q15 , . . . , q63 and differences δQ−3 ,δQ12 , δQ13 , δQ64 .
It remains to try and glue together each of these combinations by finishingsteps t = 12, 13, 14, 15 (cf. step c.4 in Section 3.6) until a full differential path isfound. First, as in the backward extension in Section 3.6.5, for t = 12, 13, 14, 15
we set δRt = δQt+1 − δQt , choose the resulting δTt by left-rotating δRt overn − RCt bits, and determine δFt = δTt − δWt − δQt−3 .

Algorithm 3-2 Construction of Ui+1 from Ui .
Suppose Ui is given as {(δQ12 , δQ13 , δF12 , δF13 , δF14 , δF15 )} if i = 0 or if i > 0
constructed inductively based on Ui−1 by means of this algorithm. For each tuple(q1 , q2 , f1 , f2 , f3 , f4 ) ∈ Ui do the following:
1. Let Ui+1 = ∅ and (a, b, e, f ) = (q15[i], q14 [i], q11 [i], q10 [i]){.} if q1 [i] = 0
2. For each bitcondition d = q12 [i] ∈do{-, +} if q1 [i] = 1
0
3.
Let q1 = 0, −1 or +1 depending on whether d = ‘.’, ‘-’ or ‘+’, respectively
4.
For each different f10 ∈ {−f1 [i], +f1 [i]} ∩ Vdef do
5.
Let (d0 , e0 , f 0 ) = F C(12, def, f10 ) {.} if q2 [i] = 0
6.
For each bitcondition c = q13 [i] ∈do{-, +} if q2 [i] = 1
0
7.
Let q2 = 0, −1 or +1 depending on whether c = ‘.’, ‘-’ or ‘+’, respectively
8.
For each different f20 ∈ {−f2 [i], +f2 [i]} ∩ Vcd0 e0 do
9.
Let (c0 , d00 , e00 ) = F C(13, cd0 e0 , f20 )10.
For each different f30 ∈ {−f3 [i], +f3 [i]} ∩ Vbc0 d00 do
11.
Let (b0 , c00 , d000 ) = F C(14, bc0 d00 , f30 )12.
For each different f40 ∈ {−f4 [i], +f4 [i]} ∩ Vab0 c00 do
13.
Let (a0 , b00 , c000 ) = F C(15, ab0 c00 , f40 )14.
If (q1 − 2i q10 , q2 − 2i q20 , f1 − 2i f10 , f2 − 2i f20 , f3 − 2i f30 , f4 − 2i f40 )is not in Ui+1 yet, insert it in Ui+1

We aim to complete the differential path by finding new bitconditions q10 ,
q11 , . . ., q15 that are compatible with the original bitconditions and that resultin the required δQ12 , δQ13 , δF12 , δF13 , δF14 , δF15 .
An efficient way to find the missing bitconditions is to first test if they exist,
and if so to backtrack to actually construct them. For i = 0, 1, . . . , 32 we attempt
to construct a set Ui consisting of all tuples (q1 , q2 , f1 , f2 , f3 , f4 ) of 32-bit integers
with qj ≡ fk ≡ 0 mod 2i for j = 1, 2 and k = 1, 2, 3, 4 such that for all ` =0, 1, . . . , i − 1 there exist compatible bitconditions q10 [`], q11 [`], . . . , q15 [`] that21

determine ∆Q11+j [[`]] and ∆F11+k [[`]] below, and such that
δQ11+jδF11+k= qj += fk +

i−1
X
`=0
i−1
X

2` ∆Q11+j [[`]],

j = 1, 2,(6)`

2 ∆F11+k [[`]],

k = 1, 2, 3, 4.

`=0

From these conditions it follows that U0 must be chosen as {(δQ12 , δQ13 , δF12 ,δF13 , δF14 , δF15 )}. For i = 1, 2, . . . , 32, we attempt to construct Ui based on
Ui−1 using Algorithm 3-2. Because per j there are at most two qj ’s and per k
there are at most two fk ’s that can satisfy the above relations, we have that|Ui | ≤ 26 for each i, 0 ≤ i ≤ 32. On the other hand, for each tuple in Ui there
may in principle be many different compatible sets of bitconditions.
As soon as we encounter an i for which Ui = ∅, we know that the desired
bitconditions do not exist, and that we should try another combination of forward and backward partial differential paths. If, however, we find U32 6= ∅ thenit must be the case that U32 = {(0, 0, 0, 0, 0, 0)}. Furthermore, in that case, every
set of bitconditions that leads to this non-empty U32 gives rise to a full differential path, since equations (6) hold with i = 32. Thus, if U32 6= ∅, there exists atleast one valid path u0 , u1 , . . . , u32 with ui ∈ Ui . For each valid path, the desired
new bitconditions (q15 [i], q14 [i], . . . , q10 [i]) are (a0 , b00 , c000 , d000 , e00 , f 0 ), which canbe found at step 13 of Algorithm 3-2.
3.7

Collision finding0
Collision finding is the process of finding an actual message block pair Sc,j , Sc,jthat satisfies a given δSc,j and a differential path based on a given IHVn+j−1 ,IHV0n+j−1 , cf. step (d) of Algorithm 3-1. The differential paths as originallyconsidered by Wang et al. [33] consisted of only 28 bitconditions. In that case,collision finding can now be done in the equivalent of a mere 224.8 expected MD5compression function calls, for arbitrary IHV [27]. For chosen-prefix collisions,however, the number of bitconditions is substantially larger, thereby complicating collision finding. For instance, in one of our earliest chosen-prefix collision
constructions the differential path has 71 bitconditions on Q20 up to Q63 .

3.7.1 Tunnels
To find collisions for these more difficult differential paths, we make extensive useof so-called tunnels [17]. A tunnel allows one to make small changes in a certain
first round Qt , in specific bits of Qt that are determined by the full differential
path q−3 , q−2 , . . . , q64 under consideration, while causing changes in the second
round only after some step l that depends on the tunnel. However, each tunnel
implies that additional first-round bitconditions have to be taken into accountin the differential path, while leaving freedom of choice for some of the bits in
Qt that may be changed. A tunnel’s strength is the number of independent bits
22

that can be changed in this first round Qt . Thus, a tunnel of strength k allows
us to generate 2k different message blocks that all satisfy the differential path
up to and including step l in the second round.
Table 3-5. Collision finding tunnels for MD5.
Tunnel Change
T1
T2
T3
T4
T5
T6
T7
T8

Extra bitconditions?

AffectedQ4 [b]
m3 ..m5 , m7 , Q21 ..Q64
Q5 [b] = 1, Q6 [b] = 1
Q5 [b]
m4 , m5 , m7 , m8 , Q21 ..Q64
Q6 [b] = 0
Q14 [b] m13 ..m15 , m6 , Q3 , m2 ..m5 , Q21 ..Q64 Q15 [b] = Q16 [b], Q3 [b] free†Q9 [b]
m8 ..m10 , m12 , Q22 ..Q64
Q10 [b] = 1, Q11 [b] = 1
Q10 [b]m9 , m10 , m12 , m13 , Q22 ..Q64
Q11 [b] = 0
Q8 [b]
m7 ..m9 , Q12 , m12 ..m15 , Q23 ..Q64 Q10 [b] = 1, RR(Q12 , 22)[b] free‡Q4 [b]
m3 , m4 , m7 , Q24 ..Q64
Q5 [b] = 0, Q6 [b] = 1
Q9 [b]
m8 , m9 , m12 , Q25 ..Q64
Q10 [b] = 0, Q11 [b] = 1

The extra bitconditions refer only to Qt [b] and not to Q0t [b], so e.g. Q6 [b] = 0 is met
by both q6 [b] = ‘0’ and q6 [b] = ‘+’.
†Bitcondition q3 [b] = ‘.’ and no other indirect bitconditions may involve Q3 [b]. Set
Q3 [b] = Q14 [b] to avoid carries in Q3 .
‡Bitcondition q12 [b − 22 mod 32] = ‘.’ and no other indirect bitconditions may involve
Q12 [b − 22 mod 32]. Set Q12 [b − 22 mod 32] = Q8 [b] to avoid carries in Q12 .

?

The tunnels used in our collision finding algorithm are shown in Table 3-5.
For example, the first tunnel (T1 ) allows changes in bits of Q4 , in such a waythat if Q4 [b] is changed for some bit position b with 0 ≤ b < 32, this causes
extra bitconditions Q5 [b] = 1 and Q6 [b] = 1, which have to be incorporated
in the differential path. Furthermore, because tunnel T1 affects after the firstround only Q21 through Q64 we have that l = 20, and T1 can be used to change
message blocks m3 , m4 , m5 , and m7 . To determine the strength of a tunnel one
first needs to incorporate the tunnel’s extra bitconditions in the full differential
path, and then count the remaining amount of freedom in the first round Qt
that is changed by the tunnel. Given its dependence on the differential path, atunnel’s strength can thus not be tabulated.
The most effective tunnel is T8 . As indicated in the table, it affects after the
first round only Q25 , . . . , Q64 . Over these rounds, Wang’s original differential
paths have 20 bitconditions whereas the chosen-prefix collision differential paths
that we manage to construct have approximately 27 bitconditions. It follows
that, given enough tunnel strength, especially for T7 and T8 , collision finding
can be done efficiently.

23

3.7.2

Algorithm

Algorithm 3-3 Collision finding algorithm.
Given a full differential path q−3 , . . . , q64 consisting of only direct and backward bitconditions and the set T1 , . . . , T8 of tunnels from Table 3-5, perform the following steps:
1. Determine for all tunnels for which bits b the extra bitconditions as shown in
Table 3-5 can be met. For each possible case, apply compatible bitconditions toenforce the extra bitconditions and change the bitconditions qt [b] of the changed
or affected Qt [b] in the first round from ‘.’ to ‘0’.
2. Perform the steps below until a collision block has been found.
3. Select Q1 , Q2 , Q13 , . . . , Q16 such that q1 , q2 , q13 , . . . , q16 hold.
4. Compute m1 , Q17 .
5. If q17 holds and the rotation for t = 16 is successful, then proceed.
6. Store the set Z of all pairs (Q1 , Q2 ) meeting q1 , q2 that do not change m1 andbits of Q2 involved in q3 .
7. For all Q3 , . . . , Q7 meeting q3 , . . . , q7 do:
8.
Compute m6 , Q18 .
9.
If q18 holds and the rotation for t = 17 is successful, then proceed.
10.
For all Q8 , . . . , Q12 meeting q8 , . . . , q12 do:
11.
Compute m11 , Q19 .
12.
If q19 holds and the rotation for t = 18 is successful, then proceed.
13.
For all (Q1 , Q2 ) in Z do:
14.
Compute m0 , Q20 .
15.
If q20 holds and the rotation for t = 19 is successful, then proceed.
16.
For all values of the bits of tunnels T1 , T2 , T3 do:
17.
Set the bits to those values and compute m5 , Q21 .
18.
If q21 holds and the rotation for t = 20 is successful, then proceed.
19.
For all values of the bits of tunnels T4 , T5 do:
20.
Set the bits to those values and compute m10 , Q22 .
21.
If q22 holds and the rotation for t = 21 is successful, then proceed.
22.
For all values of the bits of tunnel T6 do:
23.
Set the bits to those values and compute m15 , Q23 .
24.
If q23 holds and the rotation for t = 22 is successful, then proceed.
25.
For all values of the bits of tunnel T7 do:
26.
Set the bits to those values and compute m4 , Q24 .
27.
If q24 holds and the rotation for t = 23 is successful, then proceed.
28.
For all values of the bits of tunnel T8 do:
29.
Set the bits to those values and compute m9 , Q25 .
30.
If q25 holds and the rotation for t = 24 is successful, then proceed.
31.
Compute m0 , . . . , m15 , Q26 , . . . , Q64 and Q01 , . . . , Q064 .
dt = Q0t − Qt agrees with qt for t = 61, 62, 63, 64, return M, M 0 .
32.
If δQ
Computation of mi and Qi is performed at t = i and t = i − 1, respectively.
We assume that the rotations in the first round have probability very close to 1 to becorrect, and therefore do not verify them. This is further explained in Section 3.7.3.

24

In our construction we performed the collision finding using Algorithm 3-3.
The conditions on the differential path imposed by Algorithm 3-3 can easily be
met because, as mentioned in Section 3.5.1, forward and backward bitconditionsin the differential path are interchangeable. Steps 10 through 15 of Algorithm 3-3
are its most computationally intensive part, in particular for the toughest differential paths in a chosen-prefix collision, so they should be optimized. Greatertunnel strength significantly reduces the time spent there, because after step 15
all tunnels are used.
In practice, in step c.4 of Algorithm 3-1 (cf. Section 3.6) we keep only thosefull differential paths for which tunnels T1 , T2 , T4 and T5 satisfy a certain lower
bound on their strength. Furthermore, of the full differential paths kept, we selectthose with the best properties such as high tunnel strength and a low numberof bitconditions on Q18 , . . . , Q63 .
3.7.3 Rotation bitconditions
As mentioned below Algorithm 3-3, it is assumed there that all rotations in thefirst round will be correct with probability very close to 1. In Algorithm 3-3,
Q1 , . . . , Q16 are chosen in a non-sequential order and also changed at various
steps in the algorithm. Ensuring correct rotations in the first round would be
cumbersome and it would hardly avoid wasting time in a state where one ormore rotations in the first round would fail due to the various tunnels. However,as shown in [26], if we use additional bitconditions qt [i] we can (almost) ensure
correct rotations in the first round, thereby (almost) eliminating both the effort
to verify rotations and the wasted computing time. This is explained below.
We use the notation introduced in Section 3.6.4. Given δTt and δRt it iseasy to determine which partition (α, β) satisfies RL((α, β), RCt ) = δRt . The
probability that this correct rotation holds is not necessarily p(α,β) because it
may be assumed that bitconditions qt and qt+1 hold and these directly affect
Rt = Qt+1 − Qt and thus Tt = RR(Rt , RCt ). Hence, using bitconditions qt and
qt+1 we can try and increase the probability of a correct rotation in step t to(almost) 1 in the following way.
The other three partitions (of the four listed in Section 3.6.4) correspond to
the incorrect rotations. Those partitions are of the form(α̂, β̂) = (α − λ0 232−RCt , β + λ0 232−RCt + λRCt 232 ),λ0 , λRCt ∈ {−1, 0, +1}

dt of the form
where either λ0 6= 0 or λRCt 6= 0. They result in incorrect δR
dt = RL((α̂, β̂), RCt ) = δRt + λ0 20 + λRC 2RCt .
δRtThey are caused by a carry when adding δTt to Tt that does or does not propagate: from bit position 32 − RCt − 1 to 32 − RCt for λ0 6= 0 and from bit
position 31 to 32 for λRCt 6= 0. Since we chose the partition (α, β) with highest
probability, this usually means that we have to prevent instead of ensure those
propagations in order to decrease the probability that λ0 6= 0 or λRCt 6= 0.
To almost guarantee proper rotations in each step of Algorithm 3-3, additional bitconditions can be determined by hand, as shown in [26]. It was seen that25

adding bitconditions on Qt , Qt+1 around bit positions 31 − RCt + i and lower
helps preventing λi 6= 0. This can be automated using a limited brute-force
search, separately handling the cases λ0 6= 0 and λRCt 6= 0.
Let i ∈ {0, RCt }. Given bitconditions qt , qt+1 , we estimate P r[λi 6= 0|qt , qt+1 ]bt , Qb t+1 satisfying qt , qt+1 , e.g. of size 211 , and deby sampling a small set of Q
dt − δRt )[[i]] 6= 0 using
termining the fraction where λi = NAF(δR
dt = RL(RR(Qb t+1 − Q
b t , RCt ) + δTt , RCt ).
δR
Using this approach, we estimate the probability that λi = 0 by selecting asmall search bound B and exhaustively trying all combinations of additional
bitconditions on Qt [b], Qt+1 [b] for b = 31−RCt +i−B, . . . , 31−RCt +i. Finally, if
there are any bitconditions (q0t , q0t+1 ) for which P r[λi 6= 0|q0t , q0t+1 ] is negligible,
we select the pair (q0t , q0t+1 ) that leads to the smallest number of additional
bitconditions and for which P r[λ0 = λRCt = 0|qt−1 , q0t ] and P r[λ0 = λRCt =0|q0t+1 , qt+2 ] do not decrease significantly for step t − 1 and t + 1, respectively.
3.8

Implementation remarks

Our software to construct chosen-prefix collisions consists of five main components that perform the following tasks:
1. the birthday search (with a special implementation for Sony’s PlayStation 3);
2. forward extension of a given set of partial lower differential paths by a given
step t, saving only the paths with the fewest bitconditions;
3. backward extension of a given set of partial upper differential paths by agiven step t, saving only the paths with the fewest bitconditions;
4. attempt to connect all combinations of given lower and upper differential
paths;
5. coordinate the four earlier tasks by preparing the required inputfiles, collectthe outputs, and search for near-collision blocks.
These tasks are carried out as described in the earlier sections. A few remarks are
in order. The first task is the most computationally expensive one and consists
mostly of simple applications of the MD5 compression function. It turns out that
the Cell processor, contained in the PlayStation 3 game console, can be madeto perform this task about 30 times faster than a regular 32-bit PC core. Moredetails on the peculiarities of the PlayStation 3 implementation are described in
Section 4.2.2.
For the second and third task we exhaustively try all limited weight BSDRs
of δQt , all possible δFt ’s, and we use the highest-probability rotation. We keep
at most a preset number of paths with the lowest number of bitconditions thathave a preset minimum total strength over tunnels T1 , T2 , T4 , and T5 . Each of
the programs is designed to execute several separate but parallel threads.
26

3.9

Complexity analysis

The overall complexity of the chosen-prefix collision attack depends on the parameters used for the birthday search and the construction of pairs of nearcollision blocks. This involves various trade-offs and is described in this section.
The birthday search complexity depends on the parameter w (defining thefamily of differential paths), the upper bound on the number r of pairs of nearcollision blocks, the size 264+k of the search space, and the amount of available
memory M . For various parameter choices of r, k and w we have tabulated
the heuristically determined expected birthday search complexities and memory
requirements in Appendix C (in practice it is advisable to use a small factor
more memory than required to achieve Ccoll  Ctr ). Given r, w and M , theoptimal value for k and the resulting birthday complexity can thus easily belooked up. When r is left free, one can balance the birthday complexity and thecomplexity of constructing r pairs of near-collision blocks.
Each pair of near-collision blocks requires construction of a set of full differential paths followed by the actual construction of the pair of near-collision
blocks. The complexity of the former construction depends on several parameterchoices, such as the size of the sets of lower and upper differential paths, andthe restraints used when selecting BSDRs for a δQt . Naturally, a higher overall
quality of the resulting complete differential paths, i.e., a low number of overall bitconditions and a high total tunnel strength, generally results when more
effort is put into the construction. For practical purposes we have found parameters sufficient for almost all cases (as applicable to the chosen-prefix collisionattack) that have an average total complexity equivalent to roughly 235 MD5compressions.
The complexity of the collision finding, i.e., the construction of a pair of nearcollision blocks, depends on the parameter w, the total tunnel strength and thenumber of bitconditions in the last 2.5 rounds. For small w = 0, 1, 2 and paths
based on Table 3-1, the construction requires on average roughly the equivalentof 234 MD5 compressions. Combined with the construction of the differential
paths, this leads to the rough overall estimate of about 235.6 MD5 compressions
to find a single pair of near-collision blocks for a chosen-prefix collision attack.
With w = 2 and optimizing for overall complexity this leads to the optimal
parameter choices r = 9 and k = 0. For these choices, the birthday searchcost is about 237 MD5 compressions and constructing the r = 9 pairs of nearcollision blocks costs about 238.8 MD5 compressions. The overall complexity isthus estimated at roughly 239.1 MD5 compressions, which takes about 35 hours
on a single PC-core. For this parameter choice the memory requirements for thebirthday search are very low, even negligible compared to the several hundredsof MBs required for the construction of the differential paths.
With more specific demands, such as a small number r of near-collision blocks
possibly in combination with a relatively low M , the overall complexity will
increase. As an example, our rogue CA construction required at most r = 3
near-collision blocks, and using M = 5TB this results in an overall complexityof about 249 MD5 compressions.
27

In Table 3-6 we present a historical overview of the decline in complexityof MD5 and SHA-1 collision finding. It clearly illustrates that attacks only getbetter, not worse. Not reflected in the table is the fact that already in 1993 it
was known that there was serious trouble with MD5, based on collisions in its
compression function (cf. [2], [8]). We leave any speculation about the future of
SHA-1 cryptanalysis to the knowledgeable reader.
Table 3-6. Collision complexities – Historical overview.
MD5
SHA-1
year identical-prefix chosen-prefix identical-prefix chosen-prefix
pre-2004 264 (trivial)
264 (trivial) 280 (trivial)
280 (trivial)
2004 240 [30], [33]2005 237 [16]269 [32]
263 [31]
32
49
2006 2 [17], [26]
2 [28]
280− [24]2007 225 [27]242 [27]261 [20]
2008 221 [34]2009 216 [29]239 [29]
252 [19]
Complexity is given as the number of calls to the relevant compression function. The
figures are optimized for speed, i.e., for collisions using any number of near-collision
blocks. For other collision lengths the complexities may differ.

3.10

Single-block chosen-prefix collision

Using a different approach it is even possible to construct a chosen-prefix collisionusing only a single pair of near-collision blocks. Together with 84 birthday bits,
the chosen-prefix collision-causing appendages are only 84 + 512 = 596 bits long.
This approach is based on an even richer family of differential paths that allows
elimination using a single pair of near-collision blocks of a set of δIHVs thatis bounded enough so that finding the near-collision blocks is still feasible, butlarge enough that such a δIHV can be found efficiently by a birthday search.
Instead of using the family of differential paths based on δm11 = ±2i , we use
the fastest known collision attack for MD5 and vary the last few steps to find alarge family of differential paths.
We first present a new collision attack for MD5 with complexity of approximately 216 MD5 compressions improving upon the 220.96 MD5 compressions
required in [34]. Our starting point is the partial differential path for MD5 given
in Table 3-7. It is based on message differences δm2 = 28 , δm4 = δm14 = 231
and δm11 = 215 which is very similar to those used by Wang et al. in [33] for the
first collision attack against MD5. This partial differential path can be used for anear-collision attack with complexity of approximately 214.8 MD5 compressions.
This leads in the usual fashion to an identical-prefix collision attack for MD5
that requires approximately 216 MD5 compressions, since one has to do it twice:28

first to add differences to δIHV and then to eliminate them again. It should be
noted that usually bitconditions are required on the IHV and IHV0 between thetwo collision blocks which imply an extra factor in complexity. In the present
case, however, we can construct a large set of differential paths for the second
near-collision block that will cover all bitconditions that are likely to occur,
thereby avoiding the extra complexity.
Table 3-7. Partial differential path for fast near-collision attack.
t

δQt

δFt

δWt

δTt

δRt

RCt

26
27
28
29

−28
0
0
0

0

28

0

0

9

30 − 33

0

0

0

0

0

·

15

15

31

16
23
4
11

34
35
36
37

0
231
231
231

0
231
0
231

38 − 46

231

231

0

0

0

·

47
48
49
50

31

2
0
0
0

231
0
0
0

28
0
0
231

28
0
0
0

231
0
0
0

23
6
10
15

51 − 59

0

0

0

0

0

·

31

31

60
61
62
63
64

2
231
0
231

2
0
0
0

2
0
0
0

5

0
0
2
2
−2
6
−25
0
215
215
225
10
−25 + 225
0
28
28
223
15
5
25
23
5
23
5
23 26
−2 + 2 + 2
2 −2
0 2 − 2 2 − 214 21−25 + 225 + 223 + 226 − 214

Partial differential path for t = 29, . . . , 63 using message differences δm2 = 28 , δm4 =δm14 = 231 , δm11 = 215 . The probability that it is satisfied is approximately 2−14.5 .

By properly tuning the birthday search, the same partial differential pathleads to the construction of a single near-collision block chosen-prefix collision
for MD5. By varying the last steps of the differential path and by allowing thecollision finding complexity to grow by a factor of about 226 , we have founda set S of about 223.3 different δIHV = (δa, δb, δc, δd) of the form δa = −25 ,δd = −25 + 225 , δc = −25 mod 220 that can be eliminated. Such δIHVs can befound using an 84-bit birthday search with step function f : {0, 1}84 → {0, 1}84of the form(dφ(MD5compress(IHV, Bkx) + δ IHV)
for σ(x) = 0
f (x) =0
0
φ(MD5compress(IHV , B kx))for σ(x) = 1,29

d is of the required form, σ : x 7→ {0, 1} is a balanced selector function
where δ IHV
and φ(a, b, c, d) 7→ akdk(c mod 220 ). There are 2128−84 = 244 possible δIHVs ofthis form, of which only about 223.3 are in the allowed set S. It follows that abirthday collision has probability p = 223.3 /(244 · 2) = 2−21.7 to be useful, where
the additional factor 2 stems from the fact that different
p prefixes are required.
A useful birthday collision can be expected after π284 /(2p) ≈ 253.2 MD5compressions, requires 400MB of storage and takes about 3 days on 215 PS3s.
The expected complexity of finding the actual near-collision blocks is boundedby about 214.8+26 = 240.8 MD5 compressions.
In Table 3-8 two 128-byte messages are given both consisting of a 52-byte
chosen prefix and a 76-byte single-block chosen-prefix collision suffix and withcolliding MD5 hash value D320B6433D8EBC1AC65711705721C2E1.
Table 3-8. Example single-block chosen-prefix collision.
Message 1
4F 64 65 64 20 47 6F 6C 64 72 65 69 63 68 0A 4F
64 65 64 20 47 6F 6C 64 72 65 69 63 68 0A 4F 64
65 64 20 47 6F 6C 64 72 65 69 63 68 0A 4F 64 65
64 20 47 6F D8 05 0D 00 19 BB 93 18 92 4C AA 96
DC E3 5C B8 35 B3 49 E1 44 E9 8C 50 C2 2C F4 61
24 4A 40 64 BF 1A FA EC C5 82 0D 42 8A D3 8D 6B
EC 89 A5 AD 51 E2 90 63 DD 79 B1 6C F6 7C 12 97
86 47 F5 AF 12 3D E3 AC F8 44 08 5C D0 25 B9 56
Message 2
4E 65 61 6C 20 4B 6F 62 6C 69 74 7A 0A 4E 65 61
6C 20 4B 6F 62 6C 69 74 7A 0A 4E 65 61 6C 20 4B
6F 62 6C 69 74 7A 0A 4E 65 61 6C 20 4B 6F 62 6C
69 74 7A 0A 75 B8 0E 00 35 F3 D2 C9 09 AF 1B AD
DC E3 5C B8 35 B3 49 E1 44 E8 8C 50 C2 2C F4 61
24 4A 40 E4 BF 1A FA EC C5 82 0D 42 8A D3 8D 6B
EC 89 A5 AD 51 E2 90 63 DD 79 B1 6C F6 FC 11 97
86 47 F5 AF 12 3D E3 AC F8 44 08 DC D0 25 B9 56

4Applications of chosen-prefix collisions

When exploiting collisions in real world applications two major obstacles must
be overcome.
– The problem of meaningful collisions. Given current methods, collisions require appendages consisting of unpredictable and mostly uncontrollable bitstrings. These must be hidden in the usually heavily formatted application
data structure without raising suspicion.
30

– The problem of realistic attack scenarios. As we do not have effective attacks against MD5’s (second) preimage resistance but only collision attacks,
we cannot target existing MD5-values. In particular, the colliding data structures must be generated simultaneously, along with their shared hash, by theadversary.
In Section 4.1 several chosen-prefix collision applications are surveyed wherethese problems are addressed with varying degrees of success. Sections 4.2, 4.3,
and 4.4 describe the three most prominent applications in more detail.
4.1

A survey of potential applications

We mention some potential applications of chosen-prefix collisions.
Digital certificates. Given how heavily they rely on cryptographic hash functions, digital certificates are the first place to look for applications of chosenprefix collisions. Two X.509 certificates are said to collide if their to-be-signed
parts have the same hash and consequently their digital signatures, as provided by the CA, are identical. In earlier work (cf. [18]) we have shown how
identical-prefix collisions can be used to construct colliding X.509 certificateswith different RSA moduli but identical Distinguished Names. Here the RSA
moduli absorbed the random-looking near-collision blocks, thus inconspicuously and elegantly solving the meaningfulness problem. Allowing different
Distinguished Names required chosen-prefix collisions, as shown in [28]. The
certificates resulting from both constructions do not contain spurious bits,
so superficial inspection at bit level of either of the certificates will not reveal
the existence of a sibling certificate that collides with it signature-wise. Nevertheless, for these constructions to work the entire to-be-signed parts, andthus the signing CA, must be fully under our own control, thereby limiting
the practical attack potential.
A related but in detail rather different construction was carried out incollaboration with Alexander Sotirov, Jacob Appelbaum, David Molnar,and Dag Arne Osvik, as reported on http://www.win.tue.nl/hashclash/rogue-ca/ and in [29]. Although in practice a certificate’s to-be-signed partcannot be for 100% under control of the party that submits the certification request, for some commercial CAs (that still used MD5 for their digital
signature generation) the entire to-be-signed part could be predicted reliably enough to make the following guess-and-check approach practicallyfeasible: prepare the prefix of the to-be-signed part of a legitimate certification request including a guess for the part that will be included by the CA
upon certification, prepare a rogue to-be-signed prefix, determine different
collision-causing and identical collision-maintaining appendages to complete
two colliding to-be-signed parts, and submit the legitimate one for certification. If upon receipt of the legitimate certificate the guess turns out to havebeen correct, then the rogue certificate can be completed by pasting the
CA’s signature of the legitimate data onto the rogue data: because the data31

collide, the signature will be equally valid for both. Otherwise, if the guess isincorrect, another attempt is made. Using this approach we managed (uponthe 4th attempt) to trick a commercial CA into providing a signature valid
for a rogue CA certificate. For the intricate details of the construction werefer to Section 4.2.
A few additional remarks about this construction are in order here. We
created not just a rogue certificate, but a rogue CA certificate, containing
identifying information and public key material for a rogue CA. The private
key of this rogue CA is under our control. Because the commercial CA’s signature is valid for the rogue CA certificate, all certificates issued by the rogue
CA are trusted by anybody trusting the commercial CA. As the commercial
CA’s root certificate is present in all major browsers, this gives us in principle the possibility to impersonate any certificate owner. This is certainly
a realistic attack scenario. The price that we have to pay is that the meaningfulness problem is only adequately – and most certainly not elegantly –solved: as further explained in the next paragraph, one of the certificatescontains a considerable number of suspicious-looking bits.
To indicate that a certificate is a CA certificate, a certain bit has to be set
in the certificate’s to-be-signed-part. According to the X.509v3 standard [6],this bit comes after the public key field. Because it is unlikely that a commercial CA will accept a certification request where the CA bit is set, thebit must not be set in the legitimate request. For our rogue CA certificate
construction, the fact that the two to-be-signed parts must contain a different bit after the public key field causes an incompatibility with our ‘usual’colliding certificate construction as in [18] and [28]. In that construction thecollision-causing appendages correspond to the high order bits of RSA moduli, and they are followed by identical collision-maintaining appendages thattransform the two appendages into valid RSA moduli. Anything following
after the moduli must remain identical lest the collision property goes lost.
As a consequence, the appendages on the rogue side can no longer be hidden in the public key field and some other field must be found for them.
Such a field may be specially defined for this purpose, or an existing (proprietary) extension may be used. The Netscape Comment extension is a good
example of the latter, as we found that it is ignored by the major certificate processing software. The upshot is, however, that as the appendages
have non-negligible length, it will be hard to define a field that will not looksuspicious to someone who looks at the rogue certificate at bit level.
Colliding documents. In [7] (see also [10]) it was shown how to construct apair of PostScript files that collide under MD5, but that display different
messages when viewed or printed. Because these constructions use identicalprefix collisions, they have to rely on the presence of both messages in each of
the colliding files and on macro-functionalities of the document format used.
Obviously, this raises suspicion upon inspection at bit level. With chosenprefix collisions, one message per colliding document suffices and macrofunctionalities are no longer required. For example, using a document format
that allows insertion of color images (such as Microsoft Word or Adobe32PDF), inserting one message per document, two documents can be madeto collide by appending carefully crafted color images after the messages. A
short one pixel wide line will do – for instance hidden inside a layout element,
a company logo, or a nicely colored barcode – and preferably scaled down
to hardly visible size (or completely hidden from view, as possible in PDF).
An extension of this construction is presented in the paragraphs below andset forth in detail in Section 4.3.
Hash based commitments. Kelsey and Kohno [15] presented a method tofirst commit to a hash value, and next to construct faster than by a trivial pre-image attack a document with the committed hash value, and withany message of one’s choice as a prefix. The method applies to any MerkleDamgård hash function, such as MD5, that given an IHV and a suffix produces some IHV. Omitting details involving message lengths and MerkleDamgård strengthening, the idea is to commit to a hash value based on an
IHV at the root of a tree, either that IHV itself or calculated as the hash ofthat IHV and some suffix at the root. The tree is a complete binary tree andis calculated from its leaves up to the root, so the IHV at the root will be oneof the last values calculated. This is done in such a way that each node of thetree is associated with an IHV along with a suffix that together hash to the
IHV associated with the node’s parent. Thus, two siblings have IHVs andsuffixes that collide under the hash function. The IHVs at the leaves may bearbitrarily chosen but are, preferably, all different. Given a prefix of one’s
choice one performs a brute-force search for a suffix that, when appended tothe prefix and along with the standard IHV, results in the IHV at one of theleaves (or nodes) of the tree. Appending the suffixes one encounters on one’s
way from that leave or node to the root, results in a final message with thedesired prefix and committed hash value.
Originally based on a birthday search, the construction of the tree can bedone more efficiently by using chosen-prefix collisions to construct siblingnode suffixes based on their IHVs. For MD5, however, it remains far fromfeasible to carry out the entire construction in practice. In a variant that is
feasible, one commits to a prediction by publishing its hash value. In due time
one reveals the correct prediction, chosen from among a large enough preconstructed collection of documents that, due to tree-structured chosen-prefix
collision appendages, all share the same published hash value. In section 4.3
we present an example involving 12 documents.
Software integrity checking. In [14] and [21] it was shown how any existingMD5 collision, such as the ones originally presented by Xiaoyun Wang at the
Crypto 2004 rump session, can be abused to mislead integrity checking software that uses MD5. A similar application, using freshly made collisions,
was given on http://www.mathstat.dal.ca/~selinger/md5collision/.
As shown on http://blog.didierstevens.com/2009/01/17/ this can evenbe done within the framework of Microsoft’s Authenticode code signing program. All these results use identical-prefix collisions and, similar to the colliding PostScript application mentioned earlier, differences in the colliding
inputs are used to construct deviating execution flows.
33

Chosen-prefix collisions allow a more elegant approach, since common operating systems ignore bitstrings that are appended to executables: the programs will run unaltered. Thus, using tree-structured chosen-prefix collisionappendages as above, any number of executables can be made to have thesame MD5 hash value or MD5-based digital signature. See Section 4.4 foran example.
One can imagine two executables: a ‘good’ one (say Word.exe) and a badone (the attacker’s Worse.exe). A chosen-prefix collision for those executables is computed, and the collision-causing bitstrings are appended to both
executables. The resulting altered file Word.exe, functionally equivalent to
the original Word.exe, can be offered to a code signing program such as Microsoft’s Authenticode and receive an ‘official’ MD5-based digital signature.
This signature will then be equally valid for the attacker’s Worse.exe, andthe attacker might be able to replace Word.exe by his Worse.exe (renamed
to Word.exe) on the appropriate download site. This construction affects acommon functionality of MD5 hashing and may pose a practical threat. It
also allows people to get many executables signed at once and for free by
getting a single executable signed, bypassing verification of any kind (e.g. authenticity, quality, compatibility, non-spyware, non-malware) by the signing
party.
Computer forensics. In computer forensics so-called hash sets are used toquickly identify known files. For example, when a hard disk is seized by law
enforcement officers, they may compute the hashes of all files on the disk, andcompare those hashes to hashes in existing hash sets: a whitelist (for known
harmless files such as operating system and other common software files) anda blacklist (for previously identified harmful files). Only files whose hashes
do not occur in either hash set have to be inspected further. A useful featureof this method of recognizing files is that the file name itself is irrelevant,since only the content of the file is hashed.
MD5 is a popular hash function for this application. Examples are NIST’s
National Software Reference Library Reference Data Set (http://www.nsrl.
nist.gov/) and the US Department of Justice’s Hashkeeper application(http://www.usdoj.gov/ndic/domex/hashkeeper.htm).
A conceivable, and rather obvious, attack on this application of hashes is to
produce a harmless file (e.g. an innocent picture) and a harmful one (e.g.
an illegal picture), and insert collision blocks that will not be noticed bycommon application software or human viewers. In a learning phase theharmless file might be submitted to the hash set and thus the common hash
may end up on the whitelist. The harmful file will be overlooked from thenon.
Peer to peer software. Hash sets are also used in peer to peer software. A
site offering content may maintain a list of pairs (file name, hash). The filename is local only, and the peer to peer software uniquely identifies thefile’s content by means of its hash. Depending on how the hash is computed
such systems may be vulnerable to a chosen-prefix attack. Software such as
eDonkey and eMule use MD4 to hash the content in a two stage manner:
34

the identifier of the content c1 kc2 k . . . kcn is MD4(MD4(c1 )k . . . kMD4(cn )),where the chunks ci are about 9 MB each. One-chunk files, i.e., files notlarger than 9 MB, are most likely vulnerable; whether multi-chunk files arevulnerable is open for research. We have not worked out the details of achosen-prefix collision attack against MD4, but this seems very well doableby adapting our methods and should result in an attack that is considerably
faster than our present one against MD5.
Content addressed storage. In recent years content addressed storage is gaining popularity as a means of storing fixed content at a physical location ofwhich the address is directly derived from the content itself. For example, ahash of the content may be used as the file name. See [23] for an example.
Clearly, chosen-prefix collisions can be used by an attacker to fool such storage systems, e.g. by first preparing colliding pairs of files, by then storing theharmless-looking first one, and later overwriting it with the harmful second
one.
Further investigations are required to assess the impact of chosen-prefix collisions. We leave it to others to study to what extent commonly used protocols
and message formats such as TLS, S/MIME (CMS), IPSec and XML Signatures(see [1] and [13]) allow insertion of random looking data that may be overlookedby some or all implementations. The threat posed by identical-prefix collisions is
not well understood either: their application may be more limited, but for MD5
they can be generated almost instantaneously and thus allow real-time attacks
on the execution of cryptographic protocols, and, more importantly, for SHA-1
they may soon be feasible.
4.2

Creating a rogue Certification Authority certificate

This section contains an in-depth discussion of the practical dangers posed byrogue Certification Authority certificates, followed by a detailed description of
how we managed to construct such a certificate.
The work reported here was carried out in close collaboration with Alexander Sotirov and Dag Arne Osvik, and was triggered by email exchanges with
Alexander Sotirov, Jacob Appelbaum and David Molnar.
4.2.1 Attack potential of rogue CA certificatesIn the conference version [28, Section 4.1] of this paper we daydreamed:“Ideally, a realistic attack targets the core of PKI: provide a relying party
with trust, beyond reasonable cryptographic doubt, that the person indicated by the Distinguished Name field has exclusive control over theprivate key corresponding to the public key in the certificate. The attack
should also enable the attacker to cover his trails.”
Our dream scenario has been, mostly, realized with the construction of a rogue
CA certificate. With the private key of a CA under our control, and the public
35

key appearing in a certificate with a valid signature of a commercial CA that istrusted by all major browsers, we can create ‘trusted’ certificates at will. Whenscrutinized at bit level, however, our rogue CA certificate may look suspicious
which may, ultimately, expose us. Bit level inspection is not something manyusers will engage in – if they know the difference between https and http tobegin with – and, obviously, the software that is supposed to inspect a certificate’s bits is expertly guided around the suspicious ones. So, it may be argued
that our construction has a non-negligible attack potential. Below we discuss
some possibilities in this direction. Upfront, however, we like to point out that
our rogue CA is nothing more than a proof of concept that is incapable of doing
much harm, because it expired, on purpose, in September of 2004, i.e., morethan 4 years before it was created.
Any website secured using TLS can be impersonated using a rogue certificate
issued by a rogue CA. This is irrespective of which CA issued the website’s true
certificate and of any property of that certificate (such as the hash function it isbased upon – SHA-256 is not any better in this context than MD4). Combinedwith redirection attacks where http requests are redirected to rogue web servers,
this leads to virtually undetectable phishing attacks.
But any application involving a Certification Authority that provides MD5based certificates with sufficiently predictable serial number and validity period
may be vulnerable. In contexts different from TLS this may include signing or
encryption of e-mail or software, non-repudiation services, etc.
As pointed out earlier, bit-level inspection of our rogue CA certificate will
reveal a relatively large number of bits that may look suspicious – and that are
suspicious. This could have been avoided if we had chosen to create a rogue
certificate for a regular website, as opposed to a rogue CA certificate, because inthat case we could have hidden all collision causing bits inside the public keys.
Nevertheless, even if each resulting certificate by itself looks unsuspicious, as soon
as a dispute arises, the rogue certificate’s legitimate sibling can be located withthe help of the CA, and the fraud becomes apparent by putting the certificatesalongside, thus exposing the party responsible for the fraud.
Our attack relies on our ability to predict the content of the certificate fields
inserted by the CA upon certification: if our prediction is correct with nonnegligible probability, a rogue certificate can be generated with the same nonnegligible probability. Irrespective of the weaknesses, known or unknown, of thecryptographic hash function used for digital signature generation, our type ofattack becomes effectively impossible if the CA adds a sufficient amount of fresh
randomness to the certificate fields before the public key fields. Relying parties,
however, cannot verify this randomness. Also, the trustworthiness of certificatesshould not crucially depend on such secondary and circumstantial aspects. We
would be in favor of a more fundamental solution – along with a strong cryptographic hash function – possibly along the lines as proposed in [11]. Generally
speaking, it is advisable not to sign data that is completely determined by someother party. Put differently, a signer should always make a few trivial and unpre36

dictable modifications before digitally signing a document provided by someone
else.
Based on our previous work [28], the issue in the previous paragraph was recognized and the possibility of the attack presented in this paper anticipated in the
catalogue [3] of algorithms suitable for the German Signature Law (‘Signaturgesetz’). This catalogue includes conditions and time frames for cryptographic hashalgorithms to be used in legally binding digital signatures in Germany. One of
the changes introduced in the 2008 version of the catalog is an explicit conditionon the usage of SHA-1: only until 2010, and only for so-called “qualified certificates” that contain at least 20 bits of entropy in their serial numbers. We are
grateful to Prof. Werner Schindler of the BSI for bringing this to our attention
and for confirming that this change was introduced to thwart exactly the typeof rogue certificates that we present here for MD5. Currently the complexity ofidentical-prefix collisions for SHA-1 is rumored to hover around 252 compressionfunction calls. It is unlikely it will again inch up from there, but may instead
tumble down even further: given the flux in SHA-1 cryptanalysis, 20 bits ofadditional entropy may not suffice for much longer to even approach SHA-1’s
intended 80 bits of security.
We stress that our attack on MD5 is not a preimage or second preimage
attack. We cannot create a rogue certificate having a signature in common witha certificate that was not especially crafted using our chosen-prefix collision. In
particular, we cannot target any existing, independently created certificate andforge a rogue certificate that shares its digital signature with the digital signatureof the targeted certificate. However, given any certificate with an MD5-based
digital signature, a relying party cannot easily recognize if it is trustworthy
or, on the contrary, crafted by our method. Therefore we repeat our urgent
recommendation not to use MD5 for new X.509 certificates. How existing MD5
certificates should be handled is a subject of further research. We also urgently
recommend to reconsider usage of MD5 in other applications. Proper alternatives
are available; but compatibility with existing applications is obviously anothermatter. Given potential developments related to SHA-1 (see [4] and http://
www.iaik.tugraz.at/content/research/krypto/sha1/) we feel that usage of
SHA-1 in certificate generation should be reassessed as well.
4.2.2 Certificate construction
Our first colliding X.509 certificate construction was based on an identical-prefix
collision, and resulted in two certificates with different public keys, but identical
Distinguished Name fields [18]. As a first application of chosen-prefix collisions weshowed how the Distinguished Name fields could be chosen differently as well [28].
In this section we describe the details of a colliding certificate construction that
goes one step further by also allowing different “basic constraints” fields. This
allows us to construct one of the certificates as an ordinary website certificate,but the other one as a CA certificate. As already pointed out in Section 4.1, thisadditional difference required a radical departure from our traditional construction method from [18] and [28]. Also, unlike our previous colliding certificate
37

constructions where the CA was under our control, a commercial CA provided
the digital signature for the (legitimate) website certificate. This required us tosufficiently accurately predict its serial number and validity period well before
the certification request was submitted to the signing CA.
We exploited the following weaknesses of the commercial CA that carriedout the legitimate certification request:– Its usage of the cryptographic hash function MD5 to generate digital signatures for new certificates.
– Its fully automated way to process online certification requests that fails torecognize anomalous behavior of requesting parties.
– Its usage of sequential serial numbers and its usage of validity periods thatare determined entirely by the date and time in seconds at which the certification request is processed.
– Its failure to enforce, by means of the “basic constraints” field in its own
certificate, a limit on the length of the chain of certificates that it can sign.
The first three points are further discussed below. The last point, if properly
handled, could have crippled our rogue CA certificate but does not affect its
construction. A certificate contains a “basic constraints” field where a bit is
set to indicate if the certificate is a CA certificate. With the bit set, a “pathlength constraint” subfield may be present, specifying an integer that indicates
how many CAs may occur in the chain between the CA certificate in questionand end-user certificates. The commercial CA that we interacted with failed touse this option in its own certificate, implying that any number of intermediate
CAs is permitted. If the “path length constraint” would have been present andset at 0 (zero), then our rogue CA certificate could still have been constructed.
But whether or not the rogue CA certificate or certificates signed by it canthen also be used depends on (browser-)software actually checking the “pathlength constraint” subfields in chains of certificates. Thus a secondary “defense
in depth” mechanism was present that could have foiled our attack, but failed
to do so simply because it was not used.
Before describing the construction of the colliding certificates, we briefly
discuss the parameter choices used for the chosen-prefix collision search. The
2048-bit upper bound on the length of RSA moduli, as enforced by some CAs,
combined with other limitations of our certificate construction, implied we could
allow for at most 3 near-collision blocks. Opting for the least difficult possibility (namely, 3 near-collision blocks), we had to decide on values for k and theaimed for value for w, determining the costs of the birthday search and the nearcollision block constructions (cf. Sections 3.4 and 3.3), respectively. Obviously,
our choices were influenced by our computational resources, namely a cluster of
215 PlayStation 3 (PS3) game consoles. When running Linux on a PS3, applications have access to 6 Synergistic Processing Units (SPUs), a general purpose
CPU, and about 150MB of RAM per PS3. For the birthday search, the 6 × 215
SPUs are computationally equivalent to approximately 8600 regular 32-bit cores,
due to each SPU’s 4 × 32-bit wide SIMD architecture. The other parts of thechosen-prefix collision construction are not suitable for the SPUs, but we were38

able to use the 215 PS3 CPUs for the construction of the actual near-collision
blocks. With these resources, the choice w = 5 still turned out to be acceptable despite the 1000-fold increase in the cost of the actual near-collision block
construction. This is the case even for the hard cases with many differences
between IHV and IHV0 : as a consequence the differential paths contain many
bitconditions, which leaves little space for the tunnels, thereby complicating thenear-collision block construction.
For the targeted 3 near-collision blocks, the entries for w = 5 in the first tablein Appendix C show the time-memory tradeoff when the birthday search space
is varied with k. With 150MB at our disposal per PS3, for a total of about 30GB,
we decided to use k = 8 as this optimizes the overall
birthday complexity for√the plausible case that the birthday search takes 2 times longer than expected.
The resulting overall chosen-prefix collision construction takes on average lessthan a day on the PS3-cluster. In theory we could have used 1TB (or more) ofhard drive space, in which case it would have been optimal to use k = 0 for abirthday search of about 20 PS3 days.
We summarize the construction of the colliding certificates in the sequenceof steps below, and then describe each step in more detail.
1. Construction of templates for the two to-be-signed parts, as outlined in Figure 2. Note that we distinguish between a ‘legitimate’ to-be-signed part on
the left hand side, and a ‘rogue’ to-be-signed part on other side.
2. Prediction of serial number and validity period for the legitimate part,
thereby completing the chosen prefixes of both to-be-signed parts.
3. Computation of the two different collision-causing appendages.
4. Computation of a single collision-maintaining appendage that will be appended to both sides, thereby completing both to-be-signed parts.
5. Preparation of the certification request for the legitimate to-be-signed part.
6. Submission of the certification request and receipt of the new certificate.
7. If serial number and validity period of the newly received certificate are aspredicted, then the rogue certificate can be completed. Otherwise return toStep 2.
Step 1. Templates for the to-be-signed parts. In this step all bits are set
in the two to-be-signed parts, except for bits that will be determined in later
steps. For the latter bits space will be reserved here. On the legitimate side theparts to be filled in later are the predictions for the serial number and validity
period, and most bits of the public key. On the rogue side the largest part of thecontent of an extension field of the type “Netscape Comment” is for the moment
left undetermined. The following roughly describes the sequence of steps.
– On the legitimate side, the chosen prefix contains space for serial number andvalidity period, along with the exact Distinguished Name of the commercial
CA where the certification request will be submitted. This is followed bya subject Distinguished Name that contains a legitimate website domainname (owned by one of us) consisting of as many characters as allowed by
the commercial CA (in our case 64), and concluded by the first 208 bits of an39

legitimate website
certificate

rogue CA certificate

serial number

serial number

commercial CA namecommercial CA namevalidity period

validity period
chosen prefixes

rogue CA name1024 bit RSA public key

domain namev3 extensions“CA = TRUE”

2048 bit RSA public key

collision bits

v3 extensions

identical suffixes

tumor“CA = FALSE”

Fig. 2. The to-be-signed parts of the colliding certificates.

RSA modulus, the latter all chosen at random after the leading ‘1’-bit. These
sizes were chosen in order to have as many corresponding bits as possible on
the rogue side, while fixing as few bits as possible of the RSA modulus on
the legitimate side (see Step 4 for the reason why).
– The corresponding bits on the rogue side contain an arbitrarily chosen serial
number, the same commercial CA’s Distinguished Name, an arbitrarily chosen validity period (actually chosen as indicating “August 2004”, to avoid
abuse of the rogue certificate), a short rogue CA name, a 1024-bit RSA public key generated using standard software, and the beginning of the X.509v3
extension fields. One of these fields is the “basic constraints” field, a bitthat we set to indicate that the rogue certificate will be a CA certificate (inFigure 2 this bit is denoted by “CA=TRUE”).
– At this point the entire chosen prefix is known on the rogue side, but on
the legitimate side predictions for the serial number and validity period stillneed to be inserted. That will be done in Step 2.
– The various field sizes were selected so that on both sides the chosen prefixes
are now 96 bits short of the same MD5 block boundary. On both sides these
96 bit positions are reserved for the birthday bits. Because only 64 + k = 72
birthdaying bits per side will be needed (and appended in Step 3) the first
24 bits at this point are set to 0. On the legitimate side these 96 bits arepart of the RSA modulus, on the rogue side they are part of an extension
field of the type “Netscape Comment”, denoted as ‘tumor’ in Figure 2.
– From here on forward, everything that goes to the rogue side is part of
the “Netscape Comment” field, as it is not meaningful for the rogue CA
certificate but only appended to cause and maintain a collision with bits
added to the legitimate side. On the legitimate side we first make spacefor 3 near-collision blocks of 512 bits each (calculated in Step 3) and for 208
40

bits used to complete a 2048-bit RSA modulus (determined in Step 4), andthen set the RSA public exponent (for which we took the common choice65537) and the X.509v3 extensions including the bit indicating that thelegitimate certificate will be an end-user certificate (in Figure 2 denoted by“CA=FALSE”).
Step 2. Prediction of serial number and validity period. Based on repeated certification requests submitted to the targeted commercial CA, it turned
out that the validity period can very reliably be predicted as the period of precisely one year plus one day, starting exactly six seconds after a request is submitted. So, to control that field, all we need to do is select a validity periodof the right length, and submit the legitimate certification request precisely six
seconds before it starts. Though occasional accidents may happen in the formof one-second shifts, this was the easy part.
Predicting the serial number is harder but not impossible. In the first place, it
was found that the targeted commercial CA uses sequential serial numbers. Being
able to predict the next serial number, however, is not enough: the construction of
the collision can be expected to take at least a day, before which the serial number
and validity period have to be fixed, and only after which the to-be-signed partof the certificate will be entirely known. As a consequence, there will have been asubstantial and uncertain increment in the serial number by the time the collision
construction is finished. So, another essential ingredient of our construction was
the fact that the CA’s weekend workload is quite stable: it was observed during
several weekends that the increment in serial number over a weekend does notvary a lot. This allowed us to pretty reliably predict Monday morning’s serial
numbers on the Friday afternoon before. Thus, on Friday afternoon we selected
a number at the high end of the predicted range for the next Monday morning,
and inserted it in the legitimate to-be-signed part along with a validity period
starting that same Monday morning at the time corresponding to our serial
number prediction. See Step 6 how we then managed, after the weekend, totarget precisely the selected serial number and validity period.
Step 3. Computation of the collision. At this point both chosen prefixes
have been fully determined so the chosen-prefix collision can be computed: first
the 72 birthday bits per side, calculated in parallel on the 1290 SPUs of a clusterof 215 PS3s, followed by the calculation of 3 pairs of 512-bit near-collision blocks
on the 215 PS3 CPUs. The entire calculation takes on average about a day.
Given that we had a weekend available, and that the calculation can be expected to take just a day, we sequentially processed a number of chosen-prefixes,
each corresponding to different serial numbers and validity periods (targeting
both Monday and Tuesday mornings). So, a near-collision block calculation on
the CPUs would always run simultaneously with a birthday search on the SPUs
for the ‘next’ attempt.
Step 4. Finishing the to-be-signed parts. At this point the legitimate androgue sides collide under MD5, so that from here on only identical bits may beappended to both sides.
41

With 208 + 24 + 72 + 3 ∗ 512 = 1840 bits set, the remaining 2048 − 1840 = 208
bits need to be set for the 2048-bit RSA modulus on the legitimate side. Because
in the next step the RSA private exponent corresponding to the RSA public
exponent is needed, the full factorization of the RSA modulus needs to be known,
and the factors must be compatible with the choice of the RSA public exponent.
Because common CAs (including our targeted commercial CA) do not check forcompositeness of RSA moduli in certification requests, we could simply haveadded 208 bits to make the RSA modulus a prime. We found that approach
unsatisfactory, and opted for the rather crude but trivial to program method
sketched below that results in a 224-bit prime factor with a prime 1824-bit
cofactor. Given that at the time this work was done the largest factor foundusing the elliptic curve integer factorization method was 222 bits long, a 224bit smallest prime factor keeps the resulting modulus out of reach of common
factoring efforts. We could have used a relatively advanced lattice-based method
to try and squeeze in a 312-bit prime factor along with a prime 1736-bit cofactor.
Given only 208 bits of freedom to select a 2048-bit RSA modulus, it is unlikelythat a more balanced solution can efficiently be found. Thus the reason why as
few bits as possible should be fixed in Step 1, is that it allows us to construct aslightly less unbalanced RSA modulus.
Let N be the 2048-bit integer consisting of the 1840 already determined bitsof the RSA modulus-to-be, followed by 208 one bits. We select a 224-bit integer p
at random until N mod p is less than 2208 , and keep doing this until both p andq = bN/pc are prime and the RSA public exponent is coprime to (p − 1)(q − 1).
Once such primes p and q have been found, the number pq will be the legitimate
side’s RSA modulus, the leading 1840 bits of which are already present in thelegitimate side’s to-be-signed part, and the 208 least significant bits of which are
inserted in both to-be-signed parts.
To analyse the required effort somewhat more in general, 2k−208 integers ofk bits (with k > 208) need to be selected on average for pq to have the desired
1840 leading bits. Since an `-bit integer is prime with probability approximately
1/ log(2` ), a total of k(2048 − k)2k−208 (log 2)2 attempts may be expected before
a suitable RSA modulus is found. The coprimality requirement is a lower ordereffect that we disregard. Note that for k(k − 2048)(log 2)2 of the attempts the
k-bit number p has to be tested for primality, and that for (2048 − k) log 2 ofthose q needs to be tested as well (on average, obviously). For k = 224 thisturned out to be doable in a few minutes on a standard PC.
This completes the to-be-signed parts on both sides. Now it remains to be
hoped that the legitimate part that actually will be signed corresponds, bit for
bit, with the legitimate to-be-signed part that we concocted.
Step 5. Preparing the certification request. Using the relevant informationfrom the legitimate side’s template, i.e., the subject Distinguished Name andthe public key, a PKCS#10 Certificate Signing Request is prepared. The CA
requires proof of possession of the private key corresponding to the public key
in the request. This is done by signing the request using the private key – thisis the sole reason that we need the RSA private exponent.
42Step 6. Submission of the certification request. The targeted legitimate
to-be-signed part contains a very specific validity period that leaves no choice forthe moment at which the certification request needs to be submitted to the CA.
Just hoping that at that time the serial number would have precisely the predicted value is unlikely to work, so a somewhat more elaborate approach is used.
About half an hour before the targeted submission moment, the same request
is submitted, and the serial number in the resulting certificate is inspected. If
it is already too high, the entire attempt is abandoned. Otherwise, the request
is repeatedly submitted, with a frequency depending on the gap that may still
exist between the serial number received and the targeted one, and taking into
account possible certification requests by others. In this way the serial number
is slowly nudged toward the right value at the right time. Although there isnothing illegal about repeated certification requests, it should be possible for a
CA to recognize the somewhat anomalous behavior sketched above and to takeappropriate countermeasures (such as random delays or jumps in serial numbers)
if it occurs.
Various types of accidents may happen, of course, and we experienced someof them, such as another CA customer ‘stealing’ our targeted serial number justa few moments before our attempt to get it, thereby wasting that weekend’s calculations. But, after the fourth weekend it worked as planned, and we managed
to get an actually signed part that exactly matched our predicted legitimate
to-be-signed part.
Step 7. Creation of the rogue certificate. Given the perfect match between
the actually signed part and the hoped for one, and the MD5 collision between
the latter and the rogue side’s to-be-signed part, the MD5-based digital signaturepresent in the legitimate certificate as provided by the commercial CA is equallyvalid for the rogue side. To finish the rogue CA certificate it suffices to copy thedigital signature to the right spot in the rogue CA certificate.
The full details of the above construction, including both certificates, can befound on http://www.win.tue.nl/hashclash/rogue-ca/.
4.3

Nostradamus attack

In the original Nostradamus attack from [15] one first commits to a certain
hash value, and afterwards for any message constructs a document that not only
contains that message but that also has the committed hash value. In its fullgenerality, this attack is at this point in time not feasible for MD5. It is easily
doable, though, if a limited size message space has been defined upfront.
Suppose there are messages m1 , m2 , . . . , mr , then using r − 1 chosen-prefix
collisions we can construct r suffixes s1 , s2 , . . . , sr such that the r documents di =mi ksi all have the same hash. After committing to the common hash, afterwards
any of the r documents d1 , d2 , . . . , dr can be shown, possibly to achieve somemalicious goal. The other documents will remain hidden and their contents, i.e.,the mi -parts, cannot be derived – with overwhelming probability – from thesingle published document or from the common hash value.
43

To show the practicality of this variant, we have made an example consistingof 12 different PDF documents with a common MD5-hash, where each document
predicts a different outcome of the 2008 US presidential elections. The PDF
format is convenient for this purpose because it allows insertion of extra image
objects that are unreferenced in the resulting document and thus invisible in any
common PDF reader. See the next section for more on the PDF related detailsof the construction and http://www.win.tue.nl/hashclash/Nostradamus/ forthe actual documents, one of which correctly predicted the outcome one year
before the elections took place. For each of the 11 collisions required for thisexample we used a 64-bit birthday search (on a single PS3) aiming for about 11
near-collision blocks (constructed on a quad-core PC). It took less than 2 days
per chosen-prefix collision. Since we performed those computations our methods
have improved as described in this paper, so this attack would now run much
faster.
4.3.1 PDF construction
Given the structure of PDF documents it is not entirely straightforward how toinsert different chosen-prefix collision blocks, while keeping the parts following
those blocks identical in order to maintain the collision. The relevant details ofboth the PDF structure and our construction are covered here.
A PDF document is built up from the following 4 consecutive parts: a fixed
header, a part consisting of an arbitrary number of numbered objects, an object
lookup table and, finally, a trailer. The trailer specifies the number of objects,
which of the objects is the unique root object (containing the document content)
and which is the info object (containing the document’s meta information suchas authors and title etc.), and contains a filepointer to the start of the object
lookup table.
Given a file containing a PDF document, additional numbered objects can beinserted, as long as they are added to the object lookup table and the corresponding changes are made to the number of objects and the filepointer in the trailer.
A template for an image object is given in Table 4-1. With the exception of thebinary image, the format is entirely text based. The binary image is put between
single line-feed characters (ASCII code 10) and the result is encapsulated by the
keywords stream and endstream. The keyword /Length must specify the byte
length of the image. Because the image is uncompressed and each pixel requires
three bytes (‘RGB’), the image byte length must be three times the product of
the specified width and height. The object number (42 in the example object
header) must be set to the next available object number.
When constructing colliding PDF files they must be equal after the collisioncausing data. The object lookup tables and trailers for all files must therefore
be the same. This was achieved as follows:– Because all documents must have the same number of objects, dummy objects are inserted where necessary.
– Because all root objects must have the same object number, they can becopied if necessary to objects with the next available object number.
44

Table 4-1. A numbered image object in the PDF format.
Part

Contents

object header 42 0 obj
image header << /ColorSpace /DeviceRGB /Subtype /Image
image size
/Length 9216 /Width 64 /Height 48 /BitsPerComponent 8
image contents >> stream...endstream
object footer endobj– The info objects are treated in the same way as the root objects.
– To make sure that all object lookup tables and filepointers are identical, theobjects can be sorted by object number and if necessary padded with spaces
after their obj keyword to make sure that all objects with the same object
number have the same file position and byte length in all files.
– Finally, the object lookup tables and trailers need to be adapted to reflect
the new situation – as a result they should be identical for all files.
Although this procedure works for basic PDF files (such as PDF version 1.4 as
we produced using pdflatex), it should be noted that the PDF document format
allows additional features that may cause obstructions.
Given r LATEX files with the desired subtle differences (such as names of rdifferent candidates), r different PDF files are produced using a version of LATEX
that is suitable for our purposes (cf. above). In all these files a hidden image
object with a fixed object number is then inserted, and the approach sketchedabove is followed to make the lookup tables and trailers for all files identical.
To ensure that the files are identical after the hidden image contents, theircorresponding objects were made the last objects in the files. This then leads
to r chosen prefixes consisting of the leading parts of the PDF files up to andincluding the keyword stream and the first line-feed character. After determiningr − 1 chosen-prefix collisions resulting in r collision-causing appendages, theappendages are put in the proper binary image parts, after which all files arecompleted with a line-feed character, the keywords endstream and endobj, andthe identical lookup tables and trailers.
Note that the Length etc. fields have to be set before collision finding, andthat the value of Length will grow logarithmically with r and linearly in thenumber of near-collision blocks one is aiming for.
4.4

Colliding executables

Using the same set-up as used for the Nostradamus attack reported in Section 4.3, i.e., 64-bit birthdaying on a PS3 followed by the construction of about
12 near-collision blocks on a quad-core PC, it took us less than 2 days to create
two different Windows executables with the same MD5 hash.

45

Initially both 40960 bytes large, 13 × 64 bytes had to be appended to each
executable, for a resulting size of just 41792 bytes each, to let the files collide
under MD5 without changing their functionality. See http://www.win.tue.nl/
hashclash/SoftIntCodeSign/ for details. As noted above, it has been shownon http://blog.didierstevens.com/2009/01/17/ that this attack can be elevated to one on a code signing scheme.
As usual, the following remarks apply:– An existing executable with a known and published hash value not resulting from this construction cannot be targeted by this attack: our attack is
not a preimage or second preimage attack. In order to attack a software integrity protection or code signing scheme using this approach, the attacker
must be able to manipulate the files before they are hashed (and, possibly,
signed). Given the level of access required to realize the attack an attacker
can probably do more harm in other simpler and more traditional ways.
– On the other hand, there is no guarantee that a downloaded file with theproper hash or correct signature is not the evil sibling of the intended file.
Especially when software integrity verification takes place under the hood,users may be lured into installing – and trusting – malware. Until a tool isavailable that would also be able to distinguish potentially malicious MD5based certificates, all a relying party can do is resorting to bit-level inspectionof each executable; the latter requires more expertise than most users canbe expected to have, in particular if the collision blocks are hidden at a lessconspicious place than at the very end of the executable.
– Any number r of executables can be made to collide, at the cost of r − 1chosen-prefix collisions and an O(log r)-byte appendage to each of the roriginal executables.
A countermeasure thwarting our attack would be the inclusion of a self-checking
component in software, i.e., where the software would check the integrity of its
own executable as the first step of the execution. It is better, however, not to rely
on cryptographic primitives such as MD5 that fail to meet their design criteria.

Acknowledgements
This work benefited greatly from suggestions by Xiaoyun Wang. We are gratefulfor comments and assistance received from the anonymous Eurocrypt 2007 reviewers, and from Jacob Appelbaum, Joppe Bos, Stuart Haber, Paul Hoffman,
Pascal Junod, Vlastimil Klima, David Molnar, Dag Arne Osvik, Bart Preneel,
NBV, Werner Schindler, Gido Schmitz, Alexander Sotirov, Eric Verheul, andYiqun Lisa Yin.
This work has been supported in part by the Swiss National Science Foundation under grant number 206021-117409, by EPFL DIT, and by the European
Commission through the EU ICT program ECRYPT II.
46

References
1. Steven M. Bellovin and Eric K. Rescorla, Deploying a New Hash Algorithm,
in: Proceedings of the Network and Distributed System Security Symposium, NDSS 2006, San Diego, California, USA, The Internet Society, 2006.
Available from http://www.isoc.org/isoc/conferences/ndss/06/proceedings/
papers/deploying_new_hash_algorithm.pdf.
2. B. den Boer and A. Bosselaers, Collisions for the compression function of MD5,
Eurocrypt ’93, Springer LNCS 765, pp. 293–304, 1994.
3. Bundesnetzagentur für Elektrizität, Gas, Telekommunikation, Post und Eisenbahnen, Bekanntmachung zur elektronischen Signatur nach dem Signaturgesetz und der
Signaturverordnung (Übersicht über geeignete Algorithmen), December 2007, Bundesanzeiger Nr. 19, p. 376, 2008. Available from http://www.bundesnetzagentur.
de/media/archive/12198.pdf.
4. Christophe de Cannière and Christian Rechberger, Finding SHA-1 Characteristics:
General results and applications, AsiaCrypt 2006, Springer LNCS 4284, pp. 1–20,
2006.
5. W. Clark and J. Liang, On arithmetic weight for a general radix representation of
integers, IEEE Transactions on Information Theory, 19(6), 823 – 826, 1973.
6. D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley, W. Polk, Internet
X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL)
Profile, IETF RFC 5280, May 2008, http://www.ietf.org/rfc/rfc5280.txt.
7. M. Daum and S. Lucks, Attacking Hash Functions by Poisoned Messages, “TheStory of Alice and her Boss”, June 2005, http://th.informatik.uni-mannheim.
de/People/lucks/HashCollisions/.
8. H. Dobbertin, Cryptanalysis of MD5 Compress, EuroCrypt’96 Rump session, May
1996, http://www-cse.ucsd.edu/~bsy/dobbertin.ps.
9. P. Gauravaram, A. McCullagh and E. Dawson, Collision Attacks on MD5 andSHA-1: Is this the “Sword of Damocles” for Electronic Commerce?, AusCERT
2006 R&D Stream, May 2006, http://www2.mat.dtu.dk/people/P.Gauravaram/
AusCert-6.pdf.
10. M. Gebhardt, G. Illies and W. Schindler, A Note on Practical Value of Single Hash Collisions for Special File Formats, NIST First Cryptographic Hash
Workshop, October/November 2005, http://csrc.nist.gov/groups/ST/hash/documents/Illies_NIST_05.pdf.
11. S. Halevi and H. Krawczyk, Strengthening Digital Signatures via Randomized Hashing, Crypto 2006, Springer LNCS 4117, pp. 41–59, 2006.
12. Philip Hawkes, Michael Paddon and Gregory G. Rose, Musings on the Wang etal. MD5 Collision, Cryptology ePrint Archive, Report 2004/264, http://eprint.
iacr.org/2004/264.
13. P. Hoffman and B. Schneier, Attacks on Cryptographic Hashes in Internet Protocols, IETF RFC 4270, November 2005, http://www.ietf.org/rfc/rfc4270.txt.
14. D. Kaminsky, MD5 to be considered harmful someday, December 2004, http://
www.doxpara.com/research/md5/md5_someday.pdf.
15. J. Kelsey and T. Kohno, Herding Hash Functions and the Nostradamus Attack,Eurocrypt 2006, Springer LNCS 4004, pp. 183–200, 2006.
16. Vlastimil Klima, Finding MD5 Collisions on a Notebook PC Using Multi-message
Modifications, Cryptology ePrint Archive, Report 2005/102, http://eprint.iacr.
org/2005/102.

47

17. Vlastimil Klima, Tunnels in Hash Functions: MD5 Collisions Within a Minute,
Cryptology ePrint Archive, Report 2006/105, http://eprint.iacr.org/2006/
105.
18. A.K. Lenstra and B.M.M. de Weger, On the possibility of constructing meaningful hash collisions for public keys, ACISP 2005, Springer LNCS 3574, pp.
267–279, 2005. Full version available from http://www.win.tue.nl/~bdeweger/
CollidingCertificates/ddl-full.pdf.
19. Cameron McDonald, Philip Hawkes and Josef Pieprzyk, SHA-1 collisions
now 252 , Eurocrypt 2009 Rump session, http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf.
20. Florian Mendel, Christian Rechberger and Vincent Rijmen, Update on SHA-1,
Crypto 2007 Rump session, http://rump2007.cr.yp.to/09-rechberger.pdf.
21. O. Mikle, Practical Attacks on Digital Signatures Using MD5 Message Digest,
Cryptology ePrint Archive, Report 2004/356, http://eprint.iacr.org/2004/
356.
22. Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology 12(1), 1–28, 1999.
23. Robert Primmer and Carl D’Halluin, Collision and Preimage Resistance of theCentera Content Address, Technical Report, EMC Corporation, 2005, http://
www.robertprimmer.com/rjp/tech/mine/CenteraCollisionProbs.pdf.
24. Christian Rechberger, unpublished result, 2006.
25. R. Rivest, The MD5 Message-Digest Algorithm, IETF RFC 1321, April 1992, http://www.ietf.org/rfc/rfc1321.txt.
26. Marc Stevens, Fast Collision Attack on MD5, Cryptology ePrint Archive, Report
2006/104, http://eprint.iacr.org/2006/104.
27. Marc Stevens, On Collisions for MD5, TU Eindhoven MSc thesis, June 2007. Available from http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%
20-%20M.M.J.%20Stevens.pdf.
28. Marc Stevens, Arjen Lenstra and Benne de Weger, Chosen-Prefix Collisions forMD5 and Colliding X.509 Certificates for Different Identities, in M. Naor (Ed.),
Eurocrypt 2007, Springer LNCS 4515, pp. 1–22, 2007.
29. Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar,
Dag Arne Osvik and Benne de Weger, Short chosen-prefix collisions for MD5 andthe creation of a rogue CA certificate, Crypto 2009, Springer LNCS 5677, 2009.
30. X. Wang, D. Feng, X. Lai and H. Yu, Collisions for Hash Functions MD4, MD5,HAVAL-128 and RIPEMD, Cryptology ePrint Archive, Report 2004/199, http://eprint.iacr.org/2004/199.
31. Xiaoyun Wang, Andrew Yao and Frances Yao, New Collision Search for SHA-1,
Crypto 2005 Rump session, http://www.iacr.org/conferences/crypto2005/r/
2.pdf.
32. Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full
SHA-1, Crypto 2005, Springer LNCS 3621, pp. 17–36, 2005.
33. X. Wang and H. Yu, How to Break MD5 and Other Hash Functions, Eurocrypt
2005, Springer LNCS 3494, pp. 19–35, 2005.
34. Tao Xie, FanBao Liu and DengGuo Feng, Could The 1-MSB Input Difference
Be The Fastest Collision Attack For MD5?, Cryptology ePrint Archive, Report
2008/391, http://eprint.iacr.org/2008/391.

48

A

MD5 compression function constants

Table A-1. MD5 Addition and Rotation Constants and message block expansion.
RCt Wtt

0 d76aa47816
1 e8c7b75616
2 242070db16
3 c1bdceee16
4 f57c0faf16
5 4787c62a16
6 a830461316
7 fd46950116
8 698098d816
9 8b44f7af16
10 ffff5bb116
11 895cd7be16
12 6b90112216
13 fd98719316
14 a679438e16
15 49b4082116

t

ACt

7
12
17
22
7
12
17
22
7
12
17
22
7
12
17
22

16 f61e256216
17 c040b34016
18 265e5a5116
19 e9b6c7aa16
20 d62f105d16
21 0244145316
22 d8a1e68116
23 e7d3fbc816
24 21e1cde616
25 c33707d616
26 f4d50d8716
27 455a14ed16
28 a9e3e90516
29 fcefa3f816
30 676f02d916
31 8d2a4c8a16

5
9
14
20
5
9
14
20
5
9
14
20
5
9
14
20

t

RCt Wtt

RCt Wt

4
11
16
23
4
11
16
23
4
11
16
23
4
11
16
23

48 f429224416
49 432aff9716
50 ab9423a716
51 fc93a03916
52 655b59c316
53 8f0ccc9216
54 ffeff47d16
55 85845dd116
56 6fa87e4f16
57 fe2ce6e016
58 a301431416
59 4e0811a116
60 f7537e8216
61 bd3af23516
62 2ad7d2bb16
63 eb86d39116

ACt

32 fffa394216
33 8771f68116
34 6d9d612216
35 fde5380c16
36 a4beea4416
37 4bdecfa916
38 f6bb4b6016
39 bebfbc7016
40 289b7ec616
41 eaa127fa16
42 d4ef308516
43 04881d0516
44 d9d4d03916
45 e6db99e516
46 1fa27cf816
47 c4ac566516

m0
m1
m2
m3
m4
m5
m6
m7
m8
m9
m10
m11
m12
m13
m14
m15

m5
m8
m11
m14
m1
m4
m7
m10
m13
m0
m3
m6
m9
m12
m15
m2

49

ACt

ACt

RCt Wt

6
10
15
21
6
10
15
21
6
10
15
21
6
10
15
21

m1
m6
m11
m0
m5
m10
m15
m4
m9
m14
m3
m8
m13
m2
m7
m12

m0
m7
m14
m5
m12
m3
m10
m1
m8
m15
m6
m13
m4
m11
m2
m9

B

Boolean Function Bitconditions

The 4 tables in this appendix correspond to rounds 1 through 4, respectively, i.e.,
0 ≤ t < 16, 16 ≤ t < 32, 32 ≤ t < 48 and 48 ≤ t < 64. The ‘abc’ in each of thefirst columns denotes the three differential bitconditions (qt [i], qt−1 [i], qt−2 [i]) for
the relevant t and 0 ≤ i ≤ 31, with each table containing all 27 possible triples.
Columns 2, 3, 4 contain forward bitconditions F C(t, abc, g) for g = 0, +1, −1,
respectively, and columns 5, 6, 7 contain backward bitconditions BC(t, abc, g)
for those same g’s, respectively. The parenthesized number next to a triple def
is |Udef |, the amount of freedom left. An entry is left empty if g ∈/ Vabc . See
section 3.6.3 for more details.
B.1

Bitconditions applied to boolean function F

Table B-1. Round 1 (0 ≤ t < 16) bitconditions applied to boolean function F :F (X, Y, Z) = (X ∧ Y ) ⊕ (X ∧ Z)
DB
Forward bitconditions Backward bitconditionsabc
g = 0 g = +1 g = −1 g = 0 g = +1 g = −1... (8) ... (8)... (8)..+ (4) 1.+ (2) 0.+ (2)
1.+ (2) 0.+ (2)..- (4) 1.- (2)0.- (2) 1.- (2)0.- (2).+. (4) 0+. (2) 1+. (2)0+. (2) 1+. (2).++ (2).++ (2).++ (2).+- (2)
1+- (1) 0+- (1)
1+- (1) 0+- (1).-. (4) 0-. (2)
1-. (2) 0-. (2)
1-. (2).-+ (2)0-+ (1) 1-+ (1)0-+ (1) 1-+ (1).-- (2).-- (2).-- (2)+.. (4) +.V (2) +10 (1) +01 (1) +^. (2) +10 (1) +01 (1)+.+ (2) +0+ (1) +1+ (1)+0+ (1) +1+ (1)+.- (2) +1- (1)+0- (1) +1- (1)+0- (1)++. (2) ++1 (1) ++0 (1)++1 (1) ++0 (1)+++ (1)+++ (1)+++ (1)++- (1) ++- (1)++- (1)+-. (2) +-0 (1)+-1 (1) +-0 (1)+-1 (1)+-+ (1) +-+ (1)+-+ (1)+-- (1)+-- (1)+-- (1)-.. (4) -.V (2) -01 (1) -10 (1) -^. (2) -01 (1) -10 (1)-.+ (2) -1+ (1) -0+ (1)-1+ (1) -0+ (1)-.- (2) -0- (1)-1- (1) -0- (1)-1- (1)-+. (2) -+0 (1) -+1 (1)-+0 (1) -+1 (1)-++ (1)-++ (1)-++ (1)-+- (1) -+- (1)-+- (1)--. (2) --1 (1)--0 (1) --1 (1)--0 (1)--+ (1) --+ (1)--+ (1)--- (1)--- (1)--- (1)50

B.2

Bitconditions applied to boolean function G

Table B-2. Round 2 (16 ≤ t < 32) bitconditions applied to boolean function G:
G(X, Y, Z) = (Z ∧ X) ⊕ (Z ∧ Y )DBForward bitconditions Backward bitconditionsabc
g = 0 g = +1 g = −1 g = 0 g = +1 g = −1... (8) ... (8)... (8)..+ (4) .V+ (2) 10+ (1) 01+ (1) ^.+ (2) 10+ (1) 01+ (1)..- (4) .V- (2) 01- (1) 10- (1) ^.- (2) 01- (1) 10- (1).+. (4) .+1 (2) .+0 (2).+1 (2) .+0 (2).++ (2) 0++ (1) 1++ (1)0++ (1) 1++ (1).+- (2) 1+- (1) 0+- (1)
1+- (1) 0+- (1).-. (4) .-1 (2).-0 (2) .-1 (2).-0 (2).-+ (2) 1-+ (1)0-+ (1) 1-+ (1)0-+ (1).-- (2) 0-- (1)1-- (1) 0-- (1)1-- (1)+.. (4) +.0 (2) +.1 (2)+.0 (2) +.1 (2)+.+ (2) +1+ (1) +0+ (1)+1+ (1) +0+ (1)+.- (2) +0- (1) +1- (1)+0- (1) +1- (1)++. (2)++. (2)++. (2)+++ (1)+++ (1)+++ (1)++- (1)++- (1)++- (1)+-. (2)+-1 (1) +-0 (1)+-1 (1) +-0 (1)+-+ (1) +-+ (1)+-+ (1)+-- (1) +-- (1)+-- (1)-.. (4) -.0 (2)-.1 (2) -.0 (2)-.1 (2)-.+ (2) -0+ (1)-1+ (1) -0+ (1)-1+ (1)-.- (2) -1- (1)-0- (1) -1- (1)-0- (1)-+. (2)-+0 (1) -+1 (1)-+0 (1) -+1 (1)-++ (1) -++ (1)-++ (1)-+- (1) -+- (1)-+- (1)--. (2)--. (2)--. (2)--+ (1)--+ (1)--+ (1)--- (1)--- (1)--- (1)51

B.3

Bitconditions applied to boolean function H

Table B-3. Round 3 (32 ≤ t < 48) bitconditions applied to boolean function H:
H(X, Y, Z) = X ⊕ Y ⊕ Z
DBForward bitconditions Backward bitconditionsabc
g = 0 g = +1 g = −1 g = 0 g = +1 g = −1... (8) ... (8)... (8)..+ (4).V+ (2) .Y+ (2)^.+ (2) !.+ (2)..- (4).Y- (2) .V- (2)!.- (2) ^.- (2).+. (4).+W (2) .+H (2)m+. (2) #+. (2).++ (2) .++ (2).++ (2).+- (2) .+- (2).+- (2).-. (4).-H (2) .-W (2)#-. (2) m-. (2).-+ (2) .-+ (2).-+ (2).-- (2) .-- (2).-- (2)+.. (4)+.V (2) +.Y (2)+^. (2) +!. (2)+.+ (2) +.+ (2)+.+ (2)+.- (2) +.- (2)+.- (2)++. (2) ++. (2)++. (2)+++ (1)+++ (1)+++ (1)++- (1)++- (1)++- (1)+-. (2) +-. (2)+-. (2)+-+ (1)+-+ (1)+-+ (1)+-- (1)+-- (1)+-- (1)-.. (4)-.Y (2) -.V (2)-!. (2) -^. (2)-.+ (2) -.+ (2)-.+ (2)-.- (2) -.- (2)-.- (2)-+. (2) -+. (2)-+. (2)-++ (1)-++ (1)-++ (1)-+- (1)-+- (1)-+- (1)--. (2) --. (2)--. (2)--+ (1)--+ (1)--+ (1)--- (1)--- (1)--- (1)52

B.4

Bitconditions applied to boolean function I

Table B-4. Round 4 (48 ≤ t < 64) bitconditions applied to boolean function I:
I(X, Y, Z) = Y ⊕ (X ∨ Z)
DB
Forward bitconditions Backward bitconditionsabc
g = 0 g = +1 g = −1 g = 0 g = +1 g = −1... (8) ... (8)... (8)..+ (4) 1.+ (2) 01+ (1) 00+ (1) 1.+ (2) 01+ (1) 00+ (1)..- (4) 1.- (2) 00- (1) 01- (1) 1.- (2) 00- (1) 01- (1).+. (4)0+1 (1) .+Q (3)0+1 (1) ?+. (3).++ (2) 0++ (1)
1++ (1) 0++ (1)
1++ (1).+- (2) 0+- (1)
1+- (1) 0+- (1)
1+- (1).-. (4).-Q (3) 0-1 (1)?-. (3) 0-1 (1).-+ (2) 0-+ (1) 1-+ (1)0-+ (1) 1-+ (1).-- (2) 0-- (1) 1-- (1)0-- (1) 1-- (1)+.. (4) +.0 (2) +01 (1) +11 (1) +.0 (2) +01 (1) +11 (1)+.+ (2) +.+ (2)+.+ (2)+.- (2)+0- (1) +1- (1)+0- (1) +1- (1)++. (2) ++1 (1)++0 (1) ++1 (1)++0 (1)+++ (1)+++ (1)+++ (1)++- (1) ++- (1)++- (1)+-. (2) +-1 (1) +-0 (1)+-1 (1) +-0 (1)+-+ (1)+-+ (1)+-+ (1)+-- (1) +-- (1)+-- (1)-.. (4) -.0 (2) -11 (1) -01 (1) -.0 (2) -11 (1) -01 (1)-.+ (2)-1+ (1) -0+ (1)-1+ (1) -0+ (1)-.- (2) -.- (2)-.- (2)-+. (2) -+1 (1)-+0 (1) -+1 (1)-+0 (1)-++ (1) -++ (1)-++ (1)-+- (1)-+- (1)-+- (1)--. (2) --1 (1) --0 (1)--1 (1) --0 (1)--+ (1) --+ (1)--+ (1)--- (1)--- (1)--- (1)53

C

Birthday Cost

In this appendix notation and variables are as in Section 3.4. The columns p,
Ctr and M denote the values − log2 (pr,k,w ), log2 (Ctr (r, k, w)) and the minimum
required memory such that Ccoll (r, k, w, M ) ≤ Ctr (r, k, w), respectively.

r=3
k
0
4
8
12
16
20
24
28
32
r=3
k
0
4
8
12
16
20
24
28
32

p

w=0
Ctr
M

p

w=1
Ctr
M

p

w=2
Ctr
M

p

w=3
Ctr
M

34.01 51.33 2TB
33.42 53.03 748GB 31.31 51.98 174GB
34.01 55.33 2TB 32.42 54.53 374GB 30.55 53.6 103GB 28.24 52.44 21GB
31. 55.83 141GB 29.65 55.15 55GB 27.36 54.01 12GB 25.6 53.13 4GB
27.51 56.08 13GB 26.18 55.42 5GB 24.53 54.59 2GB 23.26 53.96 673MB
24.33 56.49 2GB 23.35 56. 714MB 22.17 55.41 315MB 21.19 54.92 160MB
21.11 56.88 152MB 20.56 56.6 103MB 19.98 56.32 70MB 19.57 56.11 52MB
17.88 57.26 17MB 17.88 57.27 17MB 17.89 57.27 17MB 17.88 57.27 17MB
p

w=4
Ctr
M

p

w=5
Ctr
M

p

w=6
Ctr
M

p

w=7
Ctr
M

31.68 48.17 225GB 30.25 47.45 84GB 28.01 46.33 18GB
32.2 50.43 323GB 29.92 49.29 67GB 28.06 48.36 19GB 26.2 47.43 6GB
28.83 50.74 32GB 27.33 49.99 11GB 25.88 49.26 5GB 24.47 48.56 2GB
26.63 51.64 7GB 25.14 50.9 3GB 23.96 50.3 2GB 22.94 49.8 537MB
24.31 52.48 2GB 23.27 51.96 675MB 22.49 51.57 394MB 21.86 51.26 255MB
22.28 53.46 340MB 21.62 53.13 215MB 21.14 52.9 155MB 20.73 52.69 117MB
20.53 54.59 102MB 20.01 54.33 71MB 19.65 54.15 55MB 19.38 54.01 46MB
19.25 55.95 42MB 19.02 55.83 36MB 18.82 55.74 31MB 18.65 55.65 28MB
17.88 57.27 17MB 17.88 57.27 17MB 17.88 57.27 17MB 17.88 57.27 17MB

54

r=4
k
0
4
8
12
16
20
24
28
32
r=4
k
0
4
8
12
16
20
24
28
32

r=5
k
0
4
8
12
16
20
24
28
32
r=5
k
0
4
8
12
16
20
24
28
32

p

w=0
Ctr
M

p

w=1
Ctr
M

p

w=2
Ctr
M

p

w=3
Ctr
M

34. 49.33 2TB 30.19 47.42 81GB
33.42 51.04 749GB 30.36 49.51 90GB 27.59 48.12 14GB
35. 53.83 3TB 30.3 51.48 87GB 27.21 49.93 11GB 24.87 48.76 2GB
29.58 53.12 53GB 27.53 52.09 13GB 24.59 50.62 2GB 22.47 49.56 388MB
26.26 53.45 6GB 24.36 52.51 2GB 22.06 51.36 292MB 20.38 50.51 91MB
23.16 53.91 628MB 21.5 53.08 199MB 19.72 52.19 58MB 18.54 51.6 26MB
20.25 54.45 84MB 19.09 53.87 38MB 17.8 53.23 16MB 16.86 52.76 8MB
17.26 54.95 11MB 16.63 54.64 7MB 16.02 54.34 5MB 15.6 54.13 4MB
14.29 55.47 2MB 14.29 55.47 2MB 14.29 55.47 2MB 14.29 55.47 2MB
p

w=4
Ctr
M

p

w=5
Ctr
M

p

w=6
Ctr
M

p

w=7
Ctr
M

26.98 45.81 9GB 24.45 44.55 2GB 22.14 43.4 310MB 20.33 42.49 88MB
24.95 46.8 3GB 22.82 45.73 493MB 21.04 44.84 144MB 19.55 44.1 52MB
22.63 47.64 432MB 20.92 46.79 133MB 19.58 46.12 53MB 18.56 45.61 26MB
20.67 48.66 112MB 19.41 48.03 47MB 18.45 47.55 24MB 17.71 47.18 15MB
19.08 49.86 37MB 18.19 49.42 21MB 17.56 49.1 13MB 17.08 48.86 10MB
17.66 51.16 14MB 17.09 50.87 10MB 16.7 50.67 8MB 16.39 50.52 6MB
16.25 52.45 6MB 15.82 52.24 4MB 15.54 52.09 4MB 15.33 51.99 3MB
15.31 53.98 3MB 15.09 53.87 3MB 14.93 53.79 3MB 14.78 53.72 2MB
14.29 55.47 2MB 14.29 55.47 2MB 14.29 55.47 2MB 14.29 55.47 2MB

p

w=0
Ctr
M

p

w=1
Ctr
M

p

w=2
Ctr
M

p

w=3
Ctr
M

35. 49.83 3TB 31.2 47.92 161GB 27.13 45.89 10GB 23.74 44.2 938MB
33.42 51.04 749GB 28.47 48.56 25GB 24.63 46.64 2GB 21.58 45.12 210MB
28.61 50.63 27GB 25.61 49.13 4GB
22. 47.33 280MB 19.39 46.02 46MB
25.43 51.04 3GB 22.74 49.7 468MB 19.66 48.15 56MB 17.53 47.09 13MB
22.36 51.51 360MB 20.02 50.34 72MB 17.59 49.12 14MB 15.95 48.3 5MB
19.38 52.01 46MB 17.48 51.07 13MB 15.67 50.16 4MB 14.55 49.6 2MB
16.68 52.66 7MB 15.35 52. 3MB 14.06 51.36 2MB 13.17 50.91 1MB
13.92 53.29 2MB 13.22 52.93 1MB 12.61 52.63 1MB 12.21 52.43 1MB
11.2 53.92 1MB 11.2 53.93 1MB 11.2 53.92 1MB 11.2 53.93 1MB
p

w=4
Ctr
M

p

w=5
Ctr
M

20.53 42.59 102MB 18.03 41.34 18MB
18.94 43.79 34MB 17. 42.82 9MB
17.27 44.96 11MB 15.79 44.22 4MB
15.92 46.28 5MB 14.84 45.75 2MB
14.8 47.73 2MB 14.06 47.35 2MB
13.79 49.22 1MB 13.31 48.98 1MB
12.64 50.64 1MB 12.29 50.47 1MB
11.95 52.3 1MB 11.76 52.2 1MB
11.2 53.92 1MB 11.2 53.93 1MB

55

p

w=6
Ctr
M

16.17 40.41
15.57 42.11
14.75 43.7
14.09 45.37
13.55 47.1
12.99 48.82
12.07 50.36
11.62 52.14
11.2 53.92

5MB
4MB
2MB
2MB
1MB
1MB
1MB
1MB
1MB

p

w=7
Ctr
M

14.92 39.79
14.53 41.59
14.01 43.33
13.56 45.11
13.18 46.92
12.76 48.7
11.91 50.28
11.5 52.07
11.2 53.93

3MB
2MB
2MB
1MB
1MB
1MB
1MB
1MB
1MB

r=6
k
0
4
8
12
16
20
24
28
32
r=6
k
0
4
8
12
16
20
24
28
32

r=7
k
0
4
8
12
16
20
24
28
32
r=7
k
0
4
8
12
16
20
24
28
32

p

w=0
Ctr
M

p

w=1
Ctr
M

p

w=2
Ctr
M

p

w=3
Ctr
M

31.2 47.92 161GB 26.73 45.69 8GB 21.78 43.22 241MB 18.14 41.4 20MB
28.18 48.42 20GB 23.89 46.27 2GB 19.56 44.11 52MB 16.46 42.55 6MB
24.66 48.66 2GB 21.17 46.91 158MB 17.37 45.01 12MB 14.79 43.72 2MB
21.67 49.16 224MB 18.6 47.62 27MB 15.43 46.04 3MB 13.4 45.03 1MB
18.82 49.74 31MB 16.21 48.43 6MB 13.74 47.2 1MB 12.23 46.44 1MB
16.03 50.34 5MB 13.97 49.31 2MB 12.2 48.43 1MB 11.18 47.92 1MB
13.54 51.1 1MB 12.11 50.38 1MB 10.86 49.75 1MB 10.04 49.35 1MB
11.03 51.84 1MB 10.28 51.47 1MB 9.69 51.17 1MB 9.33 50.99 1MB
8.56 52.6 1MB 8.56 52.6 1MB 8.56 52.6 1MB 8.56 52.6 1MB
p

w=4
Ctr
M

15.12 39.88
14.05 41.35
12.92 42.79
12.01 44.33
11.25 45.95
10.53 47.59
9.59 49.12
9.09 50.87
8.56 52.6

p

3MB
2MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

w=0
Ctr
M

p

w=5
Ctr
M

13.05 38.85
12.44 40.55
11.73 42.19
11.14 43.9
10.64 45.64
10.14 47.39
9.31 48.98
8.93 50.79
8.56 52.6

p

1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

w=1
Ctr
M

p

w=6
Ctr
M

11.73 38.19
11.39 40.02
10.95 41.8
10.57 43.61
10.24 45.45
9.89 47.27
9.14 48.9
8.82 50.74
8.56 52.6

p

1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

w=2
Ctr M

p

w=7
Ctr
M

10.91 37.78 1MB
10.7 39.68 1MB
10.44 41.54 1MB
10.2 43.42 1MB
9.98 45.32 1MB
9.72 47.19 1MB
9.04 48.85 1MB
8.73 50.69 1MB
8.56 52.6 1MB

p

w=3
Ctr M

26.82 45.73 8GB 22.2 43.43 323MB 17.02 40.83 9MB 13.4 39.02 1MB
24.02 46.34 2GB 19.68 44.16 56MB 15.16 41.9 3MB 12.18 40.41 1MB
21.1 46.88 151MB 17.23 44.94 11MB 13.37 43.01 1MB 10.97 41.81 1MB
18.32 47.49 22MB 14.96 45.8 3MB 11.82 44.24 1MB 9.98 43.31 1MB
15.67 48.16 4MB 12.87 46.76 1MB 10.48 45.56 1MB 9.13 44.89 1MB
13.1 48.88 1MB 10.93 47.79 1MB 9.26 46.95 1MB 8.35 46.5 1MB
10.82 49.74 1MB 9.32 48.99 1MB 8.15 48.4 1MB 7.43 48.04 1MB
8.56 50.6 1MB 7.78 50.22 1MB 7.23 49.94 1MB 6.91 49.78 1MB
6.34 51.5 1MB 6.34 51.5 1MB 6.34 51.5 1MB 6.34 51.5 1MB
p

w=4
Ctr
M

10.8 37.73
10.13 39.39
9.42 41.03
8.82 42.74
8.31 44.48
7.82 46.23
7.06 47.86
6.71 49.68
6.34 51.5

1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

p

w=5
Ctr
M

9.25 36.95
8.9 38.78
8.5 40.57
8.15 42.4
7.84 44.24
7.51 46.08
6.84 47.75
6.58 49.62
6.34 51.5

1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

56

p

w=6
Ctr M

8.35 36.5 1MB
8.17 38.41 1MB
7.94 40.3 1MB
7.74 42.19 1MB
7.55 44.1 1MB
7.32 45.99 1MB
6.72 47.69 1MB
6.5 49.58 1MB
6.34 51.5 1MB

p

w=7
Ctr M

7.84 36.25 1MB
7.74 38.19 1MB
7.61 40.13 1MB
7.48 42.07 1MB
7.37 44.01 1MB
7.21 45.93 1MB
6.66 47.65 1MB
6.43 49.54 1MB
6.34 51.5 1MB

r=8
k
0
4
8
12
16
20
24
28
32

w=0
Ctr
M

p

p

w=1
Ctr
M

p

w=2
Ctr M

p

w=3
Ctr M

23.39 44.02 732MB 18.21 41.43 21MB 12.88 38.76 1MB 9.52 37.09 1MB
20.57 44.61 105MB 15.94 42.29 5MB 11.39 40.02 1MB 8.69 38.67 1MB
17.91 45.28 17MB 13.77 43.21 1MB 9.99 41.32 1MB 7.86 40.26 1MB
15.35 46. 3MB 11.78 44.22 1MB 8.79 42.72 1MB 7.17 41.91 1MB
12.91 46.78 1MB
10. 45.32 1MB 7.75 44.2 1MB 6.59 43.62 1MB
10.56 47.61 1MB 8.35 46.5 1MB 6.81 45.73 1MB 6.03 45.34 1MB
8.49 48.57 1MB 6.97 47.81 1MB 5.91 47.28 1MB 5.29 46.97 1MB
6.48 49.56 1MB 5.71 49.18 1MB 5.21 48.93 1MB 4.93 48.79 1MB
4.54 50.6 1MB 4.54 50.6 1MB 4.54 50.6 1MB 4.54 50.6 1MB

r=8
k

p

0
4
8
12
16
20
24
28
32

7.45 36.05
7.06 37.85
6.63 39.64
6.26 41.46
5.94 43.29
5.61 45.13
5.01 46.83
4.78 48.71
4.54 50.6

r=9
k
0
4
8
12
16
20
24
28
32

w=4
Ctr
M

p

1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB
1MB

w=0
Ctr
M

p

w=5
Ctr
M

6.37 35.51 1MB
6.18 37.42 1MB
5.96 39.31 1MB
5.77 41.21 1MB
5.59 43.12 1MB
5.38 45.01 1MB
4.85 46.75 1MB
4.68 48.67 1MB
4.54 50.6 1MB

p

w=1
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

5.8 35.23 1MB 5.5 35.08 1MB
5.71 37.18 1MB 5.45 37.05 1MB
5.6 39.12 1MB 5.39 39.02 1MB
5.49 41.07 1MB 5.34 40.99 1MB
5.39 43.02 1MB 5.28 42.97 1MB
5.25 44.95 1MB 5.18 44.92 1MB
4.77 46.71 1MB 4.73 46.69 1MB
4.62 48.64 1MB 4.58 48.62 1MB
4.54 50.6 1MB 4.54 50.6 1MB

p

w=2
Ctr M

p

w=3
Ctr M

20.16 42.4 79MB 14.62 39.64 2MB 9.38 37.02 1MB 6.46 35.56 1MB
17.56 43.1 13MB 12.63 40.64 1MB 8.26 38.45 1MB 5.93 37.29 1MB
15.09 43.87 3MB 10.75 41.7 1MB 7.2 39.92 1MB 5.41 39.03 1MB
12.73 44.69 1MB 9.06 42.86 1MB 6.3 41.47 1MB 4.96 40.81 1MB
10.51 45.58 1MB 7.57 44.11 1MB 5.53 43.09 1MB 4.57 42.61 1MB
8.39 46.52 1MB 6.2 45.43 1MB 4.83 44.74 1MB 4.2 44.42 1MB
6.53 47.59 1MB 5.05 46.85 1MB 4.12 46.39 1MB 3.63 46.14 1MB
4.77 48.71 1MB 4.05 48.35 1MB 3.61 48.13 1MB 3.4 48.02 1MB
3.14 49.9 1MB 3.14 49.9 1MB 3.14 49.9 1MB 3.14 49.9 1MB

r=9
k

p

w=4
Ctr
M

0
4
8
12
16
20
24
28
32

4.95 34.8 1MB
4.73 36.69 1MB
4.49 38.57 1MB
4.28 40.47 1MB
4.09 42.37 1MB
3.88 44.27 1MB
3.42 46.04 1MB
3.28 47.97 1MB
3.14 49.9 1MB

p

w=5
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

4.25 34.45 1MB 3.92 34.28 1MB 3.76 34.21 1MB
4.15 36.4 1MB 3.87 36.26 1MB 3.74 36.2 1MB
4.04 38.35 1MB 3.82 38.24 1MB 3.72 38.18 1MB
3.94 40.3 1MB 3.78 40.21 1MB 3.69 40.17 1MB
3.85 42.25 1MB 3.73 42.19 1MB 3.67 42.16 1MB
3.72 44.19 1MB 3.64 44.15 1MB 3.6 44.13 1MB
3.32 45.99 1MB 3.27 45.96 1MB 3.25 45.95 1MB
3.21 47.93 1MB 3.18 47.92 1MB 3.16 47.9 1MB
3.14 49.9 1MB 3.14 49.9 1MB 3.14 49.9 1MB57

r = 10
k
0
4
8
12
16
20
24
28
32
r = 10
k
0
4
8
12
16
20
24
28
32

r = 11
k
0
4
8
12
16
20
24
28
32
r = 11
k
0
4
8
12
16
20
24
28
32

p

w=0
Ctr
M

p

w=1
Ctr M

p

w=2
Ctr M

p

w=3
Ctr M

17.28 40.97 11MB 11.47 38.06 1MB 6.54 35.6 1MB 4.18 34.42 1MB
14.87 41.76 3MB 9.77 39.21 1MB 5.73 37.19 1MB 3.87 36.26 1MB
12.6 42.63 1MB 8.18 40.42 1MB 4.97 38.81 1MB 3.56 38.11 1MB
10.45 43.55 1MB 6.79 41.72 1MB 4.34 40.49 1MB 3.3 39.97 1MB
8.45 44.55 1MB 5.57 43.11 1MB 3.8 42.22 1MB 3.06 41.86 1MB
6.56 45.61 1MB 4.48 44.56 1MB 3.31 43.98 1MB 2.83 43.74 1MB
4.92 46.79 1MB 3.53 46.09 1MB 2.78 45.71 1MB 2.42 45.53 1MB
3.44 48.04 1MB 2.78 47.72 1MB 2.44 47.54 1MB 2.28 47.47 1MB
2.13 49.39 1MB 2.13 49.39 1MB 2.13 49.39 1MB 2.13 49.39 1MB
p

w=4
Ctr
M

3.17 33.91 1MB
3.06 35.85 1MB
2.94 37.8 1MB
2.83 39.74 1MB
2.73 41.69 1MB
2.61 43.63 1MB
2.28 45.47 1MB
2.2 47.43 1MB
2.13 49.39 1MB

p

w=0
Ctr M

p

w=5
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

2.77 33.71 1MB 2.6 33.62 1MB 2.53 33.59 1MB
2.72 35.69 1MB 2.58 35.62 1MB 2.52 35.59 1MB
2.68 37.66 1MB 2.56 37.61 1MB 2.51 37.58 1MB
2.63 39.64 1MB 2.54 39.6 1MB 2.5 39.58 1MB
2.59 41.62 1MB 2.52 41.59 1MB 2.49 41.57 1MB
2.51 43.58 1MB 2.47 43.56 1MB 2.45 43.55 1MB
2.22 45.44 1MB 2.2 45.42 1MB 2.19 45.42 1MB
2.16 47.41 1MB 2.15 47.4 1MB 2.14 47.39 1MB
2.13 49.39 1MB 2.13 49.39 1MB 2.13 49.39 1MB

p

w=1
Ctr M

p

w=2
Ctr M

p

w=3
Ctr M

14.72 39.68 2MB 8.77 36.71 1MB 4.34 34.5 1MB 2.61 33.63 1MB
12.5 40.58 1MB 7.36 38. 1MB 3.8 36.23 1MB 2.45 35.55 1MB
10.43 41.54 1MB 6.06 39.36 1MB 3.3 37.98 1MB 2.29 37.47 1MB
8.49 42.57 1MB 4.94 40.8 1MB 2.89 39.77 1MB 2.15 39.4 1MB
6.7 43.68 1MB 3.98 42.32 1MB 2.54 41.59 1MB 2.02 41.34 1MB
5.06 44.86 1MB 3.15 43.9 1MB 2.22 43.44 1MB 1.89 43.27 1MB
3.64 46.15 1MB 2.42 45.54 1MB 1.86 45.25 1MB 1.63 45.14 1MB
2.44 47.54 1MB 1.91 47.28 1MB 1.66 47.16 1MB 1.56 47.11 1MB
1.49 49.07 1MB 1.49 49.07 1MB 1.49 49.07 1MB 1.49 49.07 1MB
p

w=4
Ctr M

p

w=5
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

2.02 33.33 1MB 1.82 33.24 1MB 1.75 33.2 1MB 1.73 33.19 1MB
1.97 35.31 1MB 1.81 35.23 1MB 1.75 35.2 1MB 1.72 35.19 1MB
1.92 37.29 1MB 1.79 37.22 1MB 1.74 37.2 1MB 1.72 37.19 1MB
1.87 39.26 1MB 1.77 39.21 1MB 1.73 39.19 1MB 1.72 39.19 1MB
1.83 41.24 1MB 1.75 41.2 1MB 1.73 41.19 1MB 1.72 41.18 1MB
1.76 43.21 1MB 1.71 43.18 1MB 1.7 43.17 1MB 1.69 43.17 1MB
1.55 45.1 1MB 1.52 45.09 1MB 1.52 45.08 1MB 1.51 45.08 1MB
1.52 47.09 1MB 1.5 47.08 1MB 1.49 47.07 1MB 1.49 47.07 1MB
1.49 49.07 1MB 1.49 49.07 1MB 1.49 49.07 1MB 1.49 49.07 1MB58

r = 12
k
0
4
8
12
16
20
24
28
32
r = 12
k
0
4
8
12
16
20
24
28
32

r = 13
k
0
4
8
12
16
20
24
28
32
r = 13
k
0
4
8
12
16
20
24
28
32

p

w=0
Ctr M

p

w=1
Ctr M

p

w=2
Ctr M

p

w=3
Ctr M

12.45 38.55 1MB 6.53 35.59 1MB 2.78 33.71 1MB 1.66 33.16 1MB
10.43 39.54 1MB 5.39 37.02 1MB 2.45 35.55 1MB 1.59 35.12 1MB
8.55 40.6 1MB 4.37 38.51 1MB 2.15 37.4 1MB 1.52 37.09 1MB
6.81 41.73 1MB 3.51 40.08 1MB 1.91 39.28 1MB 1.46 39.06 1MB
5.24 42.95 1MB 2.8 41.72 1MB 1.71 41.18 1MB 1.41 41.03 1MB
3.85 44.25 1MB 2.2 43.43 1MB 1.54 43.09 1MB 1.35 43. 1MB
2.66 45.66 1MB 1.69 45.17 1MB 1.32 44.98 1MB 1.2 44.93 1MB
1.75 47.2 1MB 1.37 47.01 1MB 1.23 46.94 1MB 1.18 46.92 1MB
1.15 48.9 1MB 1.15 48.9 1MB 1.15 48.9 1MB 1.15 48.9 1MB
p

w=4
Ctr M

p

w=5
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

1.38 33.02 1MB 1.3 32.98 1MB 1.28 32.97 1MB 1.28 32.96 1MB
1.36 35.01 1MB 1.3 34.98 1MB 1.28 34.97 1MB 1.28 34.96 1MB
1.35 37. 1MB 1.3 36.97 1MB 1.28 36.97 1MB 1.28 36.96 1MB
1.33 38.99 1MB 1.29 38.97 1MB 1.28 38.96 1MB 1.27 38.96 1MB
1.31 40.98 1MB 1.29 40.97 1MB 1.28 40.96 1MB 1.27 40.96 1MB
1.29 42.97 1MB 1.27 42.96 1MB 1.26 42.96 1MB 1.26 42.95 1MB
1.17 44.91 1MB 1.16 44.91 1MB 1.16 44.91 1MB 1.16 44.91 1MB
1.16 46.91 1MB 1.16 46.9 1MB 1.15 46.9 1MB 1.15 46.9 1MB
1.15 48.9 1MB 1.15 48.9 1MB 1.15 48.9 1MB 1.15 48.9 1MB

p

w=0
Ctr M

p

w=1
Ctr M

p

w=2
Ctr M

p

w=3
Ctr M

10.45 37.55 1MB 4.73 34.69 1MB 1.78 33.22 1MB 1.2 32.93 1MB
8.62 38.64 1MB 3.86 36.26 1MB 1.62 35.13 1MB 1.18 34.91 1MB
6.93 39.79 1MB 3.09 37.87 1MB 1.47 37.06 1MB 1.15 36.9 1MB
5.41 41.03 1MB 2.47 39.56 1MB 1.35 39. 1MB 1.13 38.89 1MB
4.06 42.35 1MB 1.98 41.31 1MB 1.26 40.95 1MB 1.12 40.88 1MB
2.91 43.78 1MB 1.59 43.12 1MB 1.18 42.92 1MB 1.1 42.87 1MB
1.96 45.31 1MB 1.27 44.96 1MB 1.08 44.87 1MB 1.04 44.85 1MB
1.33 46.99 1MB 1.11 46.88 1MB 1.05 46.85 1MB 1.03 46.84 1MB
1.03 48.84 1MB 1.03 48.84 1MB 1.03 48.84 1MB 1.03 48.84 1MB
p

w=4
Ctr M

p

w=5
Ctr M

p

w=6
Ctr M

p

w=7
Ctr M

1.1 32.88 1MB 1.08 32.87 1MB 1.08 32.86 1MB 1.08 32.86 1MB
1.1 34.87 1MB 1.08 34.87 1MB 1.08 34.86 1MB 1.08 34.86 1MB
1.09 36.87 1MB 1.08 36.87 1MB 1.08 36.86 1MB 1.08 36.86 1MB
1.09 38.87 1MB 1.08 38.87 1MB 1.08 38.86 1MB 1.08 38.86 1MB
1.09 40.87 1MB 1.08 40.86 1MB 1.08 40.86 1MB 1.08 40.86 1MB
1.08 42.86 1MB 1.07 42.86 1MB 1.07 42.86 1MB 1.07 42.86 1MB
1.03 44.84 1MB 1.03 44.84 1MB 1.03 44.84 1MB 1.03 44.84 1MB
1.03 46.84 1MB 1.03 46.84 1MB 1.03 46.84 1MB 1.03 46.84 1MB
1.03 48.84 1MB 1.03 48.84 1MB 1.03 48.84 1MB 1.03 48.84 1MB

59