Eindhoven University of Technology
Department of Mathematics and Computing Science

MASTER’S THESISOn Collisions for MD5
By

M.M.J. Stevens

Supervisor:
Prof. dr. ir. H.C.A. van Tilborg
Advisors:
Dr. B.M.M. de Weger
Drs. G. Schmitz

Eindhoven, June 2007

1

Acknowledgements
I would like to express my gratitude to some people who were involved in this project. First of all,
I owe thanks to Henk van Tilborg for being my overall supervisor and arranging this project andprevious projects. I would like to thank Benne de Weger, who was especially involved in my work,
for all his help, advice, comments, discussions, our joint work and his patience. The NBV deserve
thanks for facilitating this project and I would like to thank Gido Schmitz especially for being mysupervisor in the NBV. My gratitude goes out to Arjen Lenstra for comments, discussions, ourjoint work and my previous and future visits at EPFL. Thanks is due to Johan Lukkien for being
on my committee.
This work benefited greatly from suggestions by Xiaoyun Wang. I am grateful for comments
and assistance received from the anonymous Eurocrypt 2007 reviewers, Stuart Haber, Paul Hoffman, Pascal Junod, Vlastimil Klima, Bart Preneel, Eric Verheul, and Yiqun Lisa Yin. Furthermore, thanks go out to Jan Hoogma at LogicaCMG for technical discussions and sharing his
BOINC knowledge and Bas van der Linden at TU/e for allowing us to use the Elegast cluster.
Finally, thanks go out to hundreds of BOINC enthousiasts all over the world who donated an
impressive amount of cpu-cycles to the HashClash project.

2

CONTENTS

Contents
Acknowledgements

1

Contents

2

1 Introduction
1.1 Cryptographic hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Collisions for MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
4
5
6

2 Preliminaries

7

3 Definition of MD5
3.1 MD5 Message Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 MD5 compression function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

888

4 MD5 Collisions by Wang et al.
4.1 Differential analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Two Message Block Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Differential paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Sufficient conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Collision Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10
10
11
11
12
12

5 Collision Finding Improvements
5.1 Sufficient Conditions to control rotations . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Conditions on Qt for block 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2 Conditions on Qt for block 2 . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.3 Deriving Qt conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Conditions on the Initial Value for the attack . . . . . . . . . . . . . . . . . . . . .
5.3 Additional Differential Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Tunnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Example: Q9 -tunnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Notation for tunnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Collision Finding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14
14
15
17
18
18
19
20
20
21
22

6 Differential Path Construction Method
6.1 Bitconditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Differential path construction overview . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Extending partial differential paths . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Carry propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2 Boolean function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.3 Bitwise rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 Extending backward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Constructing full differential paths . . . . . . . . . . . . . . . . . . . . . . . . . . .

26
26
27
28
28
28
29
30
30

7 Chosen-Prefix Collisions
7.1 Near-collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Birthday Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Iteratively Reducing IHV -differences . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 Improved Birthday Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5 Colliding Certificates with Different Identities . . . . . . . . . . . . . . . . . . . . .
7.5.1 To-be-signed parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5.2 Chosen-Prefix Collision Construction . . . . . . . . . . . . . . . . . . . . . .

32
32
33
33
34
35
36
37

CONTENTS

7.6

7.7

7.5.3 Attack Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6.1 Colliding Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6.2 Misleading Integrity Checking . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6.3 Nostradamus Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Remarks on Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

38
38
38
39
39
40

8 Project HashClash using the BOINC framework

41

9 Conclusion

42

References

43

A MD5 Constants and Message Block Expansion

46

B Differential Paths for Two Block Collisions
B.1 Wang et al.’s Differential Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 Modified Sufficient Conditions for Wang’s Differential Paths . . . . . . . . . . . . .
B.3 New First Block Differential Path . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.4 New Second Block Differential Paths . . . . . . . . . . . . . . . . . . . . . . . . . .
B.4.1 New Second Block Differential Path nr. 1 . . . . . . . . . . . . . . . . . . .
B.4.2 New Second Block Differential Path nr. 2 . . . . . . . . . . . . . . . . . . .
B.4.3 New Second Block Differential Path nr. 3 . . . . . . . . . . . . . . . . . . .
B.4.4 New Second Block Differential Path nr. 4 . . . . . . . . . . . . . . . . . . .

48
48
50
52
54
54
56
58
60

C Boolean Function Bitconditions
C.1 Bitconditions applied to boolean function F . . . . . . . . . . . . . . . . . . . . . .
C.2 Bitconditions applied to boolean function G . . . . . . . . . . . . . . . . . . . . . .
C.3 Bitconditions applied to boolean function H . . . . . . . . . . . . . . . . . . . . . .
C.4 Bitconditions applied to boolean function I . . . . . . . . . . . . . . . . . . . . . .

62
62
63
64
65

D Chosen-Prefix Collision Example - Colliding Certificates
D.1 Chosen Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.2 Birthday attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3 Differential Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.1 Block 1 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.2 Block 2 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.3 Block 3 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.4 Block 4 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.5 Block 5 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.6 Block 6 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.7 Block 7 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.3.8 Block 8 of 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.4 RSA Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66
66
67
70
70
72
74
76
78
80
82
84
86

4

1 INTRODUCTION

1Introduction

This report is the result of my graduation project in completion of Applied Mathematics at theEindhoven University of Technology (TU/e). It has been written in order to obtain the degreeof Master of Science. The project has been carried out at the Nationaal Bureau Verbindingsbeveiliging (NBV), which is part of the Algemene Inlichtingen en Veiligheids Dienst (AIVD) in
Leidschendam.

1.1

Cryptographic hash functions

Hash functions are one-way functions with as input a string of arbitrary length (the message) andas output a fixed length string (the hash value). The hash value is a kind of signature for thatmessage. One-way functions work in one direction, meaning that it is easy to compute the hashvalue from a given message and hard to compute a message that hashes to a given hash value.
They are used in a wide variety of security applications such as authentication, commitments,
message integrity checking, digital certificates, digital signatures and pseudo-random generators.
The security of these applications depend on the cryptographic strength of the underlying hashfunction. Therefore some security properties are required to make a hash function H suitable forsuch cryptographic uses:
P1. Pre-image resistance: Given a hash value h it should be hard to find any message m suchthat h = H(m).
P2. Second pre-image resistance: Given a message m1 it should be hard to find another message
m2 6= m1 such that H(m1 ) = H(m2 ).
P3. Collision resistance: It should be hard to find different messages m1 , m2 such that H(m1 ) =H(m2 ).
A hash collision is a pair of different messages m1 6= m2 having the same hash value H(m1 ) =H(m2 ). Therefore second pre-image resistance and collision resistance are also known as weak andstrong collision resistance, respectively. Since the domain of a hash function is much larger (caneven be infinite) than its range, it follows from the pigeonhole principle that many collisions must
exist. A brute force attack can find a pre-image or second pre-image for a general hash function
with n-bit hashes in approximately 2n hash operations. Because of the birthday paradox a brute
force approach to generate collisions will succeed in approximately 2(n/2) hash operations. Any
attack that requires less hash operations than the brute force attack is formally considered a breakof a cryptographical hash function.
Nowadays there are two widely used hash functions: MD5[17] and SHA-1[16]. Both are iterative
hash functions based on the Merkle-Damgård[13, 1] construction and using a compression function.
The compression function requires two fixed size inputs, namely a k-bit message block and a n-bit
Intermediate Hash Value (internal state between message blocks denoted as IHV ), and outputs
the updated Intermediate Hash Value. In the Merkle-Damgård construction any message is firstpadded such that it has bitlength equal to a multiple of k and such that the last bits represent theoriginal message length. The hash function then starts with a fixed IHV called the initial value
and then updates IHV by applying the compression function with consecutive k-bit blocks, after
which the IHV is returned as the n-bit hash value.

1.2

Collisions for MD5

MD5 (Message Digest algorithm 5) was designed by Ronald Rivest in 1991 as a strengthened
version of MD4 with a hash size of 128 bits and a message block size of 512 bits. It is mainly
based on 32-bit integers with addition and bitwise operations such as XOR, OR, AND and bitwiserotation. As an Internet standard, MD5 has been deployed in a wide variety of security applications
and is also commonly used to check the integrity of files. In 1993, B. den Boer and A. Bosselaers[3]showed a weakness in MD5 by finding a ”pseudo collision” for MD5 consisting of the same message

1.3

Our Contributions

5

with different initial values. H. Dobbertin[4] published in 1996 a semi free-start collision which
consisted of two different 512-bit messages with a chosen initial value. This attack does notproduce collisions for the full MD5, however it reveals that in MD5, differences in the higher order
bits of the working state do not diffuse fast enough.
MD5 returns a hash value of 128 bits, which is small enough for a brute force birthday attackof order 264 . Such a brute force attack was attempted by the distributed computing project
MD5CRK which started in March 2004. However the project ended in August 2004 when Wanget al. [24] published their collisions for MD4, MD5, HAVAL-128 and RIPEMD, it is unknown
to us how far the project was at that time. Later, Xiaoyun Wang and Hongbo Yu presented in[25] the underlying method to construct collisions using differential paths, which are a precise
description how differences propagate through the MD5 compression function. However, they did
so after Hawkes et al. [6] described in great detail a derivation of all necessary bitconditions on
the working state of MD5 to satisfy the same differential paths.
The complexity of the original attack was estimated at 239 calls to the compression function of
MD5 and could be mounted in 15 minutes up to an hour on an IBM P690. Early improvements[26], [18], [12], [9] were able to find collisions in several hours on a single pc, the fastest being [9]which could find collisions for MD5 in about 233 compressions.
Several results were published on how to abuse such collisions in the real world. The first werebased only on the first published collision. In [7] it was shown how to achieve colliding archives,
from which different contents are extracted using a special program. Similarly, in [14] a method
was presented to construct two colliding files, both containing the same encrypted code, however
only one file allows the possibly malicious code to be decrypted and executed by a helper program.
More complex applications use Wang’s attack to find collisions starting and ending with somecontent, identical for both messages in the collision, specifically tailored to achieve a malicious
goal. The most illustrative application is given by Daum and Lucks in [2] where they construct
two colliding PostScript documents, each showing a different content. For other document formats,similar results can be achieved [5]. Also, the setting of digital certificates is not entirely safe as
Lenstra and de Weger[11] presented two colliding X.509 certificates with different public keys, butwith identical signatures from a Certificate Authority. Although as they contain the same identity
there is no realistic abuse scenario.

1.3

Our Contributions

The contributions of this thesis are split into three main topics: speeding up collision finding,constructing differential paths and chosen-prefix collisions.
First we will show several improvements to speed up Wang’s attack. All implementations of
Wang’s attack use bitconditions on the working state of MD5’s compression function to find amessage block which satisfies the differential path. We show how to find bitconditions on theworking state such that differences are correctly rotated in the execution of the compressionfunction, which was often neglected in collision finding algorithms and led to loss of efficiency.
Also, in an analysis we show that the value of the IHV at the beginning of the attack has an
impact on the complexity of collision finding. We give a recommendation to two bitconditions on
this IHV to prevent a worst case complexity. Furthermore, we presented in [21], together withthe above results, two new collision finding algorithms based on [9] which together allowed us tofind collisions in about 226.3 compressions for recommended IHV ’s. We were the first to present
a method to find collisions in the order of one minute on a single pc, rather than hours. Later,
Klima [10] gave another such method using a technique called Tunnels which was slightly faster,which we incorporated in our latest collision finding algorithm presented here. Currently, using
also part of our second main result discussed below, we are able to find collisions for MD5 in about
224.1 compressions for recommended IHV ’s which takes approx. 6 seconds on a 2.6Ghz Pentium4.
Parts of our paper [21] were used in a book on applied cryptanalysis [20].
Wang’s collision attack is based on two differential paths for the compression function which
are to be used for consecutive message blocks where the first introduces differences in the IHV andthe second eliminates these differences again. These two differential paths have been constructed6

1 INTRODUCTION

by hand using great skill and intuition. However, an often posed question was how to constructdifferential paths in an automated way. In this thesis we present the first method to constructdifferential paths for the compression function of MD5. To show the practicality of our method
we have constructed several new differential paths which can be found in the Appendix. Five of
these differential paths were used to speedup Wang’s attack as mentioned before. Our method
even allows one to optimize the efficiency of the found differential paths for collision finding.
Our third contribution is the joint work with Arjen Lenstra and Benne de Weger in which we
present a new collision attack on MD5, namely chosen-prefix collisions. A chosen-prefix collisionconsists of two arbitrarily chosen prefixes M and M 0 for which we can construct using our method
two suffixes S and S 0 , such that M extended with S and M 0 extended with S 0 collide under MD5:
M D5(M kS) = M D5(M 0 kS 0 ). Such chosen-prefix collisions allow more advanced abuse scenarios
than the collisions based on Wang’s attack. Using our method we have constructed an example
consisting of two colliding X.509 certificates which (unlike in [11]) have different identities, but still
receive the same signature from a Certification Authority. Although there is no realistic attack
using our colliding certificates, this does constitute a breach of PKI principles. We discuss several
other applications of chosen-prefix collisions which might be more realistic. This joint work [22]was accepted at EuroCrypt 2007 and has been chosen by the program committee to be one of thethree notable papers which were invited to submit their work to the Journal of Cryptology.

1.4

Overview

In the following sections 2 and 3 we will fix some notation and give a definition of MD5 which weshall use throughout this thesis. Then we will describe the original attack on MD5 of Wang et al.
in section 4. Our several improvements to speed up Wang’s attack are presented in section 5. In
section 6 we will discuss our method to construct differential paths for the compression functionof MD5. Our joint work with Arjen Lenstra and Benne de Weger on chosen-prefix collisions andcolliding certificates with different identities is presented in section 7. In section 8, we describe
our use of the distributed computing framework BOINC in our project HashClash. Finally, we
make some concluding remarks in section 9.

2 Preliminaries

2

7

Preliminaries

MD5 operates on 32-bit unsigned integers called words, where we will number the bits from 0(least significant bit) up to 31 (most significant bit). We use the following notation:• Integers are denoted in hexadecimal together with a subscript 16, e.g. 12ef16 ,and in binary together with a subscript 2, e.g. 00010010111011112 ,where the most significant digit is placed left;• For words X and Y , addition X + Y and substraction X − Y are implicitly modulo 232 ;• X[i] is the i-th bit of the word X;• The cyclic left and right rotation of the word X by n bitpositions are denoted as RL(X, n)
and RR(X, n), respectively:
RL(111100001111001001111010100111002 , 5)
= 000111100100111101010011100111102= RR(111100001111001001111010100111002 , 27);
• X ∧ Y is the bitwise AND of words X,Y or bits X,Y ;• X ∨ Y is the bitwise OR of words X,Y or bits X,Y ;• X ⊕ Y is the bitwise XOR of words X,Y or bits X,Y ;• X is the bitwise complement of the word or bit X;
A binary signed digit representation (BSDR) of a word X is a sequence Y = (ki )31
i=0 , often simply
denoted as Y = (ki ), of 32 digits ki ∈ {−1, 0, +1} for 0 ≤ i ≤ 31, where
X≡

31
X

ki 2i

mod 232 ,e.g. fc00f00016 ≡ (−1 · 212 ) + (+1 · 216 ) + (−1 · 226 ).

i=0

Since there are 332 possible BSDR’s and only 232 possible words, many BSDR’s may exist for any
given word X. For convenience, we will write BSDR’s as a (unordered) sum of positive or negative
powers of 2, instead of as a sequence, e.g. −212 + 216 − 226 . This should not cause confusion, since
it will always be clear from the context whether such a sum is a BSDR or a word.
The weight w(Y ) of a BSDR Y = (ki ) is defined as the number of non-zero ki ’s:w(Y ) =

31
X

|ki |,

Y = (ki );i=0

We use the following notation for BSDR’s:• Y ≡ X for a BSDR Y of the word X;• Y ≡ Y 0 for two BSDR’s Y and Y 0 of the same word;• Y JiK is the i-th signed bit of a BSDR Y ;• Cyclic left and right rotation by n positions of a BSDR Y is denoted as RL(Y, n) and
RR(Y, n), respectively:
RL(−231 + 222 − 210 + 20 , 5) = −24 + 227 − 215 + 25 .
A particularly useful BSDR of a word X which always exists is the Non-Adjacent Form (NAF),
where no two non-zero ki ’s are adjacent. The NAF is not unique since we work modulo 232 (making
k31 = −1 equivalent to k31 = +1), however we will enforce uniqueness of the NAF by choosing
k31 ∈ {0, +1}. Among the BSDRs of a word, the NAF has minimal weight (see e.g. [15]).

8

3 DEFINITION OF MD5

3

Definition of MD5

A sequence of bits will be interpreted in a natural manner as a sequence of bytes, where every groupof 8 consecutive bits is considered as one byte, with the leftmost bit being the most significant bit.
E.g. 01010011 11110000 = 010100112 111100002 = 5316 f016
However, MD5 works on bytes using Little Endian, which means that in a sequence of bytes, thefirst byte is the least significant byte. E.g. when combining 4 bytes into a word, the sequence ef16 ,cd16 , ab16 , 8916 will result in the word 89abcdef16 .

3.1

MD5 Message Preprocessing

MD5 can be split up into these parts:
1. Padding:
Pad the message with: first the ‘1’-bit, next as many ‘0’ bits until the resulting bitlength
equals 448 mod 512, and finally the bitlength of the original message as a 64-bit little-endian
integer. The total bitlength of the padded message is 512N for a positive integer N .
2. Partitioning:
The padded message is partitioned into N consecutive 512-bit blocks M1 , M2 , . . . , MN .
3. Processing:MD5 goes through N + 1 states IHVi , for 0 ≤ i ≤ N , called the intermediate hash values.
Each intermediate hash value IHVi consists of four 32-bit words ai , bi , ci , di . For i = 0 these
are initialized to fixed public values:
IHV0 = (a0 , b0 , c0 , d0 ) = (6745230116 , EFCDAB8916 , 98BADCFE16 , 1032547616 ),and for i = 1, 2, . . . N intermediate hash value IHVi is computed using the MD5 compressionfunction 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 sequence of bytes, each usually shown in 2 digit hexadecimal representation,
given by the four words aN , bN , cN , dN using Little-Endian. E.g. in this manner IHV0 will
be expressed as the hexadecimal string
0123456789ABCDEFFEDCBA9876543210

3.2

MD5 compression function

The input for the compression function MD5Compress(IHV, B) is an intermediate hash value
IHV = (a, b, c, d) and a 512-bit message block B. There are 64 steps (numbered 0 up to 63), split
into four consecutive rounds of 16 steps each. Each step uses a modular addition, a left rotation,
and a non-linear function. Depending on the step t, an Addition Constant ACt and a Rotation
Constant RCt are defined as follows, where we refer to Table A-1 for an overview of these values:
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.

3.2

MD5 compression function

9

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.
The message block B is partitioned into sixteen consecutive 32-bit words m0 , m1 , . . . , m15 (using
Little Endian byte ordering), and expanded to 64 words (Wt )63
t=0 for each step using the following
relations, see Table A-1 for an overview:
mt
for 0 ≤ t < 16,m
for 16 ≤ t < 32,(1+5t) mod 16
Wt =
mfor 32 ≤ t < 48,(5+3t) mod 16
m(7t) mod 16
for 48 ≤ t < 64.
We follow the description of the MD5 compression function from [6] because its ‘unrolling’ of
the cyclic state facilitates the analysis. For t = 0, 1, . . . , 63, the compression function algorithm
maintains a working register with 4 state words Qt , Qt−1 , Qt−2 and Qt−3 . These are initializedas (Q0 , Q−1 , Q−2 , Q−3 ) = (b, c, d, a) and, for t = 0, 1, . . . , 63 in succession, updated as follows:
Ft
Tt
Rt
Qt+1

=
=
=
=

ft (Qt , Qt−1 , Qt−2 ),Ft + Qt−3 + ACt + Wt ,RL(Tt , RCt ),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 ).

10

4 MD5 COLLISIONS BY WANG ET AL.

4

MD5 Collisions by Wang et al.

X. Wang and H. Yu [25] revealed in 2005 their new powerful attack on MD5 which allowed themto find the collisions presented in 2004 [24] efficiently. A collision of MD5 consists of two messages
and we will use the convention that, for an (intermediate) variable X associated with the firstmessage of a collision, the related variable which is associated with the second message will bedenoted by X 0 .
Their attack is based on a combined additive and XOR differential method. Using this differential they have constructed 2 differential paths for the compression function of MD5 which
are to be used consecutively to generate a collision of MD5 itself. Their constructed differential
paths describe precisely how differences between the two pairs (IHV, B) and (IHV 0 , B 0 ), of anintermediate hash value and an accompanying message block, propagate through the compressionfunction. They describe the integer difference (−1, 0 or +1) in every bit of the intermediateworking states Qt and even specific values for some bits.
Using a collision finding algorithm they search for a collision consisting of two consecutive
pairs of blocks (B0 , B00 ) and (B1 , B10 ), satisfying the 2 differential paths which starts from arbitrary
ˆ = IHVˆ 0 . Therefore the attack can be used to create two messages M and M 0 with the same
IHVhash that only differ slightly in two subsequent blocks as shown in the following outline whereˆ = IHVk for some k:
IHV
IHV0

→

M1

···

→

Mk

=
IHV0

→

M1

···

→

Mk

IHVk

→

B0

IHVk+1→

B1

IHVk+2

=

6=

=

IHVk

0
IHVk+10
IHVk+2

→

B00

→

B01

→

Mk+3

···

→

MN

IHVN
=

→

Mk+3

···

→

MN

IHVN

We will use this outline throughout this work with respect to this type of collisions. Note thatall blocks Mi = Mi0 can be chosen arbitrarily and that only B0 , B00 , B1 , B10 are generated by thecollision finding algorithm.
This property was used in [11] to create two X.509 certificates where the blocks B0 , B00 , B1 , B10
are embedded in different public keys. In [2] it was shown how to create two PostScript files withthe same hash which showed two different but arbitrary contents.
The original attack finds MD5 collisions in about 15 minutes up to an hour on a IBM P690 witha cost of about 239 compressions. Since then many improvements were made [18, 12, 26, 9, 21, 10].
Currently collisions for MD5 based on these differential paths can be found in several seconds ona single powerful pc using techniques based on tunnels [10], controlling rotations in the first round[21] and additional differential paths which we will present here.

4.1

Differential analysis

In [25] a combination of both integer modular substraction and XOR is used as differences, since
the combination of both kinds of differences gives more information than each by themselves.
So instead of only the integer modular difference between two related words X and X 0 , thiscombination gives the integer differences (−1, 0 or +1) between each pair of bits X[i] and X 0 [i]for 0 ≤ i ≤ 31. We will denote this difference as ∆X and represent it in a natural manner using
BSDR’s as follows∆X = (ki ), ki = X 0 [i] − X[i] for 0 ≤ i ≤ 31.
We will denote the regular modular difference as the word δX = X 0 − X and clearly δX ≡ ∆X.
As an example, suppose the integer modular difference is δX = X 0 − X = 26 , then more than
one XOR difference is possible:• A one-bit difference in bit 6 (X 0 ⊕ X = 0000004016 ) which means that X 0 [6] = 1, X[6] = 0
and ∆X = +26 .
• Two-bit difference in bits 6 and 7 caused by a carry. This happens when X 0 [6] = 0, X[6] = 1,
X 0 [7] = 1 and X[7] = 0. Now ∆X = −26 + 27 .

4.2

Two Message Block Collision11• n-bit difference in bits 6 up to 6 + n − 1 caused by n − 1 carries. This happens when X 0 [i] = 0
and X[i] = 1 for i = 6, . . . , 6 + n − 2 and X 0 [6 + n − 1] = 1 and X[6 + n − 1] = 0. In thiscase ∆X = −26 − 27 · · · − 26+n−2 + 26+n−1 .
• A 26-bit difference in bits 6 up to 31 caused by 26 carries (instead of 25 as in the previouscase). This happens when X 0 [i] = 0 and X[i] = 1 for i = 6, . . . , 31.
We extend the notation of δX and ∆X for a word X to any tuple of words coordinatewise.
E.g. ∆IHV = (∆a, ∆b, ∆c, ∆d) and δB = (δmi )15
i=0 .

4.2

Two Message Block Collision

Wang’s attack consists of two differential paths for two subsequent message blocks, which we willrefer to as the first and second differential path. Although B0 and B1 are not necessarily the thefirst blocks of the messages M and M 0 , we will refer to B0 and B1 as the first and second block,respectively. The first differential path starts with any given IHVk = IHVk0 and introduces a0difference between IHVk+1 and IHVk+1
which will be canceled again by the second differentialpath:δIHVk+1 = (δa, δb, δc, δd) = (231 , 231 + 225 , 231 + 225 , 231 + 225 ).
The first differential path is based on the following differences in the message block:δm4 = 231 ,δm11 = 215 ,δm14 = 231 ,δmi = 0, i 6∈ {4, 11, 14}

The second differential path is based on the negated message block differences:δm4 = −231 ,δm11 = −215 ,δm14 = −231 ,δmi = 0, i 6∈ {4, 11, 14}Note that −231 = 231 in words, so in fact δm4 and δm14 are not changed by the negation.
These are very specific message block differences and were selected to ensure a low complexity
for the collision finding algorithm as will be shown later.

4.3

Differential paths

The differential paths for both blocks (Tables B-1, B-2, see the Appendix) were constructed
specifically to create a collision in this manner. The differential paths describe precisely for eachof the 64 steps of MD5 what the differences are in the working state and how these differencespass through the boolean function and the rotation. More precisely, a differential path is defined64
64
through the sequences (δmt )15
t=0 , (∆Qt )t=−3 and (δTt )t=0 of differences.
The first differential path starts without differences in the IHV , however differences will be
introduced in step t = 4 by δm4 . The second differential path starts with the given δIHVk+1 . In
both, all differences in the working state will be canceled at step t = 25 by δm14 . And from stept = 34 both paths use the same differential steps, although with opposite signs. This structure
can easily be seen in the Tables B-1 and B-2.
Below we show a fraction of the first differential path:
t
13

∆Qt
24

−2

25

+2

δFt
31

+2

31

δwt

δTt

13

31

−

12

−2

18

31

31

18

−2 +2

RCt
30

12

14

+2

2 +2

2

2 −2

17

15

+23 − 213 + 231

225 +231−−27 −213 +2252216−229 + 231

231

−

224

5

31

31

17

+2

2

−

−

9

18

+231

231

215

23

14

19

+217 + 231

231

−

−229

20

12

4 MD5 COLLISIONS BY WANG ET AL.

The two differential paths were made by hand with great skill and intuition. It has been an
open question for some time how to construct differential paths methodically. In section 6 wewill present the first method to construct differential paths for MD5. Using our method we haveconstructed several differential paths for MD5. We use 5 differential paths in section 5 to speedup
the attack by Wang et al. and 8 others were used in section 7 for a new collision attack on MD5.

4.4

Sufficient conditions

Wang et al. use sufficient conditions (modified versions are shown in Tables B-3,B-4) to efficiently
search for message blocks for which these differential paths hold. These sufficient conditions
guaranteed that the necessary carries and correct boolean function differences happen. Eachcondition gives the value of a bit Qt [i] of the working state either directly or indirectly as shownin Table 4-1. Later on we will generalize and extend these conditions to also include the value ofthe related bit Q0t [i].
Table 4-1: Sufficient bitconditions.
Symbol condition on Qt [i] direct/indirect.
none
direct0
Qt [i] = 0
direct1
Qt [i] = 1
direct^Qt [i] = Qt−1 [i]indirect!
Qt [i] = Qt−1 [i]indirect
These conditions are only to find a block B on which the message differences will be applied
to find B 0 and should guarantee that the differential path happens. They can be derived for any
differential path and there can be many different possible sets of sufficient conditions.
However, it should be noted that their sufficient conditions are not sufficient at all, as they
do not guarantee that in each step the differences are rotated correctly. In fact as we will show
later on, one does not want sufficient conditions for the full differential path as this increases thecollision finding complexity significantly. On the other hand, sufficient conditions over the firstround and necessary conditions for the other rounds will decrease the complexity. This can beseen as in the first round one can still choose the working state and one explicitly needs to verify
the rotations, whereas in the other rounds the working state is calculated and verification can bedone on the fly.

4.5

Collision Finding

Using these sufficient conditions one can efficiently search for a block B. Basically one can choose arandom block B that meets all the sufficient conditions in the first round. The remaining sufficientconditions have to be fulfilled probabilistically and directly result in the complexity of this collisionfinding algorithm. Wang et al. used several improvements over this basic algorithm:
1. Early abortion:
Abort at the step where the first sufficient condition fails.
2. Multi-Message Modification:
When a certain condition in the second round fails, one can use multi-message modification.
This is a substitution formula specially made for this condition on the message block B,
such that after the substitution that condition will now hold without interfering with otherprevious conditions.
An example of multi-message modification is the following. When searching a block for the firstdifferential path using Table B-3, suppose Q17 [31] = 1 instead of 0. This can be corrected bymodifying m1 , m2 , m3 , m4 , m5 as follows:4.5

Collision Finding

13

c2 .
1. Substitute m
c1 ← (m1 + 226 ), this results in a different Q
c2 , 17) − Q−1 − F (Qc2 , Q1 , Q0 ) − AC2 ).
2. Substitute m
c2 ← (RR(Q3 − Q
c2 , Q1 ) − AC3 ).
3. Substitute m
c3 ← (RR(Q4 − Q3 , 22) − Q0 − F (Q3 , Q
c2 ) − AC4 ).
4. Substitute m
c4 ← (RR(Q5 − Q4 , 7) − Q1 − F (Q4 , Q3 , Q
c2 − F (Q5 , Q4 , Q3 ) − AC5 ).
5. Substitute m
c5 ← (RR(Q6 − Q5 , 12) − QdThe first line is the most important, here m1 is changed such that Q
17 [31] = 0, assuming Q13 up
26
to Q16 remain unaltered. The added difference +2 in m1 results in an added difference of +231
din Q17 [31], hence Q
17 [31] = 0. The four other lines simply change m2 , m3 , m4 , m5 such that Q3 up
to Q16 remain unaltered by the change in m1 . Since there are no conditions on Q2 , all previous
conditions are left intact.
Wang et al. constructed several of such multi-message modifications which for larger t become
more complex. Klima presented in [9] two collision finding algorithms, one for each block, which
are much easier and more efficient than these multi-message modifications. Furthermore, Klima’s
algorithms work for arbitrary differential paths, while multi-message modifications have to be
derived specifically for each differential path.

14

5

5 COLLISION FINDING IMPROVEMENTS

Collision Finding Improvements

In [6] a thorough analysis of the collisions presented by Wang et al. is presented. Not only a setof ‘sufficient’ conditions on Qt , similarly as those presented in [25], is derived but also a set ofnecessary restrictions on Tt for the differential to be realized. These restrictions are necessary tocorrectly rotate the add-difference δTt to δRt . Collision finding can be done more efficiently byalso satisfying the necessary restrictions on Tt used in combination with early abortion.
Fast collision finding algorithms as presented in [9] can choose message blocks B which satisfy
the conditions for Q1 , . . . , Q16 . As one can simply choose values of Q1 , . . . , Q16 fulfilling conditions
and then calculate mt for t = 0, . . . , 15 using
mt = RR(Qt+1 − Qt , RCt ) − ft (Qt , Qt−1 , Qt−2 ) − Qt−3 − ACt .
Message modification techniques are used to change a block B such that Q1 , . . . , Q16 are changedslightly maintaining their conditions and that Q17 up to some Qk do not change at all. Naturally,
we want k to be as large as possible.
Although conditions for Q1 , . . . , Q16 can easily be fulfilled, this does not hold for the restrictions
on Tt which still have to be fulfilled probabilistically. Our first collision finding improvement we
present here is a technique to satisfy those restrictions on Tt using conditions on Qt which can besatisfied when choosing a message block B.
The first block has to fulfill conditions of its differential path, however there are also conditions
due to the start of the differential path of the second block. Although not immediately clear, thelatter conditions have a probability to be fulfilled that depends on IHVk , the intermediate hashvalue used to compress the first block. We will show this dependency and present two conditions
that prevent a worst-case probability. The need for these two conditions can also be relieved with
our following result.
Another improvement is the use of additional differential paths we have constructed using thetechniques we will present in section 6. We present one differential path for the first block and4 additional differential paths for the second block. The use of these will relax some conditions
imposed on the first block due to the start of the differential path for the second block. As eachof the now five differential paths for the second block has different conditions imposed on the first
block, only one of those has to be satisfied to continue with the second block.
We were the first to present in [21] a collision finding algorithm which was able to find collisions
for MD5 in the order of minutes on a single pc, based on Klima’s algorithm in [9]. Shortly after,
Klima presented in [10] a new algorithm which was slightly faster than ours using a techniquecalled tunneling. We will explain this tunneling technique and present an improved version of ouralgorithm in [21] using this technique. These improvements in collision finding were crucial to
our chosen-prefix construction, as the differential paths for chosen-prefix collisions usually havesignificantly more conditions than Wang’s differential paths. Hence, the complexity to find collision
blocks satisfying these differential paths is significantly higher (about 242 vs. 224.1 compressions).
Currently using these three improvements we are able to find collisions for MD5 in several
seconds on a single pc (approx. 6 seconds on a 2.6Ghz Pentium4 pc). Source code and a windows
executable can be downloaded from http://www.win.tue.nl/hashclash/.

5.1

Sufficient Conditions to control rotations

The first technique presented here allows to fulfill the restrictions on Tt by using extra conditions
on Qt+1 and Qt such as those in Table 4-1. By using the relation Qt+1 − Qt = Rt = RL(Tt , RCt )we can control specific bits in Tt . In our analysis of Wang’s differential paths, we searched for those
restrictions on Tt with a significant probability that they are not fulfilled. For each such restriction
on Tt , for t = 0, . . . , 19, we have found bitconditions on Qt+1 and Qt which were sufficient for the
restriction to hold. For higher steps it is more efficient to directly verify the restriction instead ofusing conditions on Qt .
All these restrictions can be found in [6] with a description why they are necessary for thedifferential path. The resulting conditions together with the original conditions can be found in5.1

Sufficient Conditions to control rotations

15

Table B-3. Below we will show the original set of sufficient conditions in [25] in black and ouradded conditions will be underlined and in blue.
5.1.1

Conditions on Qt for block 1

1. Restriction: ∆T4 = −231 .
This restriction is necessary to guarantee that δR4 = −26 instead of +26 . The condition
T4 [31] = 1 is necessary and sufficient for ∆T4 = −231 to happen. Bit 31 of T4 is equal to
bit 6 of R4 , since T4 is equal to RR(R4 , 7). By adding the conditions Q4 [4] = Q4 [5] = 1
and Q5 [4] = 0 to the conditions Q4 [6] = Q5 [6] = 0 and Q5 [5] = 1, it is guaranteed thatR4 [6] = T4 [31] = 1. Satisfying other Qt conditions, this also implies that Q6 [4] = Q5 [4] = 0.
Q5 [6 − 4]Q4 [6 − 4]R4 [6 − 4]010 · · ·011 · · ·11. · · ·−=This table shows the bits 4,5 and 6 of the words Q5 , Q4 and R4 with the most significant bit
placed left, this is notated by Q5 [6 − 4] extending the default notation for a single bit Q5 [6].
2. Restriction: add-difference −214 in δT6 must propagate to at least bit 15 on T6 .
This restriction implies that T6 [14] must be zero to force a carry. Since T6 [14] = R6 [31], thecondition T6 [14] = 0 is guaranteed by the added conditions Q6 [30 − 28, 26] = 0. This also
implies that Q5 [30 − 28, 26] = 0 because of other conditions on Qt .
Q7 [31 − 23]
Q6 [31 − 23]
R6 [31 − 23]000000111 · · ·0000001.0 · · ·0000000.. · · ·−=Note: in [26] these conditions were also found by statistical means.
3. Restriction: add-difference +213 in δT10 must not propagate past bit 14 on T10 .
The restriction is satisfied by the condition T10 [13] = R10 [30] = 0. The conditions Q11 [29 −28] = Q10 [29] = 0 and Q10 [28] = 1 are sufficient.
Q11 [31 − 28]
Q10 [31 − 28]
R10 [31 − 28]

0010 · · ·0111 · · ·101. · · ·−=4. Restriction: add-difference −28 in δT11 must not propagate past bit 9 on T11 .
This restriction can be satisfied by the condition T11 [8] = R11 [30] = 1. With the above
added condition Q11 [29] = 1 we only need the extra condition Q12 [29] = 0.
Q12 [31 − 29]
Q11 [31 − 29]
R11 [31 − 29]000 · · ·001 · · ·11. · · ·−=5. Restriction: add-difference −230 in δT14 must not propagate past bit 31 on T14 .
For T14 the add difference −230 must not propagate past bit 31, this is satisfied by either
T14 [30] = R14 [15] = 1 or T14 [31] = R14 [16] = 1. This always happens when Q15 [16] = 0 andcan be shown for the case if no carry from the lower order bits happens as well as the case
if a negative carry does happen. A positive carry is not possible since we are subtracting.
no carryQ15 [16 − 15]
01 · · ·Q14 [16 − 15]
11 · · ·R14 [16 − 15]
10 · · ·−=negative carry from lower bits
Q15 [16 − 15]
01 · · ·Q14 [16 − 15]
11 · · · −R14 [16 − 15]
01 · · · =165 COLLISION FINDING IMPROVEMENTS

6. Restriction: add-difference −27 in δT15 must not propagate past bit 9 on T15 .
This can be satisfied by the added condition Q16 [30] = Q15 [30]. Since then either T15 [7] =R15 [29] = 1, T15 [8] = 1 or T15 [9] = 1 holds. This can be shown if we distinguish between
Q15 [30] = 0 and Q15 [30] = 1 and also distinguish whether or not a negative carry from thelower order bits happens.
no carry
001 · · ·Q16 [31 − 29]
Q15 [31 − 29]
011 · · ·R15 [31 − 29]
110 · · ·no carryQ16 [31 − 29]
011 · · ·Q15 [31 − 29]
001 · · ·R15 [31 − 29]
010 · · ·−=negative carry from lower bits
001 · · ·Q16 [31 − 29]
Q15 [31 − 29]
011 · · · −R15 [31 − 29]
101 · · · =−=negative carry from lower bits
Q16 [31 − 29]
011 · · ·Q15 [31 − 29]
001 · · · −R15 [31 − 29]
001 · · · =7. Restriction: add-difference +225 in δT15 must not propagate past bit 31 on T15 .
This is satisfied by the added condition Q16 [17] = Q15 [17]. Since then either T15 [25] =R15 [15] = 0, T15 [26] = 0 or T15 [27] = 0 holds. We compactly describe all cases by mentioning
which values were assumed for each result:Q16 [17 − 15]
Q15 [17 − 15]
R15 [17 − 15]

no carry!.. · · ·.01 · · · −
011 · · · =100 · · ·101 · · ·110 · · ·(Q16 [17 − 15] = .00)
(Q16 [17 − 15] = .01)
(Q16 [17 − 15] = .10)
(Q16 [17 − 15] = .11)

negative carry from lower bits
Q16 [17 − 15]!.. · · ·Q15 [17 − 15].01 · · · −R15 [17 − 15]010 · · · =(Q16 [17 − 15] = .00)
011 · · ·(Q16 [17 − 15] = .01)
100 · · ·(Q16 [17 − 15] = .10)
101 · · ·(Q16 [17 − 15] = .11)
8. Restriction: add-difference +224 in δT16 must not propagate past bit 26 on T16 .
This can be achieved with the added condition Q17 [30] = Q16 [30], since then always either
T16 [24] = R16 [29] = 0 or T16 [25] = R16 [30] = 0.

Q17 [30 − 29]
Q16 [30 − 29]
R16 [30 − 29]

no carry!. · · ·.1 · · · −01 · · · =10 · · ·01 · · ·10 · · ·(Q17 [30 − 29] = 00)(Q17 [30 − 29] = 01)(Q17 [30 − 29] = 10)(Q17 [30 − 29] = 11)

negative carry from lower bits
Q17 [30 − 29]!. · · ·Q16 [30 − 29].1 · · · −R16 [30 − 29]
00 · · · =(Q17 [30 − 29] = 00)
01 · · ·(Q17 [30 − 29] = 01)
00 · · ·(Q17 [30 − 29] = 10)
01 · · ·(Q17 [30 − 29] = 11)

5.1

Sufficient Conditions to control rotations

17

9. Restriction: add-difference −229 in δT19 must not propagate past bit 31 on T19 .
This can be achieved with the added condition Q20 [18] = Q19 [18], since then always either
T19 [29] = 1 or T19 [30] = 1.

Q20 [18 − 17]
Q19 [18 − 17]
R19 [18 − 17]

no carry!. · · ·.0 · · · −10 · · · =11 · · ·10 · · ·11 · · ·(Q20 [18 − 17] = 00)(Q20 [18 − 17] = 01)(Q20 [18 − 17] = 10)(Q20 [18 − 17] = 11)

negative carry from lower bits
Q20 [18 − 17]!. · · ·Q19 [18 − 17].0 · · · −R19 [18 − 17]
01 · · · =(Q20 [18 − 17] = 00)
10 · · ·(Q20 [18 − 17] = 01)
01 · · ·(Q20 [18 − 17] = 10)
10 · · ·(Q20 [18 − 17] = 11)
10. Restriction: add-difference +217 in δT22 must not propagate past bit 17 on T22 .
It is possible to satisfy this restriction with two Qt conditions. However T22 will always be
calculated in the algorithm we used, therefore it is better to verify directly that T22 [17] = 0.
This restriction holds for both block 1 and 2.
11. Restriction: add-difference +215 in δT34 must not propagate past bit 15 on T34 .
This restriction also holds for both block 1 and 2 and it should be verified with T34 [15] = 0.
5.1.2

Conditions on Qt for block 2

Using the same technique as in the previous subsection we found 17 Qt -conditions satisfying 12
Tt restrictions for block 2. An overview of all conditions for block 2 is included in Table B-4.
1. Restriction: ∆T2 J31K = +1.
Conditions: Q1 [16] = Q2 [16] = Q3 [15] = 0 and Q2 [15] = 1.
2. Restriction: ∆T6 J31K = +1.
Conditions: Q6 [14] = 1 and Q7 [14] = 0.
3. Restriction: ∆T8 J31K = +1.
Conditions: Q8 [5] = 1 and Q9 [5] = 0.
4. Restriction: add-difference −227 in δT10 must not propagate past bit 31 on T10 .
Conditions: Q10 [11] = 1 and Q11 [11] = 0.
5. Restriction: add-difference −212 in δT13 must not propagate past bit 19 on T13 .
Conditions: Q13 [23] = 0 and Q14 [23] = 1.
6. Restriction: add-difference +230 in δT14 must not propagate past bit 31 on T14 .
Conditions: Q15 [14] = 0.
7. Restriction: add-difference −225 in δT15 must not propagate past bit 31 on T15 .
Conditions: Q16 [17] = Q15 [17].
8. Restriction: add-difference −27 in δT15 must not propagate past bit 9 on T15 .
Conditions: Q16 [28] = 0.

18

5 COLLISION FINDING IMPROVEMENTS

9. Restriction: add-difference +224 in δT16 must not propagate past bit 26 on T16 .
Conditions: Q17 [30] = Q16 [30].
10. Restriction: add-difference −229 in δT19 must not propagate past bit 31 on T19 .
Conditions: Q20 [18] = Q19 [18].
11. Restriction: add-difference +217 in δT22 must not propagate past bit 17 on T22 .
See previous item 10.
12. Restriction: add-difference +215 in δT34 must not propagate past bit 15 on T34 .
See previous item 11.
5.1.3

Deriving Qt conditions

Deriving these conditions on Qt to satisfy Tt restrictions can usually be done with a bit of intuitionand naturally for step t one almost always has to look near bits 31 and RCt of Qt and Qt+1 . An
useful aid is a program which, given conditions for Q1 , . . . , Qk+1 , determines the probabilities of
the correct rotations for each step t = 1, . . . , k and the joint probability that for steps t = 1, . . . , k
all rotations are correct. The latter is important since the rotations affect each other.
Such a program could also determine extra conditions which would increase this joint probability. One can then look in the direction of the extra condition(s) that increases the joint probability
the most. However deriving such conditions is not easily fully automated as the following two
problems arise:• Conditions guaranteeing the correct rotation of δTt to δRt may obstruct the correct rotationof δTt+1 to δRt+1 . Or even other δTt+k for k > 0 if these conditions affect the values of
Qt+k and/or Qt+k+1 through indirect conditions.
• It is possible that to guarantee the correct rotation of some δTt there are several solutions
each consisting of multiple conditions. In such a case it might be that there is no single extra
condition that would increase the joint probability significantly.

5.2

Conditions on the Initial Value for the attack

The intermediate hash value, IHVk in the outline in section 4, used for compressing the first blockof the attack, is called the initial value IV for the attack. This does not necessarily have to be theMD5 initial value, it could also result from compressing leading blocks. Although not completely
obvious, the expected complexity and thus running time of the attack does depend on this initialvalue IV .
The intermediate value IHVk+1 = (ak+1 , bk+1 , ck+1 , dk+1 ) resulting from the compression of
the first block is used for compressing the second block and has the necessary conditions ck+1 [25] =1 and dk+1 [25] = 0 for the second differential path to happen. The IHVk+1 depends on the
IV = (a, b, c, d) for the attack and Q61 , . . . , Q64 of the compression of the first block:
IHVk+1 = (ak+1 , bk+1 , ck+1 , dk+1 ) = (a + Q61 , b + Q64 , c + Q63 , d + Q62 ).
In [6] the sufficient conditions Q62 [25] = 0 and Q63 [25] = 0 are given. These conditions on
ck+1 [25] and Q63 [25] can only be satisfied at the same time when
• either c[25] = 1 and there is no carry from bits 0-24 to bit 25 in the addition c + Q63 ;• or c[25] = 0 and there is a carry from bits 0-24 to bit 25 in the addition c + Q63 .
The conditions on dk+1 [25] and Q62 [25] can only be satisfied at the same time when
• either d[25] = 0 and there is no carry from bits 0-24 to bit 25 in the addition d + Q62 ;• or d[25] = 1 and there is a carry from bits 0-24 to bit 25 in the addition d + Q62 .

5.3

Additional Differential Paths

19

Satisfying all these conditions at the same time can even be impossible if for instance c[25 − 0] = 0,or d[25] = 1 ∧ d[24 − 0] = 0, since the necessary carry can never happen.
Luckily this doesn’t mean the attack cannot be done for those IV ’s, since the conditions
Q62 [25] = 0 and Q63 [25] = 0 are only sufficient. They allow the most probable differential path at
those steps to happen, however there are other (less probable) differential paths that are also valid.
If this normally most probable differential path cannot happen or happens with low probability(depending on the carry) then the average complexity of the attack depends on the probability
that other differential paths happen. Experiments clearly indicated that the average runtime forthis situation is significantly larger than the average runtime in the situation where the mostprobable differential path happens with high probability.
Therefore we relaxed all conditions on bit 25 of Q60 , . . . , Q63 to allow those other differential
paths to happen. We also give a recommendation for the following two IV conditions to avoid
this worst case:c[25] = c[24] ∧ d[25] = d[24] for IV = (a, b, c, d)

5.3

Additional Differential Paths

Furthermore, we have constructed new differential paths and conditions using the techniques wewill present in section 6. We have constructed one differential path for the first block, which canbe used as a replacement of the original first differential path.
We also have constructed four differential paths for the second block, each having different setsof conditions imposed on the first block. The first block only has to satisfy one of those sets ofconditions. Then one can continue with the differential path for the second block that is associatedwith the satisfied set of conditions. Hence, together the five differential paths for the second blockallow more freedom and improved collision finding for the first block.
Our differential paths for the first and second block were constructed using the exact samemessage block differences and IHV differences as the original first and second differential path,respectively. Also in step t = 26, ours and Wang’s original differential paths have the samedifferences in the working state (δQ26 , δQ25 , δQ24 , δQ23 ) = (0, 0, 0, 0). Hence, also in later steps
t = 26, . . . , 63 our differential paths and conditions are equal to the respective original differential
path and conditions.
Therefore we will omit steps t = 26, . . . , 63 of our differential paths. We also applied conditions
to control rotations using our technique in subsection 5.1. Our differential path for the first block
is shown in Table B-5 and below, its conditions are shown in Table B-6. Our differential paths forthe second block are shown in Table B-7, Table B-9, Table B-11 and Table B-13. The respective
conditions are listed in Table B-8, Table B-10, Table B-12 and Table B-14.

20

5 COLLISION FINDING IMPROVEMENTS

Table 5-1: New first block differential patht

(BSDR of δQt )−−−26 . . . −224 +225

6

+20 −21 +23 −24+25 −26 −27 +28 +220
+221 −222 +226 −231
−26 +231

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

5.4

∆Qt

0−3
4
5

−20 +23 −26 −215
−222 +228 +231
+20 −26 +212 +231
−212 +217 +231
−212 +218 −224
+229 +231
7−2 −213 +224 +231
+224 +231+229 +231+23 −215 −231
−229 −231−231−231+217 −231
−231
−231
−231
−
−
−

δFt

δwt

δTt

RCt

−
−
−28 +214 −219
−223 +225
23 −29 +215
+218 −220 −222

−
231
−

−
231
−28 +214 −219
−223 +225
23 −29 +215
+218 −220 −222·
7
12

−20 +26 −210
+213 −225−25 +28 +215
−221 +226 −228
−20 +23 −26 +231
20 −26 +212 +231
20 −26 −217
−229 +231
27 −212 +231
231
224 +229 +231
224 +231
231
29−2 +231
231
231
231
231
231
−
231
−

−

−20 +26 −210
+213 −225
25 +28 +215
−221 +226 −228
−21 +25 −220 +226
20 −27 +212
23 −27 −217
−222 −228
20 +26−212 +217−212 +218 −230
−27 −213 +225
224
−
23
−229
−
−
217
−
−
−

22

−

−
−
−
215
−
−
231
−
−
−
215
−
−
−
−
231
−
231

17

7
12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

Tunnels

In [10], Klima presented a new collision finding technique called tunneling. A tunnel allows one
to make controlled changes in the message block B such that in Q1 up to a certain Qk , where kdepends on the tunnel used, only small changes occur and all conditions remain unaffected. In
fact, the effect of a tunnel is best shown using changes in a certain Qm as we will show in thefollowing example with m = 9 which is called the Q9 -tunnel.
5.4.1

Example: Q9 -tunnel

Assume that we have found a block B0 that meets all first block conditions in Table B-3 up to
Q24 . The conditions for Q9 , Q10 and Q11 are:t
Conditions on Qt : b31 . . . b0
9 11111011 ...10000 0.1^1111 00111101
10 0111.... 0..11111 1101...0 01....00
11 0010.... ....0001 1100...0 11....10
As this table shows, there are four bits in Q9 that can be chosen freely, namely Q9 [14], Q9 [21],Q9 [22] and Q9 [23]. If we change one of these bits, say Q9 [22], without changing Q1 , . . . , Q8 and5.4

Tunnels

21

Q10 , . . . , Q16 then only the following message block words are changed:
m8
m9
m10
m11
m12

= W8
= W9
= W10
= W11
= W12

=
RR(Q9 − Q8 , 7)
= RR(Q10 − Q9 , 12)= RR(Q11 − Q19 , 17)= RR(Q12 − Q11 , 22)= RR(Q13 − Q12 , 7)−
f8 (Q8 , Q7 , Q6 )−f9 (Q9 , Q8 , Q7 )− f10 (Q10 , Q9 , Q8 )− f11 (Q11 , Q10 , Q9 )− f12 (Q12 , Q11 , Q10 )

− Q5
− Q6
− Q7
− Q8
− Q9

− AC8
− AC9
− AC10− AC11− AC12Hence, all conditions in the first round remain satisfied. In the second round Q17 and Q18 do notchange, as steps t = 16, 17 do not depend on m8 , . . . , m12 as shown below:
Step tMessage block Wt
Affected Qt+1

16
m1
Q17

17
m6
Q18

18
m11
Q19

19
m0
Q20

20
m5
Q21

21
m10
Q22

22
m15
Q23

23
m4
Q24

24
m9
Q25

25
m14
Q26

26
m3
Q27

On the other hand, a different m11 may lead to a different Q19 .
Suppose that Q11 [22] = 1 then
F11 [22] = f11 (Q11 [22], Q10 [22], Q9 [22]) = (Q11 [22] ∧ Q10 [22]) ⊕ (Q11 [22] ∧ Q9 [22]) = Q10 [22].
Hence F11 and thus also m11 do not change. In this case, actually Q17 up to Q21 remain unaffectedby the change in Q9 [22].
Furthermore, if we suppose that Q10 [22] = 0 then
F10 [22] = f10 (Q10 [22], Q9 [22], Q8 [22]) = (Q10 [22] ∧ Q9 [22]) ⊕ (Q10 [22] ∧ Q8 [22]) = Q8 [22]and also m10 does not change. In this case we have achieved that a change in a single bit Q9 [22]actually leaves Q17 up to Q24 unchanged and therefore all conditions in Q1 up to Q24 remain
satisfied.
In general, over multiple bits Q9 [i1 ], . . . , Q9 [in ] with Q10 [i1 ] = . . . = Q10 [in ] = 0 and Q11 [i1 ] =. . . = Q11 [in ] = 1, we find that changing those bits leads to a total of 2n different message blocks,
including the one we started with. And all those message blocks meet all conditions for Q1 up toQ24 .
In the case of the first block conditions in Table B-3 we find that only bits Q9 [21], Q9 [22] andQ9 [23] can be part of the Q9 -tunnel as Q10 [14] = 1 instead of 0. We need the extra conditions
Q10 [21] = Q10 [22] = 0 and Q11 [21] = Q11 [22] = Q11 [23] = 1 to make use of this tunnel, as shown
below in green and underlined.
t
Conditions on Qt : b31 . . . b0
9 11111011 xxx10000 0.1^1111 00111101
10 0111.... 00011111 1101...0 01....00
11 0010.... 111.0001 1100...0 11....10
Initially the bits xxx should be set to 000 in a collision finding algorithm and when a message
block B0 is found that meets all conditions for Q1 up to Q24 then we expand this B0 into a set of
8 different message blocks using the 8 different values for these bits xxx. Q25 is the first affected
Qt for which we have to check if conditions are met, and is called the point of verification or POV.
The number of bits that can be changed in a tunnel, in this case 3, is called the strength of thetunnel.
5.4.2

Notation for tunnels

We will use the notation T (Qi , mj ) for the tunnel consisting of those bits of Qi that do not change
W16 , . . . , Wk but do change Wk+1 = mj . In other words those bits of Qi that we can changesuch that Q17 , . . . , Qk+1 remain unaffected while Qk+2 does change. Naturally all such possible
tunnels are disjoint as each bit of Qi changes an unique first message word Wk+1 . E.g. the example

22

5 COLLISION FINDING IMPROVEMENTS

tunnel above consisting of the bits Q9 [21], Q9 [22] and Q9 [23] and changing W24 = m9 is notatedas T (Q9 , m9 ). Also since Q10 [14] = 1 the bit Q9 [14] changes m10 , the bit Q9 [14] is part of thetunnel T (Q9 , m10 ). Furthermore, the strength of a tunnel is the number of bits it consists of andis denoted as Si,j = |T (Qi , mj )|.
The tunnels that we will use in our results are:Table 5-2: Tunnels for collision finding
TunnelT (Q9 , m9 )T (Q4 , m4 )T (Q9 , m10 )T (Q10 , m10 )T (Q4 , m5 )T (Q5 , m5 )Required bitconditions
Q10 [i] = 0 ∧ Q11 [i] = 1
Q5 [i] = 0 ∧ Q6 [i] = 1
Q10 [i] = 1 ∧ Q11 [i] = 1
Q11 [i] = 0
Q5 [i] = 1 ∧ Q6 [i] = 1
Q6 [i] = 0

First affected Qt , t > 16
Q25
Q24
Q22
Q22
Q21
Q21

It should be noted that the tunnels and their required bitconditions above depend only on
the bits of Qt and not on the bits of Q0t . Below we show the different tunnel strengths for all
differential paths in the Appendix:
Table 5-3: Tunnel strengths for known differential paths
Differential path
Wang’s first differential path
Wang’s second differential path
Our first block diff. path
Our second block diff. path 1
Our second block diff. path 2
Our second block diff. path 3
Our second block diff. path 4
Our diff. path Table D-6
Our diff. path Table D-8
Our diff. path Table D-10
Our diff. path Table D-12
Our diff. path Table D-14
Our diff. path Table D-16
Our diff. path Table D-18
Our diff. path Table D-20

S9,9
3
9
16
9
9
9
9
12
11
11
10
12
12
10
15

S4,4
0
6
4
0
1
0
1
13
17
14
14
17
15
17
19

S9,10
1
2
1
3
2
2
1
1
1
0
1
0
1
2
0

S10,10
11
3
2
2
2
3
2
5
5
6
8
7
7
6
4

S4,5
4
0
0
0
0
0
0
0
1
3
1
0
1
1
0

S5,5
0
1
0
0
0
1
0
3
1
2
4
4
1
2
2

Total
19
21
23
15
14
15
13
34
36
36
38
40
37
38
40

Especially in the last 8 differential paths above, one can see that we are able to optimize thetunnel strength when constructing differential paths.

5.5

Collision Finding Algorithm

In this section we will present our near-collision block search algorithm. It is an extension of ourcollision finding algorithms [21] shown here as Algorithm 5.1 and 5.2 which were again based on
Klima’s algorithms [9]. For each of the two collision blocks we used a separate collision finding
algorithm. Using these two collision finding algorithms we were the first to be able to find collisions
for MD5 in the order of minutes. Currently with our three improvements (conditions for therotations, additional differential paths and the algorithms shown here) we are able to find collisions
for MD5 in several seconds on a single pc.

5.5

Collision Finding Algorithm

23

These algorithms depend on the fact that given t, the message block word Wt = mk for somek can be calculated from Qt+1 , Qt , Qt−1 , Qt−2 , Qt−3 using the formulamk = Wt = RR(Qt+1 − Qt , RCt ) − ft (Qt , Qt−1 , Qt−2 ) − Qt−3 − ACt .
Hence, we can choose the working states for the first round satisfying their bitconditions and thendetermine the corresponding message block.
We extended these two collision finding algorithms using the tunnels in subsubsection 5.4.2.
Furthermore we joined them into one near-collision block search algorithm in Algorithm 5.3 which
also is suited for our differential paths we use later on (e.g. Table D-6). As these differential paths
have a lot more bitconditions than the differential paths by Wang et al., we tried to maximize thenumber of choices at each step. During the construction of the differential paths themselves wealso tried to maximize their total tunnel strength.
Using these optimizations we were able to efficiently find collision blocks for the differential
paths we use later on (e.g. Table D-6) in chosen-prefix collisions using in the order of 242 compressions, whereas using the basic algorithm in subsection 4.5 this would be infeasible. As thesedifferential paths have a lot more bitconditions than e.g. the ones used in Wang’s attack, the basic
algorithm would need in the order of 2100 compressions to find a collision block, which is evenharder than a brute-force collision search of approx. 264 compressions.
Algorithm 5.1 Block 1 search algorithm
Note: conditions are listed in Table B-3. See subsection 5.1 for the conditions on T22 and T34 .
1. Choose Q1 , Q3 , . . . , Q16 fulfilling conditions;
2. Calculate m0 , m6 , . . . , m15 ;3. Loop until Q17 , . . . , Q21 are fulfilling conditions:(a) Choose Q17 fulfilling conditions;(b) Calculate m1 at t = 16;(c) Calculate Q2 and m2 , m3 , m4 , m5 ;(d) Calculate Q18 , . . . , Q21 ;4. Loop over all possible Q9 , Q10 satisfying conditions such that m11 does not change:(Use tunnels T (Q9 , m10 ), T (Q9 , m9 ) and T (Q10 , m10 ))(a) Calculate m8 , m9 , m10 , m12 , m13 ;(b) Calculate Q22 , . . . , Q64 ;(c) Verify conditions on Q22 , . . . , Q64 , T22 , T34 and the IHV -conditions for the next block.
Stop searching if all conditions are satisfied and a near-collision is verified.
5. Start again at step 1.

24

5 COLLISION FINDING IMPROVEMENTS

Algorithm 5.2 Block 2 search algorithm
Note: conditions are listed in Table B-4. See subsection 5.1 for the conditions on T22 and T34 .
1. Choose Q2 , . . . , Q16 fulfilling conditions;
2. Calculate m5 , . . . , m15 ;3. Loop until Q17 , . . . , Q21 are fulfilling conditions:(a) Choose Q1 fulfilling conditions;(b) Calculate m0 , . . . , m4 ;(c) Calculate Q17 , . . . , Q21 ;4. Loop over all possible Q9 , Q10 satisfying conditions such that m11 does not change:(Use tunnels T (Q9 , m10 ), T (Q9 , m9 ) and T (Q10 , m10 ))(a) Calculate m8 , m9 , m10 , m12 , m13 ;(b) Calculate Q22 , . . . , Q64 ;(c) Verify conditions on Q22 , . . . , Q64 , T22 , T34 .
Stop searching if all conditions are satisfied and a near-collision is verified.
5. Start again at step 1.

In our near-collision block search algorithm below in 5.3, one should keep the bits of tunnels
T (Q4 , m4 ), T (Q4 , m5 ), T (Q5 , m5 ), T (Q9 , m9 ), T (Q9 , m10 ) and T (Q10 , m10 ) zero-valued. Onlyat the step where one uses the tunnel we will use the different values for the bits involved. It is
more efficient to fix these tunnels before starting the collision search by applying their requiredconditions and making use of precomputed tables. However it is also possible to determine thesetunnels at the step they are used. Furthermore, when e.g. using Wang’s first block differential
path one should not actually build the set M0 as all values of m0 will do and 232 words would
require 16GB of memory. In general one should not build this set if it would require more memory
than some large memory bound, and simply use random values m0 at step 11. and then verify if
Q1 and Q2 satisfy their conditions.
We have done a complexity analysis using our latest implementation of Wang’s attack where
we distinguish between three cases for the IV : the MD5 initial value IHV0 , recommended IV ’s
as in subsection 5.2 and arbitrary IV ’s. Table 5-4 below shows the collision finding complexity as
the cost equivalent to computing the stated number of compressions and the amount of time ittakes on a 2.6Ghz Pentium4 pc.
Table 5-4: Collision finding complexity
IV caseMD5 IV = IHV0
Recommended IV ’s
Random IV ’s

Avg. complexity Avg. timein compressions in seconds
223.6
4.2
224.1
6.2
224.8
10.0

5.5

Collision Finding Algorithm

Algorithm 5.3 Near-collision block search algorithm
1. Choose random Q3 , . . . , Q6 and Q13 , . . . , Q17 fulfilling conditions;
2. Calculate m1 at step t = 16;
3. Build a set M0 of values m0 such that Q1 and Q2
resulting from m0 and m1 fulfill their conditions;
4. For all values of Q7 that fulfill conditions do:
5.
Calculate m6 at step t = 6 and Q18 at step t = 17;
6.
If Q18 does not satisfy conditions continue at step 4.;
7.
For all values of Q8 , . . . , Q12 fulfilling conditions do:
8.
Calculate m11 at step t = 11 and Q19 at step t = 18;
9.
If Q19 does not satisfy conditions continue at step 7.;
10.
For all m0 ∈ M0 do:
11.
Calculate Q1 , Q2 and Q20 at steps t = 0, 1, 19 respectively;
12.
If Q20 does not satisfy conditions continue at step 10.;
13.
Use tunnels T (Q4 , m5 ) and T (Q5 , m5 ) and do:
14.
Calculate m5 at step t = 5 and Q21 at step t = 20;
15.
If Q21 does not satisfy conditions continue at step 13.;
16.
Use tunnels T (Q9 , m10 ) and T (Q10 , m10 ) and do:
17.
Calculate m10 at step t = 10 and Q22 at step t = 21;
18.
Calculate m15 at step t = 15 and Q23 at step t = 22;
19.
If Q22 or Q23 does not satisfy conditions continue at step 16.;
20.
Use tunnel T (Q4 , m4 ), do:
21.
Calculate m4 at step t = 4 and Q24 at step t = 23;
22.
If Q24 does not satisfy conditions continue at step 20.;
23.
Use tunnel T (Q9 , m9 ), do:24.
Calculate remaining mi at t = i ∈ {0, . . . , 15};
25.
Calculate Q25 , . . . , Q64 ;26.
Verify near-collision and return B = (mi )15
i=0 if so;27.
od; (step 23.)28.
od; (step 20.)29.
od; (step 16.)30.
od; (step 13.)31.
od; (step 10.)32.
od; (step 7.)
33. od; (step 4.)
34. Start again at step 1.

25

26

6

6 DIFFERENTIAL PATH CONSTRUCTION METHOD

Differential Path Construction Method

Assume MD5Compress is applied to pairs of inputs for both intermediate hash value and message
block, i.e., to (IHV, B) and (IHV 0 , B 0 ). We will assume that both δIHV and δB = (δmi )15
i=0 aregiven and possibly even IHV and IHV 0 or bits thereof. Note the slight abuse of notation here as
we use only differences such as δmi without specifying the values mi and m0i . We will continue todo so in our differential analysis.
A differential path for MD5Compress is a precise description of the propagation of differences
through the 64 steps caused by δIHV and δB:
δFt
δTt
δRt
δQt+1

=
=
=
=

ft (Q0t , Q0t−1 , Q0t−2 ) − ft (Qt , Qt−1 , Qt−2 );δFt + δQt−3 + δWt ;RL(Tt0 , RCt ) − RL(Tt , RCt );δQt + δRt .

Note that δFt is not uniquely determined by δQt , δQt−1 and δQt−2 , so it is necessary to describe
the value of δFt and how it can result from the Qi , Q0i in such a way that it does not conflict withother steps. Similarly δRt is not uniquely determined by δTt and RCt , so also the value of δRt
has to be described.

6.1

Bitconditions

We will use bitconditions on (Qt , Q0t ) to describe differential paths, where a single bitcondition
specifies directly or indirectly the values of the bits Qt [i] and Q0t [i]. Therefore, a differential pathcan be seen as a matrix of bitconditions with 68 rows (for the possible indices t = −3, −2, . . . , 64
in Qt , Q0t ) and 32 columns (one for each bit). A direct bitcondition on (Qt [i], Q0t [i]) does not
involve other bits Qj [k] or Q0j [k], whereas an indirect bitcondition does, and specifically one of
Qt−2 [i], Qt−1 [i], Qt+1 [i] or Qt+2 [i]. Using only bitconditions on (Qt , Q0t ) we can specify all thevalues of δQt , δFt and thus δTt and δRt = δQt+1 − δQt by the relations above. A bitcondition on(Qt [i], Q0t [i]) is denoted by qt [i], and symbols like 0, 1, +, -, ^, . . . are used for qt [i], as defined below.
The 32 bitconditions (qt [i])31
i=0 are denoted by qt . We discern between differential bitconditions
and boolean function bitconditions. The former, shown in Table 6-1, are direct, and specify the
Table 6-1: 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−1
P31 i
Note: δQt = i=0 2 ki and ∆Qt = (ki ).
P ivalue ki = Q0t [i] − Qt [i] which together specify δQt =2 ki by how each bit changes. Note that
∆Qt = (ki ) is actually a BSDR of δQt . The boolean function bitconditions, shown in Table 6-2,
are used to resolve any ambiguity in∆Ft JiK = ft (Q0t [i], Q0t−1 [i], Q0t−2 [i]) − ft (Qt [i], Qt−1 [i], Qt−2 [i]) ∈ {−1, 0, +1}
caused by different possible values for Qj [i], Q0j [i] for given bitconditions.
As an example, for t = 0 and bitconditions (qt [i], qt−1 [i], qt−2 [i]) = (., +, -) there are twodifferent possible values for the tuple (Qt [i], Q0t [i], Qt−1 [i], Q0t−1 [i], Qt−2 [i], Q0t−2 [i]) satisfying thesebitconditions. As each case leads to a different boolean function difference, there is an ambiguity:
if Qt [i] = Q0t [i] = 0 then ∆Ft JiK = ft (0, 1, 0) − ft (0, 0, 1) = −1,
but if Qt [i] = Q0t [i] = 1 then ∆Ft JiK = ft (1, 1, 0) − ft (1, 0, 1) = +1.

6.2

qt [i]
0
1
^
v
!
y
m
w
#
h
?
q

Differential path construction overview

Table 6-2: Boolean function bitconditions.
condition on (Qt [i], Q0t [i])direct/indirect
Qt [i] = Q0t [i] = 0
directQt [i] = Q0t [i] = 1
directQt [i] = Q0t [i] = Qt−1 [i]indirect
Qt [i] = Q0t [i] = Qt+1 [i]indirect
Qt [i] = Q0t [i] = Qt−1 [i]indirect
Qt [i] = Q0t [i] = Qt+1 [i]indirect
Qt [i] = Q0t [i] = Qt−2 [i]indirect
Qt [i] = Q0t [i] = Qt+2 [i]indirect
Qt [i] = Q0t [i] = Qt−2 [i]indirect
Qt [i] = Q0t [i] = Qt+2 [i]indirect
Qt [i] = Q0t [i] ∧ (Qt [i] = 1 ∨ Qt−2 [i] = 0)
indirect
Qt [i] = Q0t [i] ∧ (Qt+2 [i] = 1 ∨ Qt [i] = 0)
indirect27

direction

backward
forwardbackward
forwardbackward
forwardbackward
forwardbackward
forward

To resolve this ambiguity, the bitconditions (.,+,-) can be replaced by either (0,+,-) or (1,+,-).
Later on we will show how one can efficiently determine and resolve ambiguities methodically.
All boolean function bitconditions include the constant bitcondition Qt [i] = Q0t [i], so they
do not affect δQt . Furthermore, indirect boolean function bitconditions never involve a bit withcondition + or -, since then it could be replaced by one of the direct bitconditions ., 0 or 1.
We distinguish in the direction of indirect bitconditions, since that makes it easier to resolve an
ambiguity later on. It is quite easy to change all backward bitconditions into forward ones in avalid (partial) differential pathm, and vice versa.
When all δQt and δFt are determined by bitconditions then also δTt and δRt can be determined,
which together describe the bitwise rotation of δTt in each step. Note that this does not describe
if it is a valid rotation or with what probability the rotation from δTt to δRt occurs.

6.2

Differential path construction overview

The basic idea in constructing a differential path is to construct a partial lower differential pathover steps t = 0, 1, . . . , K for some K and a partial upper differential path over steps t = K +5, 17, . . . , 63, so that the Qi involved in the partial paths meet but do not overlap. Then we will
try to connect those partial paths over the remaining 4 steps into one full differential path. This
will most likely fail and in general one will have to try to connect many pairs before finding afull valid differential path. The success probability depends heavily on the amount of freedom
left by those bitconditions in the partial differential paths that affect the remaining steps t =K + 1, K + 2, K + 3, K + 4.
Connecting those two partial paths will result in a lot of bitconditions, hence it is best to
have K + 4 < 17 to keep collision finding feasible. We chose K = 12 as then one can alreadydetermine (and maximize) the total tunnel strength of the resulting full differential path even
before connecting. However, this choice may lead to problems as there can be a lot of conditions
on Q−2 , . . . , Q2 and Q13 , . . . , Q17 which can result in a very limited (perhaps empty) set of values
m1 for which these conditions can simultaneously be satisfied. In this case, another good choice
would be K = 11 as there one also has a good idea of total tunnel strength, however there will beless conditions on Q17 and more freedom for m1 .
Constructing the partial lower path can be done by starting with bitconditions q−3 , q−2 , q−1 ,q0 that are equivalent to given values of IHV, IHV 0 and then extend this step by step. Similarly
a partial upper path can be constructed by extending the partial path in Table 7-1 step by step.
Alternatively one can construct by hand any partial lower or upper differential path and thenextend this step by step using our method. E.g. one could use the first and last parts of Wang’s
original differential paths and extend those till they meet and try to complete them in an effort
to maximize the total tunnel strength.

28

6 DIFFERENTIAL PATH CONSTRUCTION METHOD

To summarize, the algorithm for constructing a differential path consist of the following substeps:
1. Using IHV and IHV 0 determine bitconditions (qi )0i=−3 which already form a partial lower
differential path.
2. Generate a partial lower differential path by extending (qi )0i=−3 forward up to step t = K.
3. Generate a partial upper differential path by extending the path in Table 7-1 down tot = K + 5.
4. Try to connect these lower and upper differential paths over t = K + 1, K + 2, K + 3, K + 4.
If this fails generate other partial lower and upper differential paths and try again.

6.3

Extending partial differential paths

Suppose we have a partial differential path consisting of at least bitconditions qt−1 and qt−2 andthat the values δQt and δQt−3 are known. We assume that all indirect bitconditions are forwardand do not involve bits of Qt . We want to extend this partial differential path forward with stept resulting in the value δQt+1 and (additional) forward bitconditions qt , qt−1 , qt−2 fulfilling ourassumptions for the next step t + 1. If we also have qt instead of only the value δQt (e.g. q0
resulting from given values IHV, IHV 0 ), then we can skip the carry propagation and continue at
Section 6.3.2.
6.3.1

Carry propagation

First we want to use the value δQt to select bitconditions qt . This can be done by choosing any
BSDR of δQt , which directly translates into a possible choice for qt consisting of only differential
bitconditions as given in Table 6-1. Since we want to construct differential paths with as few
bitconditions as possible, but also want to be able to randomize the process, we may choose any
low weight BSDR (such as the NAF).
6.3.2

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]. The triple (a, b, c) is associated with the set
Uabc 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]):Uabc = (x, x0 , y, y 0 , z, z 0 ) ∈ {0, 1}6 satisfies bitconditions (a, b, c) .
If Uabc = ∅ then (a, b, c) is said to be contradicting and cannot be part of any valid differential
path. We define Ft as the set of all triples (a, b, c) such that all indirect bitconditions involve only
Qt [i], Qt−1 [i] or Qt−2 [i] and Uabc 6= ∅.
We define Vabc as the set of all possible boolean function differences ∆Ft JiK = ft (x0 , y 0 , z 0 ) −ft (x, y, z) for given bitconditions (a, b, c) ∈ Ft :Vabc = {ft (x0 , y 0 , z 0 ) − ft (x, y, z) | (x, x0 , y, y 0 , z, z 0 ) ∈ Uabc } ⊂ {−1, 0, +1}.
There are bitconditions (d, e, f ) such that |Vdef | = 1, hence they leave no ambiguity and thetriple (d, e, f ) is said to be a solution. Let St ⊂ Ft be the set of all solutions.
Now for arbitrary (a, b, c) and for each g ∈ Vabc we define Wabc,g as the set of solutions(d, e, f ) ∈ St that are compatible with (a, b, c) and that have g as boolean function difference:
Wabc,g = {(d, e, f ) ∈ St | Udef ⊂ Uabc ∧ Vdef = {g}} .
Note that for all g ∈ Vabc there is always a triple (d, e, f ) ∈ Wabc,g that consists only of direct
bitconditions 01+- fixing a certain tuple in Uabc , hence Wabc,g 6= ∅. Even though Wabc,g is not6.3

Extending partial differential paths

29

empty for all g ∈ Vabc , we are interested in bitconditions (d, e, f ) ∈ Wabc,g that maximizes |Udef |as this maximizes the amount of freedom in the bits of Qt , Qt−1 and Qt−2 while fixing ∆Ft JiK.
The direct and forward (resp. backward) boolean function bitconditions in Table 6-2 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 .
In other words, the chosen boolean function bitconditions allows one to resolve an ambiguity inan optimal way.
If this triple (d, e, f ) ∈ Wabc,g is not unique, then we prefer direct over indirect bitconditions
and short indirect bitconditions (vy^!) over long indirect bitconditions (whqm#?) for simplicity
reasons. For given t, bitconditions (a, b, c), and g ∈ Vabc we define F C(t, abc, g) = (d, e, f ) andBC(t, abc, g) = (d, e, f ) as the preferred triple (d, e, f ) ∈ Wabc,g consisting of direct and forward,
respectively backward bitconditions satisfying{(x, x0 , y, y 0 , z, z 0 ) ∈ Uabc | ft (x0 , y 0 , z 0 ) − ft (x, y, z) = g} = Udef .
These values can easily be determined and should be precomputed for all cases. Tables C-1, C-2,
C-3 and C-4 show these values F C(t, abc, g) and BC(t, abc, g) for all t (grouped per booleanfunction) and all (a, b, c) consisting of differential bitconditions.
For all i = 0, 1, . . . , 31 we have by assumption valid bitconditions (a, b, c) = (qt [i], qt−1 [i],qt−2 [i]) where only c can be an indirect bitcondition. If so, it must involve Qt−1 [i]. Therefore(a, b, c) ∈ Ft . If |Vabc | = 1 there is no ambiguity and we let {gi } = Vabc . Otherwise, if |Vabc | > 1,
then we choose any gi ∈ Vabc and we resolve the ambiguity left by bitconditions (a, b, c) by replacing
them by (d, e, f ) = F C(t, abc, gi ), which results in boolean function difference gi .
P31
Given all gi , the values δFt = i=0 2i gi and δTt = δFt + δQt−3 + δWt can be determined.
6.3.3

Bitwise rotation

The word δTt does not uniquely determine the value of δRt = RL(Tt0 , n) − RL(Tt , n), wheren = RCt . To determine a likely δRt we use the fact that any BSDR (ki ) of δTt fixes a δRt :
δRt =

31
X

2i+n mod 32 (Tt0 [i] − Tt [i]) =

31
X

i=0

2i+n mod 32 ki = 2n

i=0

31−n
X

31
X

2i ki + 2n−32

i=0

2i ki .

i=32−nOne can easily see that different BSDRs (ki ) and (li ) of δTt result in the same δRt as long as
31−nX

2i ki =

31−n
X

2i li

i=0

i=0

and

31
X

2i ki =

i=32−n31
X

2i l i .

i=32−nIn general, let (α, β) ∈ Z2 be a partition of the word δTt with α+β = δTt mod 232 , |α| < 232−n ,|β| < 232 and 232−n |β. For any partition there is a BSDR (ki ) of δTt such that
α=

31−n
X

2i ki

and β =

i=031
X

2i ki .

i=32−nThe converse also holds as for any BSDR (ki ) of δTt defining α and β as above forms a partition(α, β) of δTt . We will denote (ki ) ≡ (α, β) in this case.
The rotation of (α, β) is defined as
δRt = RL((α, β), n) = (2n α + 2n−32 β

mod 232 )(≡ RL((ki ), n)).

This matches exactly the definition of rotating the BSDR (ki ). Clearly different partitions (α, β)of δTt lead to different δRt . We actually can describe all possible partitions quite easily and also
determine their probability P r[δRt = RL(X + δTt , n) − RL(X, n)].

30

6 DIFFERENTIAL PATH CONSTRUCTION METHOD

Let x = (δTt mod 232−n ) and y = (δTt − x mod 232 ), then 0 ≤ x < 232−n and 0 ≤ y < 232 .
This gives rise to at most 4 partitions of δTt :••••(α, β) = (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 and y + 232−n 6= 0 mod 232 .

And these are all possible partitions of δTt . The probability of each partition (α, β) equalsp(α,β) =232−n − |α| 232 − |β|
·
.
232−n
232

This formula is derived by counting the number of 0 ≤ X < 232 such that for the BSDR definedby ki = (X + δTt )[i] − X[i] it holds that (α, β) ≡ (ki ). Looking only at the first 32 − n bits we canP31−ndetermine for a given α the probability that it will occur as α = i=0 ki . This can be done bydetermining the number r of 0 ≤ X < 232−n such that 0 ≤ α + X < 232−n . Now we distinguishcases: if α < 0 then r = 232−n + α and if α ≥ 0 then r = 232−n − α. Hence r = 232−n − |α| out
P31−nof 232−n X’s. If α = i=0 ki holds then there is no carry to the higher bits and we can use thesame argument for β/232−n . Hence, we concludep(α,β) =232−n − |α| 2n − |β|2n−32
232−n − |α| 232 − |β|
·
=
·
32−n
n
2
2
232−n
232

One then chooses any partition (α, β) for which p(α,β) ≥ 41 and determines δRt as RL((α, β), n).
Previously in practice, we used δRt = RL(N AF (δTt ), n) as this often leads to the highest probability, especially given that we try to minimize the amount of differences in δQt and therefore alsoin δTt and δRt .
We would like to note that in previous work [19] a brute-force approach was used over all
232 words X to find all possible δRt = RL(X + δTt , n) − RL(X, n) resulting from δTt and theirprobabilities. As we show here, finding all possible δRt and their probabilities can be done very
efficiently using a tiny number of computations.

6.4

Extending backward

Similar to extending forward, 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. We want toextend this partial differential path backward with step t resulting in δQt−3 and (additional)
bitconditions qt , qt−1 , qt−2 . We assume that all indirect bitconditions are backward and do not
involve bits of Qt−2 .
We choose a BSDR of δQt−2 with weight at most 1 or 2 above the lowest weight, such as the
NAF. We translate the chosen BSDR into bitconditions qt−2 .
For all i = 0, 1, . . . , 31 we have by assumption valid bitconditions (a, b, c) = (qt [i], qt−1 [i],qt−2 [i]) where only b can be an indirect bitcondition. If so, it must involve Qt−2 [i]. Therefore(a, b, c) ∈ Ft . If |Vabc | = 1 there is no ambiguity and we let {gi } = Vabc . Otherwise, if |Vabc | > 1,
then we choose any gi ∈ Vabc and we resolve the ambiguity left by bitconditions (a, b, c) by replacing
them by (d, e, f ) = BC(t, abc, gi ), which results in boolean function difference gi . Given all gi , theP31value δFt = i=0 2i gi can be determined.
To rotate δRt = δQt+1 − δQt over n = 32 − RCt bits, we simply choose a partition (α, β) ofδRt with probability ≥ 1/4 and determine δTt = RL((α, β), n). Finally, we determine δQt−3 =δTt − δFt − δWt to extend our partial differential path backward with step t.

6.5

Constructing full differential paths

Construction of a full differential path can be done as follows. Choose δQ−3 and bitconditions q−2 ,q−1 , q0 and extend forward up to step 11. Also choose δQ64 and bitconditions q63 , q62 , q61 and6.5

Constructing full differential paths

31

extend backward down to step 16. This leads to bitconditions q−2 , q−1 , . . . , q11 , q14 , q15 , . . . , q63
and differences δQ−3 , δQ12 , δQ13 , δQ64 . It remains to finish steps t = 12, 13, 14, 15. As withextending backward we can, for t = 12, 13, 14, 15, determine δRt , choose the resulting δTt afterright rotation of δRt over RCt bits, and determine δFt = δTt − δWt − δQt−3 .
We aim to find new bitconditions q10 , q11 , . . . , q15 that are compatible with the original bitconditions and that result in the required δQ12 , δQ13 , δF12 , δF13 , δF14 , δF15 , thereby completingthe differential path. First we can test whether it is even possible to find such bitconditions.
For i = 0, 1, . . . , 32, let Ui be a set of 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. We want to construct each Ui so that for eachtuple (q1 , q2 , f1 , f2 , f3 , f4 ) ∈ Ui there exist bitconditions q10 [`], q11 [`], . . . , q15 [`], determining the∆Q11+j J`K and ∆F11+k J`K below, over the bits ` = 0, . . . , i − 1, such that
δQ11+j= qj +i−1
X`=0

δF11+k= fk +i−1
X`=02` ∆Q11+j J`K,

j = 1, 2,2` ∆F11+k J`K,

k = 1, 2, 3, 4.

This implies U0 = {(δQ12 , δQ13 , δF12 , δF13 , δF14 , δF15 )}. The other Ui are constructed inductively
by Algorithm 6.1 by exhaustive search. Furthermore, |Ui | ≤ 26 , since for each qj , fk there are at
most 2 possible values that can satisfy the above relations.
If we find U32 6= ∅ then there exists a path u0 , u1 , . . . , u32 with ui ∈ Ui where each ui+1 isgenerated by ui in Algorithm 6.1. Now the desired new bitconditions (q15 [i], q14 [i], . . . , q10 [i]) are(a0 , b00 , c000 , d000 , e00 , f 0 ), which can be found at step 13 of Algorithm 6.1, where one starts with ui
and ends with ui+1 .
Clearly, the probability of success and thus the complexity of constructing a full differential pathdepends on several factors, where the amount of freedom left by the bitconditions q10 , q11 , q14 , q15
and the number of possible BSDR’s of δQ12 and δQ13 are the most important.
Algorithm 6.1 Construction of Ui+1 from Ui .
Suppose Ui is constructed as desired. Set Ui+1 = ∅ and for each tuple (q1 , q2 , f1 , f2 , f3 , f4 ) ∈ Ui
do the following:
1. Let (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
3.
Let q10 = 0, −1, +1 for resp. d =.,-,+
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
7.
Let q20 = 0, −1, +1 for resp. c =.,-,+
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.
Insert (q1 − 2i q10 , q2 − 2i q20 , f1 − 2i f10 , f2 − 2i f20 , f3 − 2i f30 , f4 − 2i f40 ) into Ui+1 .
Keep only one of each tuple in Ui+1 that occurs multiple times. By construction we find Ui+1 as
desired.

32

7

7 CHOSEN-PREFIX COLLISIONS

Chosen-Prefix Collisions

A chosen-prefix collision is a pair of messages M and M 0 which consist of arbitrary chosen prefixes
P and P 0 (not necessarily of the same length), together with constructed suffixes S and S 0 suchthat M = P kS, M 0 = P 0 kS 0 and M D5(M ) = M D5(M 0 ). Furthermore, appending an arbitrary
suffix S 00 to each of these messages still leads to a collision M D5(M kS 00 ) = M D5(M 0 kS 00 ) of MD5.
In this section we will present our joint work with Arjen Lenstra and Benne de Weger which isa method to construct such chosen-prefix collisions. Using this method we have constructed one
example of a chosen-prefix collision, namely two colliding X.509 certificates with different identities[22] which we will refer to often. Details on this example itself are discussed in subsection 7.5.
The two suffixes we will construct consist of three parts: padding bitstrings Sp and Sp0 , followedby ‘birthday’ bitstrings Sb and Sb0 , followed by ‘near collision’ blocks Sc and Sc0 . The padding
bitstrings Sp and Sp0 are chosen to guarantee that the bitlengths of P kSp and P 0 kSp0 are both
equal to L = 512n − 96 for a positive integer n. They can be chosen arbitrarily but must meet thelength requirements. The ‘birthday’ bitstrings Sb and Sb0 both consist of 96 bits and complete then-th block. Applying MD5 to P kSp kSb and P 0 kSp0 kSb0 will result in IHVn and IHVn0 , respectively.
The ‘birthday’ bitstrings are constructed in such a manner that δIHVn can be eliminated using
several near-collision blocks in Sc and Sc0 as described below.
The main idea is to eliminate the difference δIHVn using several consecutive near-collisions thattogether constitute Sc and Sc0 . The number of differences in δIHVn = (δa, δb, δc, δd) is measured
using the NAF weight, the total weight of the NAFs of δa, δb, δc and δd. For each near-collision weneed to construct a differential path such that the NAF weight of the new δIHVn+j+1 is lower thanthe NAF weight of δIHVn+j , until after r near-collisions we have reached δIHVn+r = (0, 0, 0, 0).

7.1

Near-collisions

We will use near-collisions based on a family of upper differential paths using the message block
difference δm11 = ±2d for varying 0 ≤ d ≤ 31 and δmi = 0 for i 6= 11. This was suggested to
us by Xiaoyun Wang as with this type of message difference the number of bitconditions over the
final two rounds can be kept very low. This is illustrated in Table 7-1, where the corresponding
upper differential path is shown for the final 31 steps. As one can see in Table A-1, these message
block differences maximizes the number of steps in the third and fourth round with δQt = 0.
Table 7-1: Partial differential path with δm11 = ±2d .
t
δQtδFt δWt δTt
δRt
RCt
d
30
∓2
31
0
32
0
33
0
0
±2d
0
0
16
34 − 60
0
0
0
0
0
·
61
0
0
±2d ±2d ±2d+10 mod 32
1062±2d+10 mod 32
0
0
0
0
15
63
±2d+10 mod 32
0
0
0
0
21
64
±2d+10 mod 32
Although the number of bitconditions over the final two rounds is very low, the second roundwill contain in the order of 100 bitconditions. Would these bitconditions have occurred in thethird or fourth round, they would have implied a collision finding complexity of approx. 2100 compressions. However, in our case there will be in the order of only 30 bitconditions from Q25 up toQ33 , where Q25 is the POV of the most efficient tunnel T (Q9 , m9 ) (see Table 5-2). Because of thisfact and using the collision finding techniques described in section 5, we were able to find actual
near-collision blocks within feasible time.

7.2

7.2

Birthday Attack

33

Birthday Attack

The differential paths under consideration can only add (or substract) a tuple (0, 2i , 2i , 2i ) to
δIHVn+j and therefore cannot eliminate arbitrary δIHVn . Specifically, we need δIHVn to be of
the form (0, δb, δb, δb) for some word δb.
To solve this we first use a birthday attack to find ‘birthday’ bitstrings Sb and Sb0 such that
δIHVn = (0, δb, δb, δb) for some δb. The birthday attack actually searches for a collision of
IHVn = (a, b, c, d) and IHVn0 = (a0 , b0 , c0 , d0 ) such that (a, b−c, b−d) = (a0 , b0 −c0 , b0 −d0 ), implying
indeed δa = 0 and δb = δc = δd. The search space consists of 96 bits, 3 words (a, b − pc, b − d) of 32
bits each, and therefore the birthday step can be expected to require on the order of π2 296 ≈ 249
calls to the MD5 compression function.
As soon as a collision with some δb is found, one can start eliminating the differences in δb.
Using our family of upper differential paths we can eliminate any signed bit of δb. Since the NAFof δb has lowest weight among BSDR’s, eliminating the signed bits in this NAF will lead to thelowest number of near-collisions required. Hence, on average one may expect to find a δb of NAF
weight 32/3 ≈ 11. One may extend the birthdaying by searching for a δb of lower NAF weight.
In the case of our colliding certificates example we found a δb of NAF weight only 8, after having
extended the search somewhat longer than absolutely necessary.
When actually implementing such a birthday attack, one needs to fix a IHV selection function
φ : (x, y, z) 7→ {IHVn , IHVn0 } and a message block generating function ψ : (x, y, z) 7→ B. E.g.
for φ one can use the parity of x to map either to IHVn or IHVn0 and for ψ one can use apartial 416 bit block R and map to Rkxkykz. These functions are used to compose the functionΦ : (x, y, z) 7→ (a, b − c, b − d) where (a, b, c, d) = MD5Compress(φ(x, y, z), ψ(x, y, z)), which is adeterministic pseudo-random walk in our 96 bit search space.
Applying generic Pollard-Rho, one can find a collision Φ(x, y, z) = Φ(x0 , y 0 , z 0 ) with (x, y, z) 6=0 0 0(x , y , z ). The collision is useful only if φ(x, y, z) 6= φ(x0 , y 0 , z 0 ), i.e. the collision does not consistof only one of our chosen prefixes. Directly√ parallelizing Pollard-Rho using K instances does notlead to a factor K speedup, rather to a K speedup. We refer to [23] for a method to parallelize abirthday search leading to a factor K speedup. We have implemented this method in our birthday
search for our chosen-prefix collision example.
Their general idea is to fix a relatively small set S of tuples (x, y, z) called distinguished points.
E.g. all tuples (x, y, z) having x = 0. Each instance will generate ‘trails’ starting with a random(x0 , y0 , z0 ) and iteratively calculate (xi+1 , yi+1 , zi+1 ) = Φ(xi , yi , zi ) until a distinguished point(xl , yl , zl ) ∈ S is reached. Each trail can be stored using only its starting point (x0 , y0 , z0 ), its
ending point (xl , yl , zl ) ∈ S and its length l. When one trail meets another trail in a point then the
two trails will coincide from that point on and will end in the same distinguished point. Hence,a collision is detected when different trails result in the same distinguished point. The collisionitself can then be found by recalculating both trails to the point where they meet first.
However, there are some small issues one has to be aware of. When a trail reaches its starting
point it will fall into an endless cycle without ever reaching a distinguished point. To avoid thiscase one should abort any trail whose length exceeds a certain limit, e.g. a limit set to 20 times
the expected trail length. It is also possible that a trail reaches the starting point of another trail
so that both end in the same distinguished point without yielding an actual collision. This cannot
be avoided and should only occur with a very small probability.

7.3

Iteratively Reducing IHV -differences

Assume we have found birthday bitstrings such that δIHVn = (0, δb, δb, δb) and let (ki ) be the
NAF of δb. Then we can reduce δIHVn = (0, δb, δb, δb) to (0, 0, 0, 0) by using, for each non-zero ki ,a differential path based on the partial differential path in Table 7-1 with δm11 = −ki 2i−10 mod 32 .
In other words, the signed bit difference at position i in δb can be eliminated by choosing a message
difference only in δm11 , with just one opposite-signed bit set at position i − 10 mod 32. Let ij for
j = 1, 2, . . . , r be the indices of the non-zero ki . Starting with n-block messages M = P kSp kSb
and M 0 = P 0 kSp0 kSb0 and the corresponding resulting IHVn and IHVn0 we do the following for34

7 CHOSEN-PREFIX COLLISIONS

j = 1, 2, . . . , r in succession:
1. Let δMn+j = (δmi ) where δm11 = −kij 2ij −10 mod 32 and δm` = 0 for ` 6= 11.
2. Find a full differential path as shown in section 6 by connecting a lower differential path0
starting from IHVn+j−1 and IHVn+j−1
and an upper differential path based on Table 7-1.
0
3. Find message blocks Sc,j and Sc,j
= Sc,j + δMn+j , that satisfy the differential path using
the techniques shown in section 5.
0
00
4. Let IHVn+j = MD5Compress(IHVn+j−1 , Sc,j ), IHVn+j= MD5Compress(IHVn+j−1, Sc,j),00
and append Sc,j to M and Sc,j to M .

After r iterations we will have found a chosen-prefix collision consisting of M = P kSp kSb kSc and
M 0 = P 0 kSp0 kSb0 kSc0 where Sc and Sc0 consist of the r near-collision blocks Sc = Sc,1 k · · · kSc,r and00
Sc0 = Sc,1
k · · · kSc,rjust found. Any suffix Ss appended to both messages M kSs , M 0 kSs will stilllead to a full collision of MD5, which is useful to construct meaningful collisions for MD5.

7.4

Improved Birthday Search

The following partial differential path is a variant of Table 7-1 using the same message block
differences. They differ only in the very last step where an additional bitdifference occurs. Bothpartial differential paths have almost the same probability, one never differing more than a factor
2 from the other. If we also incorporate the use of this variant upper differential path then we
Table 7-2: Variant partial differential path with δm11 = ±2d .
t
δQtδFt δWt δTt
δRt
d
30
∓2
31
0
32
0
33
0
0
±2d
0
0
34 − 60
0
0
0
0
0
d
d
d+10 mod 32
6100±2 ±2 ±262±2d+10 mod 32
0
0
0
0
63
±2d+10 mod 32
0
0
0
0
64
±2d+10 mod 32 ∓ 2d+31 mod 32

RCt

16
·
10
15
21

can eliminate any δIHVn = (δa, δb, δc, δd) of the form δa = 0, δc = δd. Note that there is nolimitation on δb which corresponds to δQ64 .
A strategy eliminating the differences in a δIHVn of that form using near-collisions based on
the differential paths in Table 7-1 and Table 7-2, denoted as DP1 and DP2 respectively, is thefollowing. Let δe = δb−δc and consider (vi ) = RR(N AF (−δc), 10) and (wi ) = RR(N AF (δe), 31).
Then a non-zero vi corresponds to a bitdifference in δb, δc, δd that can be eliminated using DP1
with δm11 = vi 2i as shown in the previous subsection. Similarly a non-zero wi corresponds to adifference in δb − δd, i.e. one of the extra differences we allowed, which can be eliminated with
DP2 using δm11 = wi 2i . In the latter case one still has to deal with a corresponding difference inδb, δc, δd as we show below.
As a trivial example, suppose δIHV = (0, +212 −21 , +212 , +212 ). This clearly can be eliminatedusing DP2 with δm11 = −22 as also the BSDR’s (vi ) and (wi ) indicate:(vi ) = RR(N AF (−212 ), 10) = RR(−212 , 10) = −22 ,(wi ) = RR(N AF (−21 ), 31) = RR(−21 , 31) = −22 .

7.5

Colliding Certificates with Different Identities

35

Depending on the values of vi and wi for each bit i = 0, . . . , 31 we can eliminate the corresponding bitdifferences in δIHVn with either 1 or 2 near-collision blocks. There are five distinct
cases which we analyze below:
1. When vi = 0 and wi = 0 there is no difference to be eliminated.
2. Suppose vi 6= 0 and wi = 0, then we can use DP1 with δm11 = vi 2i as before to eliminate
the corresponding bitdifferences.
3. Suppose vi = wi 6= 0 then we can use DP2 with δm11 = vi 2i to eliminate the corresponding
bitdifferences as shown in the example.
4. Suppose vi = 0 and wi 6= 0 then we can use one near-collision based on DP2 with δm11 =wi 2i . This introduces a new difference wi 2i+10 mod 32 in δb, δc = δd, which we correct using
a second near-collision based on DP1 with δm11 = −wi 2i .
5. Suppose vi 6= 0 and wi = −vi . In this case we use DP2 with δm11 = wi 2i . As in the previous
case this introduces the bitdifference wi 2i+10 mod 32 in δb, δc = δd. As vi = −wi this signed
bitdifference was already present in δb and δc = δd and a carry happens. If i + 10 = 31 thenthis carry is lost and both differences vi and wi are eliminated. However if i + 10 6= 31 thenwe can eliminate this carry bitdifference using DP1 with δm11 = vi 2i+1 mod 32 .
As in the previous section we use DP1 and DP2 with a given δm11 and the current IHVn+j−10
and IHVn+j−1
to construct a full differential path. Making use of our collision finding algorithm0
we find message blocks Sc,j and Sc,jsatisfying this differential path. We append these message
0
0
blocks to M and M , respectively, and continue with the resulting IHVn+j and IHVn+j
until
δIHV = (0, 0, 0, 0).
Given that (vi ) and (wi ) are rotated NAF’s, the probability that a signed bit vi or wi is nonzero equals 1/3. Also, vi or wi equals a specific value +1 or −1 with probability 1/6. Hence, we
can determine the probability for each of the five cases above:
Case
Probability# Near-collisions

1

2

3

4

5

4
22
3 = 9

2
1 2
3 · 3 = 91
1 1
3 · 6 = 1822 1
3 · 3 = 91
1 1
3 · 6 = 18

0

1

1

2

2

1
1
The expected number of required near-collisions per bit is ( 29 + 18
) · 1 + ( 29 + 18
) · 2 = 56 . It follows
5
that we can expect to need 6 · 32 ≈ 27 near-collision blocks to eliminate all differences in a random
δIHVn of the form δa = 0 and δc = δd.
The birthday search has to be slightly modified as we only need a 64-bit search space. As before,
we need a IHV selection function φ : (x, y) 7→ {IHVn , IHVn0 } and a message block generating
function ψ : (x, y) 7→ B. These functions are used to compose the function Φ : (x, y) 7→ (a, c − d)where (a, b, c, d) = MD5Compress(φ(x, y), ψ(x, y)). When a birthday collision Φ(x, y) = Φ(x0 , y 0 )with φ(x, y) 6= φ(x0 , y 0 ) occurs, we have found message blocks which result in a δIHV of therequired form δa = 0 and δc = δd.
This more advanced strategy has not been tried, however we intend to construct anotherchosen-prefix collision using this strategy in future work. One can also optimize between birthdaycomplexity
and the number of required near-collision blocks. Finding a single birthday collisionpcosts π2 264 ≈ 233 compressions which is much more feasible compared to the previous birthday
search. One can easily extend the birthday search, as the cost for subsequent birthday collisions
decreases, to find collisions with fewer required near-collision blocks. An experimentation indicated that the cost of finding a collision requiring approx. 14 near-collision blocks is approx. 239
compressions.

7.5

Colliding Certificates with Different Identities

In March 2005 it was shown how Wangs collisions could be used to construct two different valid
and unsuspicious X.509 certificates with identical digital signatures [11]. These two colliding

36

7 CHOSEN-PREFIX COLLISIONS

certificates differed only in the two collision blocks which were hidden in the RSA moduli. In
particular, their Distinguished Name fields containing the identities of the certificate owners wereequal.
It would be interesting to be able to select Distinguished Name fields which are different andchosen at will, non-random and human readable as one would expect from these fields. This can berealized now as in our chosen-prefix collisions one can extend two arbitrarily chosen messages suchthat the extended message collide. To achieve identical digital signatures for X.509 certificates one
does not need to construct full certificates which collide under MD5, rather only the to-be-signed
parts of the certificates need to collide under MD5.
We have constructed such an example of colliding X.509 certificates with different Distinguished
Name fields where the suffixes Sb and Sc are hidden in the first half of the RSA moduli. The second
half of the RSA moduli was constructed as in [11] to complete the RSA moduli n1 and n2 in sucha manner that both are the product of two large primes and that the full certificates still collide
under MD5.
7.5.1

To-be-signed parts

The to-be-signed parts up to the first bit of the RSA moduli were carefully constructed to haveequal bitlength with the last block exactly 96 bits short of a full block. These to-be-signed parts
consist of several fields compliant with the X.509 standard and the ASN.1 DER encoding rules.
We actually constructed three chosen-prefixes to increase the probability that φ(x, y, z) 6=
φ(x0 , y 0 , z 0 ) when a birthday collision Φ(x, y, z) = Φ(x0 , y 0 , z 0 ) is found. Naturally we continued
with only two of the three chosen-prefixes after the birthday search. The three chosen-prefixes
have Distinguished Names ”Arjen K. Lenstra”, ”Marc Stevens” and ”Benne de Weger”, notatedas PAL , PMS and PBW respectively. The chosen-prefixes are given as bitstrings in Table D-1,
Table D-2 and Table D-3. Below we list all fields, and their values, which are contained in theencoded chosen-prefixes:
Field 1. X.509 version number: Version 3 and identical for all three certificates;
Field 2. Serial number: Different in each chosen-prefix:
PAL : 010c000116 ,PMS : 020c000116 ,PBW : 030c000116 ;Field 3. Signature algorithm: md5withRSAEncryption for all chosen-prefixes;
Field 4. Issuer Distinguished Name: The Certificate Authority (CA) and identical in eachcase:
CN (Common Name) = ”Hash Collision CA”,
L (Locality)= ”Eindhoven”,
C (Country)= ”NL”;
Field 5. Validity period: Our certificates have the same validity period:
Not before : Jan. 1, 2006, 00h00m01s GMT
Not after: Dec. 31, 2007, 23h59m59s GMT
Field 6. Subject Distinguished Name: The identities are different in the Common Name
(CN) and Organisation (O) fields for each certificate: (The organisation name is chosensuch that the CN and O fields together hold exactly 29 characters to meet the length requirements on the chosen-prefixes.)
PAL
PMS
CN = ”Arjen K. Lenstra” CN = ”Marc Stevens”
O = ”Collisionairs”
O=”Collision Factory”
L=”Eindhoven”
L=”Eindhoven”
C=”NL”
C=”NL”PBW
CN=”Benne de Weger”
O=”Collisionmakers”
L=”Eindhoven”
C=”NL”

7.5

Colliding Certificates with Different Identities

37

Field 7. Public key algorithm: rsaEncryption for all chosen-prefixes;
Field 8. RSA modulus: Only the length specifier of the RSA modulus is part of the chosenprefixes and is set to 8192 bits. The first byte after each chosen-prefix is also the first byteof the RSA modulus itself.
When we have found the RSA moduli we only need to complete the to-be-signed parts with thefollowing fields and compute the digital signature of the CA using the MD5 hash of the colliding
to-be-signed parts:
Field 9. RSA exponent: 01000116 = 65537;
Field 10. Version 3 extensions: We use default values for these extensions:
Basic Constraints : End Entity (not an CA), no limit on certification path length
Key Usage : Digital Signature, Non-Repudiation, Key Encipherment
7.5.2

Chosen-Prefix Collision Construction

Each of these chosen-prefixes consist of three full message blocks, resulting in some IHV3 , and one
partial message block R of 416 bits which is identical for all three prefixes. We denote the threedifferent IHV3 ’s as IHVAL , IHVMS and IHVBW for prefixes PAL , PMS and PBW , respectively.
There is very limited space in a RSA modulus of 8192 bit and we also need enough freedom tocomplete the RSA moduli as a product of two large primes. Therefore we chose to use the original
birthday search in subsection 7.2.
Given the three IHV ’s and R we defined the pseudo-random walk in the 96-bit search spaceas follows: IHVAL , if x = 0 mod 3;
IHVMS , if x = 1 mod 3;
φ(x, y, z) =
IHVBW , if x = 2 mod 3.
ψ(x, y, z)
ρ(IHV ) = ρ(a, b, c, d)Φ(x, y, z)= Rkxkykz= (a, d − b, d − c)= ρ(MD5Compress(φ(x, y, z), ψ(x, y, z)))So given a 96-bit value (x, y, z) we use it to complete the message block R, determine which IHV3
to use and compute the resulting IHV4 . We map this IHV4 = (a, b, c, d) to the 96-bit search
space as (a, d − b, d − c) as then a collision implies δa = 0, δb = δc = δd. We used the method of
distinguished points to parallelize the birthday search where we defined the set of distinguishedpoints as:
S = {(x, y, z) | (x ≡ 0 mod 215 ) ∧ (RL(y, 15) ≡ 0 mod 215 )}.
Our birthday search resulted in a total of 120 collisions of which 80 were useful (different
IHV ’s). We chose the following birthday collision as it requires only 8 near-collisions to eliminate
the resulting δIHV4 :(X, Y, Z) = (cbb4091a16 , 7a26c74016 , 9b7f01af16 )(X 0 , Y 0 , Z 0 ) = (d6e773ee16 , ba4fb3b316 , 023d39a116 )This birthday collision gives us birthday bitstrings Sb = XkY kZ and Sb0 = X 0 kY 0 kZ 0 which areappended to PMS and PAL , respectively, as φ(X, Y, Z) = IHVMS and φ(X 0 , Y 0 , Z 0 ) = IHVAL . The
extended chosen-prefixes PMS kSb and PAL kSb0 consist of exactly four message blocks and result inδIHV4 = (0, δb4 , δb4 , δb4 ) whereδb4 = −25 − 27 − 213 + 215 − 218 − 222 + 226 − 230 .

38

7 CHOSEN-PREFIX COLLISIONS

We eliminated these bitdifferences in δIHV4 with 8 consecutive near-collision blocks based on the
differential path in Table 7-1.
As outlined before, we construct a full differential path starting with IHV4 and IHV40 andusing Table 7-1 with δm11 = +220 to eliminate −230 in δb4 . The differential path we have found isshown in Table D-6 in the Appendix. The near-collision blocks M5 , M50 satisfying this differential
path and the resulting IHV5 , IHV50 that we have found are shown in Table D-7. The other
differences were eliminated similarly using the values −216 , +212 , +28 , −25 , +23 , +229 and +227
for δm11 in that order. The differential paths we have constructed using these values for δm110
and the near-collision blocks M6 , M60 , . . . , M12 , M12
we found which satisfying them are shown in
Tables D-8 up to D-21.
The birthday bitstrings Sb , Sb0 and the 8 near-collisions blocks together form Sc , Sc0 and are
the 96 + 8 × 512 = 4192 most-significant bits of the RSA moduli. Using the method describedin [11] we have found a bitstring Sm such that Sb kSc kSm and Sb0 kSc0 kSm form RSA moduli n1
and n2 , respectively, as products of two large primes. The bitstring Sm and the smallest primes
dividing n1 and n2 are given in the Appendix in Table D-24 and Table D-25.
We completed the to-be-signed parts using identical suffixes for both messages (including Sm )after the chosen-prefix collision PMS kSb kSc and AL kSb0 kSc0 , hence the resulting to-be-signed parts
collide under MD5. These certificates have identical signatures and can be found at our website:
http://www.win.tue.nl/hashclash/TargetCollidingCertificates/.
7.5.3

Attack Scenarios

Though our colliding certificates construction involving different identities should have more attack potential than the one with identical identities in [11], we have not been able to find truly
convincing attack scenarios. The core of PKI is to provide a relying party with trust, beyond
reasonable cryptographic doubt, that the person belonging to the identity in the certificate has
exclusive control over the private key corresponding to the public key in the certificate. Ideally, a
realistic attack should attack this core of PKI and also enable the attack to cover his trails.
However, our construction requires that the two colliding certificates are generated simultaneously. Although each resulting certificate by itself is completely unsuspicious, the fraud becomesapparent when the two certificates are put alongside, as may happen during a fraud analysis.
Another problem is that the attacker must have sufficient control over the CA to predict all
fields appearing before the public key, such as the serial number and the validity periods. It has
frequently been suggested that this is an effective countermeasure against colliding certificate constructions in practice, but there is no consensus how hard it is to make accurate predictions. When
this condition of sufficient control over the CA by the attacker is satisfied, colliding certificates
based on chosen-prefix collisions are a bigger threat than those based on random collisions.
Obviously, the attack becomes effectively impossible if the CA adds a sufficient amount of fresh
randomness to the certificate fields before the public key, such as in the serial number (as somealready do, though probably for different reasons). This randomness is to be generated after theapproval of the certification request. On the other hand, in general a relying party cannot verify
this randomness. In our opinion, trustworthiness of certificates should not crucially depend onsuch secondary and circumstantial aspects. On the contrary, CAs should use a trustworthy hashfunction that meets the design criteria. Unfortunately, this is no longer the case for MD5.

7.6

Other Applications

7.6.1

Colliding Documents

Entirely different abuse scenarios are also possible. In [2] it was shown how to construct a pair of
PostScript files which collide under MD5, and that show different messages to output media suchas screen or printer. Similar constructions for several other document formats are presented in[5]. However, in those constructions both messages had to be hidden in each of the colliding files,
which obviously raises suspicions upon inspection at bit level.

7.6

Other Applications

39

This can be avoided using chosen-prefix collisions. For example, two different messages can beentered into a document format which allows insertion of color images (such as PostScript, Adobe
PDF, Microsoft Word), with one message per document. Each document can be constructedcarefully with at the last page a color image containing constructed birthday and near-collision
bitstrings such that the documents collide under MD5. The image itself can be a short one pixel
wide line, or hidden inside a layout element, a company logo, or in the form of a nicely coloredbarcode claiming to be some additional security feature, obviously offering far greater security
than those old-fashioned black and white barcodes.
Figure 1: The example chosen-prefix collision built into bitmap images.

In Figure 1 the actual 4192-bit collision-causing appendages computed for the certificates arebuilt into bitmaps to get two different barcode examples. Each string of 4192 bits leads to one
line of 175 pixels, say A and B, and the barcodes consist of the lines ABBBBB and BBBBBB
respectively. Apart from the 96 most significant bits corresponding to the 4 pixels in the upper
left corner, the barcodes differ in only a few bits, which makes the resulting color differences hardto spot for the human eye.
7.6.2

Misleading Integrity Checking

In [14] and [7] it was shown how to abuse existing MD5 collisions to mislead integrity checking software based on MD5. Similar to the colliding Postscript applications, they also used the differencesin the colliding inputs to construct deviating execution flows of some programs.
Here too, chosen-prefix collisions allow a more elegant approach, especially since common operating systems ignore any random bitstring when appended to an executable: such a program
will run unaltered. Thus one can imagine constructing a chosen-prefix collision for two executables: a ‘good’ program file named Word.exe and a ‘bad’ one named Worse.exe. The resulting
altered files, say Word2.exe and Worse2.exe, have the same MD5 hash value and are functionallyequivalent to the original files. The altered ‘good’ program Word2.exe can then be offered to a
executable signing authority (e.g. a software publisher) and receive an ’official’ MD5 based digital
signature from the publisher. This signature will be equally valid for the attacker’s Worse2.exe
which the attacker might be able to place on an appropriate download site.
This construction affects a common functionality of MD5 hashing and may pose a practicalthreat.
7.6.3

Nostradamus Attack

In [8] the authors present a strategy to commit to a certain hash value and afterwards construct
a document, which hashes to the committed hash value, containing an arbitrary message fasterthan a trivial pre-image attack. The main idea is to construct a tree-structure with a root node
IHVk+d and 2d end nodes IHVk,j where for each node IHVk+i,j there is a known message block
Bk+i,j resulting to its parent node. Hence, starting from any node IHVk+i,j there is a known
suffix consisting of message blocks Bk+i,j , Bk+i+1,j 0 , . . . resulting in the root node IHVk+d .
Starting from an arbitrary message one can brute force search for an extended message which
results in some node of this tree. Further extending this message with message blocks Bk+i,j
results in the root node IHVk+d . Hence, one can commit to the hash value IHVk+d and afterwards
construct a document containing an arbitrary message resulting in this hash value. The complexityof this attack depends on the number of nodes 2d , constructing the tree-structure costs approx.
2(n+d)/2+2 compressions (where n = 128 is the bit length of the MD5 hash value) and finding
the extended message resulting in some node costs approx. 2n−d compressions. This attack is notpractical as the total cost is at least 286 compressions.

40

7 CHOSEN-PREFIX COLLISIONS

A variant of this attack is now feasible using chosen-prefix collisions. Suppose we have r
messages and we want to commit to a certain hash value without committing to one of themessages specifically. Using r − 1 chosen-prefix collisions we can construct r documents containing
these r messages all with the same hash value. When committing to this hash value, afterwards
we can still show any one of the r documents to achieve some malicious goal. E.g. predicting thenext European Soccer Champion in a bet with large winnings.
This is the only attack we could think of where fraud cannot be revealed, as only one of thecolliding messages is made public and there is no other message to hold it against to reveal fraud.

7.7

Remarks on Complexity

The amount of work required to construct a chosen-prefix collision is hard to estimate, since it isdifficult to estimate the complexity for constructing the differential paths involved and finding theactual near-collision blocks. However, in our example construction of colliding certificates the work
we spent in our birthday search outweighed by far the amount of work we spent in constructing
the 8 differential paths and finding the actual near-collisions blocks.
Our chosen-prefix example was constructed in about 252 compressions, which is much fasterthan the brute-force approach of about 264 compressions. One can do even better using theimproved birthday search, however this has not been tried yet.

8 Project HashClash using the BOINC framework

841

Project HashClash using the BOINC framework

For this work we maintained the project HashClash at http://boinc.banaan.org/hashclash/which is a distributed computing project based on the BOINC framework. BOINC is a software
platform for distributed computing using volunteer computer resources. Each project can operatecompletely on its own and can present work through its servers. Anybody can then use a BOINC
client to register with the project. The BOINC client will then fetch, process and return workunitsof the project while maintaining a background profile, i.e. as a screensaver, on the volunteer’s
computer. A project can customize the whole BOINC framework to its own needs, whereas thevolunteer can use a standard BOINC client independent of the projects it wants to join.
A BOINC project consists of a database, data server(s), scheduling server(s), a web interface
and the project backend possibly all on the same physical server as in the case of our project
HashClash. The project backend is used to insert applications and workunits into the BOINC
project and to receive and process returned workunits. The files of the applications and workunits
are then stored on the data servers. The database contains all information about the applications,workunits, participants, participants computers and (un)returned results and is maintained by the
project backend and scheduling server(s).
When a participants computer connects to the BOINC project it will use a scheduling server
to request work. The scheduling server will then assign one or more workunits (if available) to thecomputer, after which the BOINC client will download the application and workunit files neededfrom the data servers. When the participants computer finishes computing a workunit it will
upload all result files to the data servers and report to a scheduling server that it has finished andpossibly requesting new work.
In return for the volunteered cpu-cycles the project maintains a credit system. The volunteers
can compete with other users with their credit gained by donating cpu-cycles and even grouping
into teams is possible. This creates a situation in which volunteers driven by competition want todonate more cpu-cycles.
Currently, there are 2752 registered volunteers most of which are part of one of the 417 teams,
running a total of 8686 pc’s. At its peak, the combined effort of these volunteers was about 400
Gflops. The project HashClash volunteers community was quite active and even requested for the
HashClash logo competition we held (see http://boinc.banaan.org/hashclash/logos.php).
Using project HashClash we performed the birthday search, as shown in subsubsection 7.5.2
for our chosen-prefix collision example, by sending out workunits that generate a birthday trail
starting from a given random startpoint and ending in a distinguished point. Locally, we calculated
the actual collisions when two trails ending in the same distinguished point were found.
On our projects webpage we maintained a list of all found collisions and for each the two users
who generated the two trails involved, whether it was useful (different IHV3 ’s) and how manynear-collision blocks are required to eliminate the resulting δIHV4 .
In the second phase of our project we used project HashClash to distribute the work involved
in finding a full differential path by connecting a lower and upper differential path given large setsof each. Using the Elegast cluster we precomputed these large sets of lower and upper differential
paths and performed the collision finding when a full differential path was found.

42

99 CONCLUSION

Conclusion

This work presented several results related to constructing collisions for MD5. We have presented
three improvements speeding up the attack by Wang et al. and also MD5 collision finding in
general, namely a method to find Qt bitconditions which satisfy Tt restrictions [21], five new
differential paths to be used together with Wang’s original differential paths, and our near-collision
search algorithm which uses Klima’s tunnels.
Together these improvements allow us to find Wang-type collisions for MD5 in approx. 224.8
compressions or approx. 10 seconds on a 2.6Ghz Pentium4 for random IV ’s, here IV is the IHV
used to compress to first collision block. Note that the number of compressions we show here are
the work-equivalent of finding collisions instead of simply the number of different message blocks
we’ve tried, i.e. we can find collisions on average as fast as computing approx. 224.8 compressions.
If we restrict ourselves to using recommended IV ’s (see subsection 5.2) and the MD5 IV = IHV0
we can find collisions in even approx. 224.1 compressions (6.2 seconds) and 223.5 compressions (4.2
seconds), respectively. This is a large improvement over the original attack (which took approx.
239 compressions using the MD5 IV ) and earlier improvements where finding a single collision
could take several hours on such a pc. The method of Klima [10] using tunnels is a bit slower
than ours taking approx. 226.3 compressions (28 seconds) to find collisions using the MD5 IV (theeasiest case). Our earlier paper [21] (containing the improvements on satisfying Tt restrictions,our first collision finding algorithms (see Algorithms 5.1 and 5.2) and the notion of recommended
IV ’s) was submitted to the IACR Cryptology ePrint Archive and parts of this paper were used in
the book [20].
Furthermore, we presented the first automated way to construct differential paths for MD5
and showed its practicality by constructing several new differential paths (see Appendix). As
mentioned above, five differential paths to speed up finding Wang-type collisions, and anothereight were used in the next result.
Our most significant result is the joint work with Arjen Lenstra and Benne de Weger [22], where
we have shown how to use our differential path construction method to build chosen-prefix collisions. Starting with two arbitrary different messages M , M 0 , a chosen-prefix collision consists ofthese messages extended with constructed suffixes S, S 0 such that M D5(M kS) = M D5(M 0 kS 0 ).
Hence, chosen-prefix collisions allow more advanced abuse scenarios than Wang-type collisions
where the only difference between colliding messages is contained in two random looking blocks.
To show that chosen-prefix collisions for MD5 are feasible, we have constructed an example chosenprefix collision consisting of two X.509 certificates with different identities but identical signatures.
Our construction required substantial cpu-time, however chosen-prefix collisions might be constructed much faster by using the improved birthday search (see subsection 7.4) and allowing
more near-collision blocks (about 14). Our joint work [22] was accepted at EuroCrypt 2007 andhas been chosen by the program committee to be one of the three notable papers which wereinvited to submit their work to the Journal of Cryptology.
As part of this research we maintained the HashClash project, which is a distributed computing
project using the BOINC framework. Volunteers all over the world could join our project anddonate idle cpu-cycles to process computational jobs. The amount of volunteers joining our project
and their enthusiasm was unexpected. Within the HashClash community we even held a logodesigning contest upon their request. It appears that the BOINC community is enthusiastic to help
further such cryptography related projects, even without a good understanding of the underlying
theory. With literally thousands of pc’s working for our project (even if only for a small fractionof their time), we completed our chosen-prefix collisions much faster than we would have without
them.

REFERENCES

43

References[1] Ivan Damgård, A design principle for hash functions, CRYPTO 1989 (Gilles Brassard, ed.),
LNCS, vol. 435, Springer, 1989, pp. 416–427.
[2] M. Daum and S. Lucks, Attacking hash functions by poisoned messages, the story of alice andher boss, http://www.cits.rub.de/MD5Collisions/.
[3] Bert den Boer and Antoon Bosselaers, Collisions for the compression function of MD5, EUROCRYPT 1993 (Tor Helleseth, ed.), LNCS, vol. 765, Springer, 1993, pp. 293–304.
[4] Hans Dobbertin, Cryptanalysis of MD5 compress, 1996, presented at the rump session ofEurocrypt’96.
[5] M. Gebhardt, G. Illies, and W. Schindler, Note on practical value of single hashcollisions for special file formats, NIST First Cryptographic Hash Workshop, 2005,
http://csrc.nist.gov/pki/HashWorkshop/2005/Oct31_Presentations/Illies_NIST_05.pdf.
[6] Philip Hawkes, Michael Paddon, and Gregory G. Rose, Musings on the Wanget al. MD5 collision, Cryptology ePrint Archive, Report 2004/264, 2004,
http://eprint.iacr.org/2004/264.
[7] D. Kaminsky, MD5 to be considered harmful someday, Cryptology ePrint Archive, Report
2004/357, 2004, http://eprint.iacr.org/2004/357.
[8] John Kelsey and Tadayoshi Kohno, Herding hash functions and the nostradamus attack, EUROCRYPT 2006 (Serge Vaudenay, ed.), LNCS, vol. 4004, Springer, 2006, pp. 183–200.
[9] Vlastimil Klima, Finding MD5 collisions on a notebook PC using multi-message modifications,
Cryptology ePrint Archive, Report 2005/102, 2005, http://eprint.iacr.org/2005/102.
[10] Vlastimil Klima, Tunnels in hash functions: MD5 collisions within a minute, Cryptology
ePrint Archive, Report 2006/105, 2006, http://eprint.iacr.org/2006/105.
[11] Arjen K. Lenstra and Benne de Weger, On the possibility of constructing meaningful hashcollisions for public keys, ACISP 2005 (Colin Boyd and Juan Manuel González Nieto, eds.),
LNCS, vol. 3574, Springer, 2005, pp. 267–279.
[12] Jie Liang and Xuejia Lai, Improved collision attack on hash function MD5, Cryptology ePrint
Archive, Report 2005/425, 2005, http://eprint.iacr.org/2005/425.
[13] Ralph C. Merkle, One way hash functions and DES, CRYPTO 1989 (Gilles Brassard, ed.),
LNCS, vol. 435, Springer, 1989, pp. 428–446.
[14] Ondrej Mikle, Practical attacks on digital signatures using MD5 message digest, Cryptology
ePrint Archive, Report 2004/356, 2004, http://eprint.iacr.org/2004/356.
[15] Jamer A. Muir and Douglas R. Stinson, Minimality and other properties of the width-w
nonadjacent form, Mathematics of Computation, vol. 75, 2006, pp. 369–384.
[16] National Information Standards Organisation, FIPS PUB 180-1: Secure hash standard, April
1995, http://www.itl.nist.gov/fipspubs/fip180.htm.
[17] R.L. Rivest, The MD5 Message-Digest algorithm, Internet RFC, April 1992, RFC 1321.
[18] Yu Sasaki, Yusuke Naito, Noboru Kunihiro, and Kazuo Ohta, Improved collision attack on MD5, Cryptology ePrint Archive, Report 2005/400, 2005,
http://eprint.iacr.org/2005/400.

44

REFERENCES[19] Yu Sasaki, Yusuke Naito, Jun Yajima, Takeshi Shimoyama, Noboru Kunihiro, and Kazuo
Ohta, How to construct sufficient condition in searching collisions of MD5, Cryptology ePrint
Archive, Report 2006/074, 2006, http://eprint.iacr.org/2006/074.
[20] Mark Stamp and Richard M. Low, Applied cryptanalysis, Wiley, 2007.
[21] Marc Stevens, Fast collision attack on MD5, Cryptology ePrint Archive, Report 2006/104,
2006, http://eprint.iacr.org/2006/104.
[22] Marc Stevens, Arjen Lenstra, and Benne de Weger, Chosen-prefix collisions for MD5 andcolliding X.509 certificates for different identities, EUROCRYPT 2007 (Moni Naor, ed.),
LNCS, vol. 4515, Springer, 2007, pp. 1–22.
[23] Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic
applications, Journal of Cryptology 12 (1999), no. 1, 1–28.
[24] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, Collisions for hash functions
MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive, Report 2004/199, 2004,
http://eprint.iacr.org/2004/199.
[25] Xiaoyun Wang and Hongbo Yu, How to break MD5 and other hash functions, EUROCRYPT
2005 (Ronald Cramer, ed.), LNCS, vol. 3494, Springer, 2005, pp. 19–35.
[26] Jun Yajima and Takeshi Shimoyama, Wang’s sufficient conditions of MD5 are not sufficient,
Cryptology ePrint Archive, Report 2005/263, 2005, http://eprint.iacr.org/2005/263.

REFERENCES

45

46

A

A MD5 CONSTANTS AND MESSAGE BLOCK EXPANSIONMD5 Constants and Message Block Expansion
Table A-1: MD5 Addition and Rotation Constants and message block expansion.
t
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ACt
d76aa47816
e8c7b75616
242070db16
c1bdceee16f57c0faf164787c62a16
a830461316
fd46950116
698098d816
8b44f7af16
ffff5bb116
895cd7be16
6b90112216
fd98719316
a679438e16
49b4082116

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

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

t
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

ACt
f61e256216
c040b34016
265e5a5116
e9b6c7aa16
d62f105d16
0244145316
d8a1e68116
e7d3fbc816
21e1cde616
c33707d616
f4d50d8716
455a14ed16
a9e3e90516
fcefa3f816
676f02d916
8d2a4c8a16

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

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

t
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

ACt
fffa394216
8771f68116
6d9d612216
fde5380c16
a4beea4416
4bdecfa916
f6bb4b6016
bebfbc7016
289b7ec616
eaa127fa16
d4ef308516
04881d0516
d9d4d03916
e6db99e516
1fa27cf816
c4ac566516

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

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

t
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

ACt
f429224416
432aff9716
ab9423a716
fc93a03916
655b59c316
8f0ccc9216
ffeff47d16
85845dd116
6fa87e4f16
fe2ce6e016
a301431416
4e0811a116
f7537e8216
bd3af23516
2ad7d2bb16
eb86d39116

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

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

A MD5 Constants and Message Block Expansion

47

48

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B

Differential Paths for Two Block Collisions

B.1

Wang et al.’s Differential Paths
Table B-1: Wang et al.’s first block differential

t
0−3
4
5
6
7

δm4 = +231 ,δm11 = +215 ,δm14 = +231 ,∆Qt(BSDR of δQt )

δFt

δwt

δTt

RCt

−
231
−
−
−

·
7
12
17
22

−

−
231
211 +219−210 −214−22 +25 +210
+216 −225 −227
28 +210 +216
−224 +231
20 −220 +226

−
215
−
−
231
−
−
−
215
−
−
−
−
231
−
231

213 −227−28 −217 −223
20 +26 +217
−212
18
2 −230−27 −213 +225
224
−
23
−229
−
−
217
−
−
−

17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

δmi = 0, i ∈/ {4, 11, 14}9−−+26 . . . +221 , −222
−26 +223 +231
0
+2 . . . +24 , −25 , +26 . . . +210−211 , −223 . . . −225 , +226 . . . +231
+20 +215 −216 +217
+218 +219 −220 −223
−20 +21 +26 +27 −28 −231

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

−212 +213 +231
+230 +231
7
8+2 −2 , +213 . . . +218 , −219 +231
−224 +225 +231
+231
3
+2 −215 +231
−229 +231+231+231+217 +231
+231
+231
+231
−
−
−

−
−
211 +219−210 −214−22 +25 +210
+216 −225 −227
26 +28 +210
+216 −224 +231
20 +26 −220
−223 +226 +231
20 +26 +213 −223
−20 −28
7
2 +217 +231
−213 +231
218 +231
225 +231
231
231
231
231
231
231
231
−
231
−

26 − 33

−

−

−

−

·

15

15

8

−

7
12

34
35
36
37
38 − 4950
51 − 59
60−
δQ35 = 231
δQ36 = 231
δQ37 = 231
δQt = 231
δQ50 = 231
δQt = 231
δQ60 = 231

−
231
−
231
231
−
231
−

2
231
−
231
−
231
−
231

2
−
−
−
−
−
−
−

16
23
4
11
·
15
·
6

61
62
63
64

δQ61 = 231
δQ62 = 231 +225
δQ63 = 231 +225
δQ64 = 231 +225

231
231
231
×

215
−
−
×

215
−
−
×

10
15
21
×

B.1

Wang et al.’s Differential Paths

49

Table B-2: Wang et al.’s second block differential
δm4 = −231 ,δm11 = −215 ,

t

∆Qt

−3
−2
−1
0
1
2
3

+231
+225 +231−225 +226 +231
+225 +231+225 +231+25 +225 +231
5
−2 −26 +27 −211 +212
−216 . . . −220 , +221
−225 . . . −229 , +230 +231
+21 +22 +23 −24 +25−225 +226 +231
+20 −26 +27 +28 −29−210 −211 +212 +231
+216 −217 +220 −221 +231

4
5
6

(BSDR of δQt )δm14 = −231 ,δmi = 0, i ∈/ {4, 11, 14}

δFt

δwt

δTt

RCt

×
×
×
231
231
225
11
−2 −221 +225
−227 +231

×
×
×
−
−
−
−

×
×
×
−
225
231 +226
11−2 −221 −226

×
×
×
7
12
17
22

21 −23 −218
+226 +230−24 −25 −28 −220
−225 −226 +228 +230
23 −25 −210 −211
−216 −221 −225
216 −227 +231

231

21 +22 −218
+225 +226 +230
−24 −28 −220
−226 +228 −230
23 −210 −221 −231

7

−26 +216 +225−

20 +216 −226 +231
26 +231231
17
2 +231−213 +231
218 +230−225 +231
231
231
231
231
231
231
231
−
231
−

−
−
−215
−
−
231
−
−
−
−215
−
−
−
−
231
−
231

−
−

17

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

+26 +27 +28 −29+227 −228 +231
−215 +216 −217 +223
+224 +225 −226 +231
0−2 +21 , −26 . . . −28 , +29 +231
+212 +231+231
7
13−2 , +2 . . . +218 −219 +231
−224 . . . −229 , +230 +231
+231
3
+2 +215 +231
−229 +231+231+231+217 +231
+231
+231
+231
−
−
−

26 − 33

−

−

−

−

·

34
35
36
37
38 − 4950
51 − 59
60−
δQ35 = 231
δQ36 = 231
δQ37 = 231
δQt = 231
δQ50 = 231
δQt = 231
δQ60 = 231

−
231
−
231
231
−
231
−

−215
231
−
231
−
231
−
231

−215
−
−
−
−
−
−
−

16
23
4
11
·
15
·
6

61
62
63
64

δQ61 = 231
δQ62 = 231 − 225
δQ63 = 231 − 225
δQ64 = 231 − 225

231
231
231
×

−215
−
−
×

−215
−
−
×

10
15
21
×

7
8

−

−21 +25 +216
+225 −227
20 +28 +29+216 +225 −231
20 −220 −226
−227
−217 −223
20 +26 +217
−212
18
2 +230−27 −213 −225
224
−
23
−229
−
−
217
−
−
−

12

22
7
12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

50

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B.2

Modified Sufficient Conditions for Wang’s Differential Paths
Table B-3: Modified first block bitconditions
t
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 − 45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

Conditions on Qt : b31 . . . b0........ ....0... ....0... .0......
1....... 0^^^1^^^ ^^^^1^^^ ^011....
1000100. 01..0000 00000000 0010.1.1
0000001^ 01111111 10111100 0100^0^100000011 11111110 11111000 00100000
00000001 1..10001 0.0.0101 01000000
11111011 ...10000 0.1^1111 00111101
0111.... 0..11111 1101...0 01....00
0010.... ....0001 1100...0 11....10000...^^ ....1000 0001...1 0.......
01....01 ....1111 111....0 0...1...
0.0...00 ....1011 111....1 1...1...
0.1...01 .......0 1....... ....0...
0!1..... ......!. ........ ........
0!...... ......0. ^....... ....^...
0.^..... ......1. ........ ........
0....... ......0. ........ ........
0....... .....!.. ........ ........
0....... ......^. ........ ........
0....... ........ ........ ........
0....... ........ ........ ........
1....... ........ ........ ........
Sub-total # conditions........ ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
........ ........ ........ ........
Sub-total # conditions
Sub-total # IV conditions from 2nd block
Total # conditions
Note: I, J, K ∈ {0, 1} and K = I.

#3
19 + 222 + 532
32
28
28
17 + 215 + 214 + 1
14
14
6+1
2+2
4+1
3
2
1+1
2
1
1
1
278
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
16
8
302

B.2

Modified Sufficient Conditions for Wang’s Differential Paths

Table B-4: Modified second block bitconditions
t
−2
−1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 − 45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

Conditions on Qt : b31 . . . b0
A.....0. ........ ........ ........
A....01. ........ ........ ........
A....00. ........ ........ ..0.....
Total # IV conditions for 1st block
B...010. ..1....0 ....0... .10.....
B^^^110. ..0^^^^0 1..^1... ^10..00.
B011111. ..011111 0..01..1 011^^11.
B011101. ..000100 ...00^^0 0001000^
A10010.. ..101111 ...01110 01010000
A..0010. 1.10..10 11.01100 01010110
B..1011^ 1.00..01 10.11110 00.....1
B..00100 0.11..10 1.....11 111...^0
B..11100 0.....01 0..^..01 110...01
B....111 1....011 11001.11 11....00
B....... ....^101 11000.11 11....11B^^^^^^^ ....1000 0001.... 1.......
A0111111 0...1111 111..... 0...1...
A1000000 1...1011 111..... 1...1...
01111101 ........ 00...... ....0...
0.10.... ......!. ........ ........
0!...... ......0. ^....... ....^...
0.^..... ......1. ........ ........
0....... ......0. ........ ........
0....... .....!.. ........ ........
0....... ......^. ........ ........
0....... ........ ........ ........
0....... ........ ........ ........
1....... ........ ........ ........
Sub-total # conditions........ ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
K....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
I....... ........ ........ ........
J....... ........ ........ ........
........ ........ ........ ........
Sub-total # conditions
Total # conditions

#
(1)
(3)
(4)
(8)
8+1
20 + 123 + 1
26
25
24 + 120 + 118 + 117 + 118 + 115 + 117
17 + 117 + 1
10 + 1
2+2
4+1
3
2
1
2
1
1
1
307

Note: A, B, I, J, K ∈ {0, 1} and B = A, K = I.

0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
16
323

51

52

B.3

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONSNew First Block Differential Path
Table B-5: New first block differential patht

∆Qt

(BSDR of δQt )

0−3
4
5

−
−
−26 . . . −224 +225

6

+20 −21 +23 −24+25 −26 −27 +28 +220
+221 −222 +226 −231
−26 +231

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

−20 +23 −26 −215
−222 +228 +231
+20 −26 +212 +231
−212 +217 +231
−212 +218 −224
+229 +231
7−2 −213 +224 +231
+224 +231+229 +231+23 −215 −231
−229 −231−231−231+217 −231
−231
−231
−231
−
−
−

δFt

δwt

δTt

RCt

−
−
−28 +214 −219
−223 +225
23 −29 +215
+218 −220 −222

−
231
−

−
231
−28 +214 −219
−223 +225
23 −29 +215
+218 −220 −222·
7
12

−20 +26 −210
+213 −225−25 +28 +215
−221 +226 −228
−20 +23 −26 +231
20 −26 +212 +231
20 −26 −217
−229 +231
27 −212 +231
231
24
2 +229 +231
224 +231
231
29−2 +231
231
231
231
231
231
−
231
−

−

−20 +26 −210
+213 −225
25 +28 +215
−221 +226 −228
−21 +25 −220 +226
20 −27 +212
23 −27 −217
−222 −228
20 +26−212 +217−212 +218 −230
−27 −213 +225
224
−
23
−229
−
−
217
−
−
−

22

−

−
−
−
215
−
−
231
−
−
−
215
−
−
−
−
231
−
231

17

7
12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

B.3

New First Block Differential Path

53

Table B-6: New first block conditions
t
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Conditions on Qt : b31 . . . b0.......1 .1111... .1....01 11......
0.....^0 ^0000^^^ ^0^^^^10 11..0...
01...^01 11111111 11111111 11^^1.^^
10.1.000 01001011 10000010 11010.10
0..0.010 01000000 00011011 .1000.11
0!.0.0.. .101.... 1..1...0 11010.11
0!10...0 .0...1^. 0..0.... 011.1..0
0.01...0 .1...00. 1..1.... 1...1..1
0!0....1 .....01. ..^1.... 00.....0
0!0....0 ..!..01. ..1..... 1.......
0.1....0 .....1.. 1.01.... 0...1...
0!0..... ........ 1.1..... 1...1...
1.0....0 .......! 1....... ....0...
1!1..... ......!. ........ ........
1!...... ......0. ^....... ....^...
1.^..... ......1. ........ ........
1....... ......0. ........ ........
1....... .....!.. ........ ........
1....... ......^. ........ ........
1....... ........ ........ ........
0....... ........ ........ ........
1....... ........ ........ ........
Subtotal # conditions

#
10
22
28
29
27
17
15
12
11
9
9
7
6
4
5
3
2
2
2
1
1
1
223

54

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B.4

New Second Block Differential Paths

B.4.1

New Second Block Differential Path nr. 1

Table B-7: New second block differential path nr. 1
t
−3
−2
−1
0
1
2
3
4

∆Qt

(BSDR of δQt )
31

δFt

δwt

δTt

RCt

×
×
×
−
−
−
−
231

×
×
×
225
226
226
0
2 −211 +226
21 −26 +28+211 −216 −222
−226 +231
1
2 +23 +25 +27+211 +216 +219
+222 −229 +231
−23 −25 −28 +210
−212 +215 −217
−221 +223 +228
1
−2 +23 −25 +28 +210
−213 +216 +218 −223
+225 +227 −229
1
−2 −28 −210 +212 +216
−218 −221 −225
−227 +229 +231
20 +220 −222 +226
−21 +27 +213 −227 −229
−23 +28 +217 −219
−223 +225 +228
−20 +22 −26
212
14−2 −218 +230
27 −29 +213 −225
−224
−
−23
229
−
−
−217
−
−
−

×
×
×
7
12
17
22
7

8

−23 +28 +215 +217
−219 −223 +225 +228

×××
225 +231
225 +231
225 +23102 −211 +225 +231
20 −26 +28 +211
−216 −222 +225
−227 +231
0
2 +23 −25 +27+211 +216 +219
+222 −225 −229
−20 −23 +25 +27 +29+211 −213 +215 −217 −221
+223 −225 +228 +231
−20 +23 +25 +27 −210
−213 +218 +222 −224
+227 −229 +231
0
2 +29 +213 −215 −219
+221 +226 −228 +230

9
10
11

−20 +22 −26+212
14−2 −218 +224 +230

−20 +28 −223 +225 +228
−20 −26 +28
−

−
−
−215

12
13
14
15
16
17
18
19
20
21
22
23
24
25

+27 −29 +213 −224 −231
−224 −231−231−23 +215+229 −231−231+231−217 +231
+231
+231
+231
−
−
−

−
−
−224 +231−224 +231
231
231
−
231
231
231
231
−
231
−

−
−
231
−
−
−
−215
−
−
−
−
231
−
231

5

6

7

+2
+225 +231+225 +231+225 +231+20 +225 +231
+20 +26 +225 +231
+20 +26 +211 +225 +231
+20 −21 −26 −27+28 +211 +216 +222
−225 −226 +227 +231
+20 +22 +23 +24 −25 +28+211 −213 −215 −217 +219
+222 +223 +224 +229 +230
+21 +28 . . . +217 −218
−220 +221 −222 −223 −224
+226 +228 +229 +230 +231
−20 −26 +213 −227 −229

−

−

−

−

12

17

22

7

12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

B.4

New Second Block Differential Paths

55

Table B-8: New second block conditions nr. 1tConditions on Qt : b31 . . . b0
−2 ......0. ........ ........ ........
−1 ^.....0. ........ ........ .......1
0 ^.....0. ........ ........ .1.....1
Total # IV conditions for 1st block1 ^.....0. ........ ....1... .1!....0
2 ^...1.0. .1.....1 ....0..0 00.....0
3 ^00.0^00 00..0.10 1.1.0..1 101.0.^0
4 01100110 000.1.10 1.1.0.00 110^1^10
5 .0010100 001^0^11 1^1^0^10 00100000
6 ^0001001 11010100 00000000 01011000
7 0.111001 01001011 1101.100 .1011011
8 10100001 11011000 01.11100 .00.1001
9 .1111.10 1...0.0. 0.11...1 .11.00.1
10 1111..10 1...1^1. 1^.0...0 .1..10.1
11 100....0 .....1.! .1^0..^. ^1...1.1
12 .01....1 ..!..0.. .001..1. 0.......
13 ^1.....1 .....1.. 110...0. 0...1...
14 100..... ........ 1.1...1. 1...1...
15 001....0 .......! 0....... ....1...
16 1!0..... ......!. ........ ........
17 1!...... ......0. ^....... ....^...
18 0.^..... ......1. ........ ........
19 0....... ......1. ........ ........
20 0....... .....!.. ........ ........
21 0....... ......^. ........ ........
22 0....... ........ ........ ........
23 0....... ........ ........ ........
24 1....... ........ ........ ........
Subtotal # conditions

#
(1)
(3)
(4)
(8)
6
10
22
27
31
32
29
29
18
18
14
10
10
8
7
4
5
3
2
2
2
1
1
1
292

56

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B.4.2

New Second Block Differential Path nr. 2

Table B-9: New second block differential path nr. 2
t
−3
−2
−1
0
1
2
3
4

5

6

7

∆Qt

(BSDR of δQt )31+2+225 +231+225 +231+225 +231+20 +225 +231
+20 +26 +225 +231
+20 +26 +211
+217 +225 +231
0−2 −21 +22 −26 −27 +28−211 −212 +213 −216 −218
+219 +222 −225 +226 +231
+20 −22 −23 −24 +25−28 −210 −212 +214 −215
+222 −223 +224 +229 +230
−21 −22 +23 , +28 . . . +215
−216 −220 +221 +222 +226
+227 +229 +230 −231
−20 −22 +27 +227 −230

δFt

δwt

δTt

RCt

×
×
×
225 +231
225 +231
02 +225 +231
20 +225 +231

×
×
×
−
−
−
−

×
×
×
225
226
0
2 +22620 +226

×
×
×
7
12
17
22

20 +22 +26 +28−211 +216 −218 −222
−225 +227 +231
22 −26 +28 −211
−214 +216 +219
−222 −225 −230
−20 −23 +25 −27 −29+211 −213 +215 +217
−219 −222 −224 +231
20 +22 −25 +28−210 −213 −216 −222
+227 −229 +231
20 −23 −213 −215 −217
+221 +223 −226 +230

231

−21 +23 +26 +28−211 +216 −218
−222 +227 +231
20 +22 +28 −211
−214 +216 +219
−222 +230
3−2 −25 −29 −212
+215 −218 −222 +224

7

−
−
−215
−
−
231
−
−
−
−215
−
−
−
−
231
−
231

8

+22 −24 +28 +215 +217
−219 −223 +225 +228

9

−20 +22 −26 −230

1011+212 +230−2 −218 +224 +230

−20 +28 −219
−223 −227 +229
−20 +22 +228
22

12
13
14
15
16
17
18
19
20
21
22
23
24
25

+27 −29 +213 −224 −231
−224 −231+231−23 +215+229 −231+231−231−217 −231
−231
−231
−231
−
−
−

230
−230
−224 +231−224 +231
231
231
−
231
231
231
231
−
231
−

14

−

−

−

−

−21 +23 +25 +28+210 −213 +217
+225 +227 −229
−21 −28 −210 +212
+216 −218 −221 −223
−225 +229 +231
20 +219 −222 +226
−21 +27 −227 −229
−23 +28 +217 −219
−223 +225 +228
−20 +22 −26
212
14−2 −218 +230
27 −29 +213 −225
−224
−
−23
229
−
−
−217
−
−
−

12

17

22

7

12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

B.4

New Second Block Differential Paths

57

Table B-10: New second block conditions nr. 2tConditions on Qt : b31 . . . b0
−2 ......0. ........ ........ ........
−1 ^.....0. ........ ........ .......00 ^.....0. ........ ........ .1.....0
Total # IV conditions for 1st block1 ^.....0. ......0. ....1..1 .1.....0
2 ^....00. .1..1100 ..111..0 .0...0.0
3 ^01..10. 00..0001 000000.1 ^01.11^04 011.001^ 10..0111 11011010 11^^1011
5 000.0010 10^^1001 10010101 01011100
6 10010001 10011011 00000000 01100110
7 01.00001 0.001.01 0.011110 01100101
8 1010.00. 11011.00 00011110 01111001
9 01.10.00 1...1.0. 01.10..1 11.0.0.1
10 00.0..10 1...1^1. 11.01..1 .0.1...1
11 00!....0 .....1.. .1^00.^. ^1...0.1
12 10.....1 ....!0.. .001..1. 0.......
13 10.....1 .....1.. 110...0. 0...1...
14 0.0..... ........ 1.1...1. 1...1...
15 111....0 .......! 0....... ....1...
16 1.0..... ......!. ........ ........
17 0....... ......0. ^....... ....^...
18 1.^..... ......1. ........ ........
19 1....... ......1. ........ ........
20 1....... .....!.. ........ ........
21 1....... ......^. ........ ........
22 1....... ........ ........ ........
23 0....... ........ ........ ........
24 1....... ........ ........ ........
Subtotal # conditions

#
(1)
(3)
(4)
(8)
7
15
25
29
31
32
28
29
19
17
14
10
10
7
7
3
4
3
2
2
2
1
1
1
299

58

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B.4.3

New Second Block Differential Path nr. 3

Table B-11: New second block differential path nr. 3
t
−3
−2
−1
0
1
2
3
4

5

∆Qt

(BSDR of δQt )31+2+225 +231+225 +231+225 +231+20 +225 +231
+20 +26 +225 +231
+20 +26 +211 +225 +231
−20 +21 , −26 . . . −210
+212 −216 −217 −218
+219 −222 +223 +225
−228 +229 −231
0−2 +22 +24 −25 +28 +211
+213 +214 +215 −216 +217
+218 −219 −220 +221 +222
−224 +227 −228 +230 +231
−20 . . . −23 +24 , −25 −26+27 +28 +210 , −212 . . . −218
+219 +220 −222 +226 −228
+20 −227 −229

δFt

δwt

δTt

RCt

×
×
×
225 +231
225 +231
225 +231
02 +26 +225 +231
20 −26 +29 −211
+213 +217 +219 +222
+225 −229 +231

×
×
×
−
−
−
−
231

×
×
×
225
226
226
0
2 +26 +226
1
2 −26 +29 −211
+213 +217 +219 +222
+226 −229 +231

×
×
×
7
12
17
22
7

21 −25 +211 −214
+218 −221 +224 +230−

−20 +22 +25 +211
−214 +218 −221
−224 +226 −230

12−

−23 +25 +29 −212
−220 −223 −225 −227

17−

21 +23 −25 +28−210 −213 +217 −219
+225 +227 −229
21 −28 −210 +212
+215 −219 −221 −225
−227 +229 +231
20 +25 −27 +210
+212 +220 −222 +226
20 +27 −212 −227 −229
−23 +27 −29 +217 −219
−223 +225 +228
0−2 +22 −26 −222 −224
212 +217 −219
−214 −218 +230
27 −29 +213 −225
−224
−
−23
229
−
−
−217
−
−
−

22

8

−23 +27 −29 +215 +217
−219 +223 +225 +228

9

−20 +22 −26 −222 −224

−20 −23 −25 +29+211 −213 −220 −223
+226 −228 +231
0
2 +23 +25 +27 +210
+212 −214 +216 −219
−222 −227 −229 +231
−20 +24 +29 +213
+215 +217 +219
+223 −225 −229
27 −29 +228

1011+212 +217 −219
−214 −218 +224 −229

27 −212
−224

−
−215

12
13
14
15
16
17
18
19
20
21
22
23
24
25

+27 −29 +213 −224 −231
−224 −229−231−23 +215+229 −231+231−231−217 −231
−231
−231
−231
−
−
−

−
−
−224 −229−224 +231
229
231
−
231
231
231
231
−
231
−

−
−
231
−
−
−
−215
−
−
−
−
231
−
231

6

7

−

−

7

12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

B.4

New Second Block Differential Paths

59

Table B-12: New second block conditions nr. 3tConditions on Qt : b31 . . . b0
−2 ......0. ........ ........ ........
−1 ^.....0. ........ ........ .......1
0 ^.....0. ........ ........ .0.....1
Total # IV conditions for 1st block1 ^.....0. ........ ....00.. .0!....0
2 ^.11..0. .1..0110 ...00100 00.....0
3 ^001..00 ^0111100 00110010 1011.0^0
4 !101^001 01010111 11101111 11010001
5 .00101.1 00011001 00000000 10101011
6 .0110011 01000111 11110000 01101111
7 01111001 1110101. 1001111. 01..0110
8 1.100101 01.01000 0001.011 01101101
9 ..111.01 01..0.0. 0..0..1. 111100.1
10 1011..10 10..1^0. 1^.0..1. 00..10.0
11 111....0 .1..010! .1^0..1. 01...1.1
12 100....1 ....101. .001..1. 0.......
13 011....1 .....1.. 110...0. 0...1...
14 111..... ........ 1.1...1. 1...1...
15 101....0 .......! 0....... ....1...
16 100..... ......!. ........ ........
17 0....... ......0. ^....... ....^...
18 1.^..... ......1. ........ ........
19 1....... ......1. ........ ........
20 1....... .....!.. ........ ........
21 1....... ......^. ........ ........
22 1....... ........ ........ ........
23 0....... ........ ........ ........
24 1....... ........ ........ ........
Subtotal # conditions

#
(1)
(3)
(4)
(8)
7
17
29
32
31
31
28
29
19
20
17
12
11
8
7
4
4
3
2
2
2
1
1
1
318

60

B DIFFERENTIAL PATHS FOR TWO BLOCK COLLISIONS

B.4.4

New Second Block Differential Path nr. 4

Table B-13: New second block differential path nr. 4
t
−3
−2
−1
0
1
2
3
4

5

6

∆Qt

(BSDR of δQt )31+2+225 +231+225 +231+225 +231+20 +225 +231
+20 +26 +225 +231
+20 +26 +211
+217 +225 +231
0−2 −26 +27 , −211 . . . −214
+215 −216 −218 −219
+220 +222 −225 +226
−228 +229 −231
0+2 +21 +23 +24 +25 −26−28 +29 −211 −212 +216 −217
+218 . . . +221 , +223 +224
+225 −227 −228 +230 −231
−20 +21 −25 −210 −211
−213 −214 +215 −217 −220
+221 +223 +224 −225
+226 +228 −229
−227 −229

δFt

δwt

δTt

RCt

×
×
×
225 +231
225 +231
02 +225 +231
20 +26 −211
+225 +231
02 −26 −212 −216
+218 −220 +222
−225 −227 +231

×
×
×
−
−
−
−

×
×
×
225
226
0
2 +2260
2 +26 −211 +226

×
×
×
7
12
17
22

231

21 −26 −212 −216
+218 −220 +222
−227 +231

7

21 −24 +28 −210
+215 +218 −221 +223
−226 −228 +230−

−20 +22 −24 +26 +28−210 +215 +218 −221
+223 −225 −228 −230

12

−23 +29 +211 −213
−215 −217 +220+226 −228 +231−

20 −23 +26 +29 −212
−215 +220 −225 −227

17

−

22

−

21 +23 −25 +28−213 +217 −219
+225 +227 −229
21 −28 −210 +212
+215 −219 −221 −225
−227 +229 +231
20 −25 +210 +212
+220 −222 +226
−20 +27 −212
−227 −229
3−2 +27 −29 +217
−219 −223 +225 +228
−20 +22 −26−222 −224
12
2 +217 −219
−214 −218 +230
27 −29 +213 −225
−224
−
−23
229
−
−
−217
−
−
−

8

−23 +27 −29 +215 +217
−219 +223 +225 +228

9

−20 +22 −26 −222 −224

−20 −22 −24 −26 +28−211 −213 −216 −219
−222 −227 −229 +231
−20 +23 +29 +213
−215 −217 +221
+225 +227 −229
217 +222 +228

10+212 −217−20 +27 −212−

11−214 −218 +224 −229

−224

−215

12

+27 −29 +213 −224 +231

−

−

13
14
15
16
17
18
19
20
21
22
23
24
25

−224 −229+231−23 +215+229 +231−231+231−217 +231
+231
+231
+231
−
−
−

−218
−224 −229−224 +231
229
231
−
231
231
231
231
−
231
−

−
231
−
−
−
−215
−
−
−
−
231
−
231

7

−

7

12
17
22
7
12
17
22
5
9
14
20
5
9
14
20
5
9

B.4

New Second Block Differential Paths

61

Table B-14: New second block conditions nr. 4tConditions on Qt : b31 . . . b0
−2 ......0. ........ ........ ........
−1 ^.....0. ........ ........ .......00 ^.....0. ........ ........ .0.....0
Total # IV conditions for 1st block1 ^.....0. ......1. ....1... .0.....0
2 ^.10.00. .0.11111 ...00... 10.....0
3 ^0111101 11001100 ^^^10.10 0011..00
4 !0010011 10101111 01111001 0110^.11
5 10111100 01000010 10011001 01000.00
6 00100010 01010111 011.1110 1.111.01
7 10111101 00.00100 0011.000 10110..0
8 0..01001 01011.0. 0001111. 001.1^10
9 1.111.01 11..0.1. 0..0..0. 010.00.1
10 1111..10 10..1^1. 1^.0..1. 00..10.1
11 101....0 .1...10! .1^0..1. 01...1.1
12 010....1 ..!..01. .001..1. 0.......
13 0011...1 .....0.. 110...0. 0...1...
14 0010.... ........ 1.1...1. 1...1...
15 1110...0 .......! 0....... ....1...
16 0101.... ......!. ........ ........
17 1....... ......0. ^....... ....^...
18 0.^..... ......1. ........ ........
19 0....... ......1. ........ ........
20 0....... .....!.. ........ ........
21 0....... ......^. ........ ........
22 0....... ........ ........ ........
23 0....... ........ ........ ........
24 1....... ........ ........ ........
Subtotal # conditions

#
(1)
(3)
(4)
(8)
6
16
29
31
31
29
28
26
19
20
16
12
12
9
8
5
4
3
2
2
2
1
1
1
313

62

C BOOLEAN FUNCTION BITCONDITIONSCBoolean Function Bitconditions

C.1

Bitconditions applied to boolean function F
Table C-1: Bitconditions applied to boolean function F
F (X, Y, Z) = (X ∧ Y ) ⊕ (X̄ ∧ Z)
DB
abc... (8)..+ (4)..- (4).+. (4).++ (2).+- (2).-. (4).-+ (2).-- (2)+.. (4)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-.. (4)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Forward bitconditions
g=0
g = +1g = −1... (8)1.+ (2) 0.+ (2)
1.- (2)0.- (2)0+. (2) 1+. (2).++ (2)
1+- (1) 0+- (1)0-. (2)
1-. (2)0-+ (1) 1-+ (1).-- (2)+.V (2) +10 (1) +01 (1)+0+ (1) +1+ (1)+1- (1)+0- (1)++1 (1) ++0 (1)+++ (1)++- (1)+-0 (1)+-1 (1)+-+ (1)+-- (1)-.V (2) -01 (1) -10 (1)-1+ (1) -0+ (1)-0- (1)-1- (1)-+0 (1) -+1 (1)-++ (1)-+- (1)--1 (1)--0 (1)--+ (1)--- (1)

Backward bitconditions
g=0
g = +1g = −1... (8)1.+ (2) 0.+ (2)
1.- (2)0.- (2)0+. (2) 1+. (2).++ (2)
1+- (1) 0+- (1)0-. (2)
1-. (2)0-+ (1) 1-+ (1).-- (2)+^. (2) +10 (1) +01 (1)+0+ (1) +1+ (1)+1- (1)+0- (1)++1 (1) ++0 (1)+++ (1)++- (1)+-0 (1)+-1 (1)+-+ (1)+-- (1)-^. (2) -01 (1) -10 (1)-1+ (1) -0+ (1)-0- (1)-1- (1)-+0 (1) -+1 (1)-++ (1)-+- (1)--1 (1)--0 (1)--+ (1)--- (1)

Here abc denotes three bitconditions (qt [i], qt−1 [i], qt−2 [i]) for 0 ≤ t ≤ 15 and 0 ≤ i ≤ 31.
The next three columns hold the forward bitconditions F C(t, abc, 0), F C(t, abc, +1) andF C(t, abc, −1), respectively. The last three columns hold the backward bitconditions
BC(t, abc, 0), BC(t, abc, +1) and BC(t, abc, −1), respectively.
Next to each triple of bitconditions def is denoted |Udef |, the amount of freedom left.
An entry is left empty if g ∈/ Vabc . See subsubsection 6.3.2 for more details.

C.2

C.2

Bitconditions applied to boolean function G

Bitconditions applied to boolean function G
Table C-2: Bitconditions applied to MD5 boolean function G
G(X, Y, Z) = (Z ∧ X) ⊕ (Z̄ ∧ Y )DB
abc... (8)..+ (4)..- (4).+. (4).++ (2).+- (2).-. (4).-+ (2).-- (2)+.. (4)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-.. (4)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Forward bitconditions
g=0
g = +1g = −1... (8).V+ (2) 10+ (1) 01+ (1).V- (2) 01- (1) 10- (1).+1 (2) .+0 (2)0++ (1) 1++ (1)
1+- (1) 0+- (1).-1 (2).-0 (2)1-+ (1)0-+ (1)0-- (1)
1-- (1)+.0 (2) +.1 (2)+1+ (1) +0+ (1)+0- (1) +1- (1)++. (2)+++ (1)++- (1)+-1 (1) +-0 (1)+-+ (1)+-- (1)-.0 (2)-.1 (2)-0+ (1)-1+ (1)-1- (1)-0- (1)-+0 (1) -+1 (1)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Backward bitconditions
g=0
g = +1g = −1... (8)^.+ (2) 10+ (1) 01+ (1)^.- (2) 01- (1) 10- (1).+1 (2) .+0 (2)0++ (1) 1++ (1)
1+- (1) 0+- (1).-1 (2).-0 (2)1-+ (1)0-+ (1)0-- (1)
1-- (1)+.0 (2) +.1 (2)+1+ (1) +0+ (1)+0- (1) +1- (1)++. (2)+++ (1)++- (1)+-1 (1) +-0 (1)+-+ (1)+-- (1)-.0 (2)-.1 (2)-0+ (1)-1+ (1)-1- (1)-0- (1)-+0 (1) -+1 (1)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Here abc denotes three bitconditions (qt [i], qt−1 [i], qt−2 [i]) for 16 ≤ t ≤ 31 and 0 ≤ i ≤ 31.
The next three columns hold the forward bitconditions F C(t, abc, 0), F C(t, abc, +1) andF C(t, abc, −1), respectively. The last three columns hold the backward bitconditions
BC(t, abc, 0), BC(t, abc, +1) and BC(t, abc, −1), respectively.
Next to each triple of bitconditions def is denoted |Udef |, the amount of freedom left.
An entry is left empty if g ∈/ Vabc . See subsubsection 6.3.2 for more details.

63

64

C BOOLEAN FUNCTION BITCONDITIONS

C.3

Bitconditions applied to boolean function H
Table C-3: Bitconditions applied to MD5 boolean function H
H(X, Y, Z) = X ⊕ Y ⊕ Z
DBabc... (8)..+ (4)..- (4).+. (4).++ (2).+- (2).-. (4).-+ (2).-- (2)+.. (4)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-.. (4)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Forward bitconditions
g=0
g = +1g = −1... (8).V+ (2) .Y+ (2).Y- (2) .V- (2).+W (2) .+H (2).++ (2).+- (2).-H (2) .-W (2).-+ (2).-- (2)+.V (2) +.Y (2)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-.Y (2) -.V (2)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Backward bitconditions
g=0
g = +1g = −1... (8)^.+ (2) !.+ (2)!.- (2) ^.- (2)m+. (2) #+. (2).++ (2).+- (2)#-. (2) m-. (2).-+ (2).-- (2)+^. (2) +!. (2)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-!. (2) -^. (2)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Here abc denotes three bitconditions (qt [i], qt−1 [i], qt−2 [i]) for 32 ≤ t ≤ 47 and 0 ≤ i ≤ 31.
The next three columns hold the forward bitconditions F C(t, abc, 0), F C(t, abc, +1) andF C(t, abc, −1), respectively. The last three columns hold the backward bitconditions
BC(t, abc, 0), BC(t, abc, +1) and BC(t, abc, −1), respectively.
Next to each triple of bitconditions def is denoted |Udef |, the amount of freedom left.
An entry is left empty if g ∈/ Vabc . See subsubsection 6.3.2 for more details.

C.4

C.4

Bitconditions applied to boolean function I

Bitconditions applied to boolean function I
Table C-4: Bitconditions applied to MD5 boolean function I
I(X, Y, Z) = Y ⊕ (X ∨ Z̄)DB
abc... (8)..+ (4)..- (4).+. (4).++ (2).+- (2).-. (4).-+ (2).-- (2)+.. (4)+.+ (2)+.- (2)++. (2)+++ (1)++- (1)+-. (2)+-+ (1)+-- (1)-.. (4)-.+ (2)-.- (2)-+. (2)-++ (1)-+- (1)--. (2)--+ (1)--- (1)

Forward bitconditions
g=0
g = +1g = −1... (8)1.+ (2) 01+ (1) 00+ (1)
1.- (2) 00- (1) 01- (1)0+1 (1) .+Q (3)0++ (1)1++ (1)0+- (1)
1+- (1).-Q (3) 0-1 (1)0-+ (1) 1-+ (1)0-- (1) 1-- (1)+.0 (2) +01 (1) +11 (1)+.+ (2)+0- (1) +1- (1)++1 (1)++0 (1)+++ (1)++- (1)+-1 (1) +-0 (1)+-+ (1)+-- (1)-.0 (2) -11 (1) -01 (1)-1+ (1) -0+ (1)-.- (2)-+1 (1)-+0 (1)-++ (1)-+- (1)--1 (1) --0 (1)--+ (1)--- (1)

Backward bitconditions
g=0
g = +1g = −1... (8)1.+ (2) 01+ (1) 00+ (1)
1.- (2) 00- (1) 01- (1)0+1 (1) ?+. (3)0++ (1)1++ (1)0+- (1)
1+- (1)?-. (3) 0-1 (1)0-+ (1) 1-+ (1)0-- (1) 1-- (1)+.0 (2) +01 (1) +11 (1)+.+ (2)+0- (1) +1- (1)++1 (1)++0 (1)+++ (1)++- (1)+-1 (1) +-0 (1)+-+ (1)+-- (1)-.0 (2) -11 (1) -01 (1)-1+ (1) -0+ (1)-.- (2)-+1 (1)-+0 (1)-++ (1)-+- (1)--1 (1) --0 (1)--+ (1)--- (1)

Here abc denotes three bitconditions (qt [i], qt−1 [i], qt−2 [i]) for 48 ≤ t ≤ 63 and 0 ≤ i ≤ 31.
The next three columns hold the forward bitconditions F C(t, abc, 0), F C(t, abc, +1) andF C(t, abc, −1), respectively. The last three columns hold the backward bitconditions
BC(t, abc, 0), BC(t, abc, +1) and BC(t, abc, −1), respectively.
Next to each triple of bitconditions def is denoted |Udef |, the amount of freedom left.
An entry is left empty if g ∈/ Vabc . See subsubsection 6.3.2 for more details.

65

66

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D

Chosen-Prefix Collision Example - Colliding Certificates

D.1

Chosen Prefixes
Table D-1: Chosen Prefix 1: Partial X.509 Certificate with identity Arjen K. Lenstra
PAL=

30 82 05 11 A0 03 02 01 02 02 04 01 0C 00 01 30
0D 06 09 2A 86 48 86 F7 0D 01 01 04 05 00 30 3D
31 1A 30 18 06 03 55 04 03 13 11 48 61 73 68 20
43 6F 6C 6C 69 73 69 6F 6E 20 43 41 31 12 30 10
06 03 55 04 07 13 09 45 69 6E 64 68 6F 76 65 6E
31 0B 30 09 06 03 55 04 06 13 02 4E 4C 30 1E 17
0D 30 36 30 31 30 31 30 30 30 30 30 31 5A 17 0D
30 37 31 32 33 31 32 33 35 39 35 39 5A 30 54 31
19 30 17 06 03 55 04 03 13 10 41 72 6A 65 6E 20
4B 2E 20 4C 65 6E 73 74 72 61 31 16 30 14 06 03
55 04 0A 13 0D 43 6F 6C 6C 69 73 69 6F 6E 61 69
72 73 31 12 30 10 06 03 55 04 07 13 09 45 69 6E
64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00

IHVAL = IHV3==

A2934A57268FC8FB99270DB2BD42867F{574a93a216 , fbc88f2616 , b20d279916 , 7f8642bd16 }Table D-2: Chosen Prefix 2: Partial X.509 Certificate with identity Marc Stevens
PMS=

30 82 05 11 A0 03 02 01 02 02 04 02 0C 00 01 30
0D 06 09 2A 86 48 86 F7 0D 01 01 04 05 00 30 3D
31 1A 30 18 06 03 55 04 03 13 11 48 61 73 68 20
43 6F 6C 6C 69 73 69 6F 6E 20 43 41 31 12 30 10
06 03 55 04 07 13 09 45 69 6E 64 68 6F 76 65 6E
31 0B 30 09 06 03 55 04 06 13 02 4E 4C 30 1E 17
0D 30 36 30 31 30 31 30 30 30 30 30 31 5A 17 0D
30 37 31 32 33 31 32 33 35 39 35 39 5A 30 54 31
15 30 13 06 03 55 04 03 13 0C 4D 61 72 63 20 53
74 65 76 65 6E 73 31 1A 30 18 06 03 55 04 0A 13
11 43 6F 6C 6C 69 73 69 6F 6E 20 46 61 63 74 6F
72 79 31 12 30 10 06 03 55 04 07 13 09 45 69 6E
64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00

IHVMS = IHV3==9756EBE66FC92AD60256345C8EC444A8{e6eb569716 , d62ac96f16 , 5c34560216 , a844c48e16 }D.2

Birthday attack

67

Table D-3: Chosen Prefix 3: Partial X.509 Certificate with identity Benne de Weger
PBW=

30 82 05 11 A0 03 02 01 02 02 04 03 0C 00 01 30
0D 06 09 2A 86 48 86 F7 0D 01 01 04 05 00 30 3D
31 1A 30 18 06 03 55 04 03 13 11 48 61 73 68 20
43 6F 6C 6C 69 73 69 6F 6E 20 43 41 31 12 30 10
06 03 55 04 07 13 09 45 69 6E 64 68 6F 76 65 6E
31 0B 30 09 06 03 55 04 06 13 02 4E 4C 30 1E 17
0D 30 36 30 31 30 31 30 30 30 30 30 31 5A 17 0D
30 37 31 32 33 31 32 33 35 39 35 39 5A 30 54 31
17 30 15 06 03 55 04 03 13 0E 42 65 6E 6E 65 20
64 65 20 57 65 67 65 72 31 18 30 16 06 03 55 04
0A 13 0F 43 6F 6C 6C 69 73 69 6F 6E 6D 61 6B 65
72 73 31 12 30 10 06 03 55 04 07 13 09 45 69 6E
64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00

IHVBW = IHV3

D.2

=
=

5B2D26DB2317BE0A93D936FD47C7B013{db262d5b16 , 0abe172316 , fd36d99316 , 13b0c74716 }Birthday attack
Table D-4: Birthday Attack
IHVAL= A2934A57268FC8FB99270DB2BD42867F= {574a93a216 , fbc88f2616 , b20d279916 , 7f8642bd16 }IHVMS= 9756EBE66FC92AD60256345C8EC444A8= {e6eb569716 , d62ac96f16 , 5c34560216 , a844c48e16 }IHVBW= 5B2D26DB2317BE0A93D936FD47C7B013= {db262d5b16 , 0abe172316 , fd36d99316 , 13b0c74716 }R= 64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00 xx xx xx xx yy yy yy yy zz zz zz zz= { 766f686416 , 0b316e6516 , 0306093016 , 1306045516 ,
304c4e0216 , 3022048216 , 2a09060d16 , f786488616 ,
0101010d16 , 8203000516 , 30000f0416 , 020a048216 ,
0001048216 ,
x,
y,
z
}


 IHVAL , if x = 0 mod 3;
IHVMS , if x = 1 mod 3;
φ(x, y, z) =
IHVBW , if x = 2 mod 3.
ψ(x, y, z) = Rkxkykz
ρ(IHV ) = ρ(a, b, c, d) = (a, d − b, d − c)Φ(x, y, z) = ρ(MD5Compress(φ(x, y, z), ψ(x, y, z)))S = {(x, y, z) | (x ≡ 0 mod 215 ) ∧ (RL(y, 15) ≡ 0

mod 215 )}68

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

Table D-5: Birthday attack - Results
IHV3 = IHVMS= 9756EBE66FC92AD60256345C8EC444A8= {e6eb569716 , d62ac96f16 , 5c34560216 , a844c48e16 }(X, Y, Z) = (cbb4091a16 , 7a26c74016 , 9b7f01af16 )IHV30 = IHVAL= A2934A57268FC8FB99270DB2BD42867F= {574a93a216 , fbc88f2616 , b20d279916 , 7f8642bd16 }(X 0 , Y 0 , Z 0 ) = (d6e773ee16 , ba4fb3b316 , 023d39a116 )M4= 64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00 1A 09 B4 CB 40 C7 26 7A AF 01 7F 9B= { 766f686416 , 0b316e6516 , 0306093016 , 1306045516 ,
304c4e0216 , 3022048216 , 2a09060d16 , f786488616 ,
0101010d16 , 8203000516 , 30000f0416 , 020a048216 ,
0001048216 , cbb4091a16 , 7a26c74016 , 9b7f01af16 }M40= 64 68 6F 76 65 6E 31 0B 30 09 06 03 55 04 06 13
02 4E 4C 30 82 04 22 30 0D 06 09 2A 86 48 86 F7
0D 01 01 01 05 00 03 82 04 0F 00 30 82 04 0A 02
82 04 01 00 EE 73 E7 D6 B3 B3 4F BA A1 39 3D 02= { 766f686416 , 0b316e6516 , 0306093016 , 1306045516 ,
304c4e0216 , 3022048216 , 2a09060d16 , f786488616 ,
0101010d16 , 8203000516 , 30000f0416 , 020a048216 ,
0001048216 , d6e773ee16 , ba4fb3b316 , 023d39a116 }IHV4= 2D857B4EA419FB613F17A61017126647= {4e7b852d16 , 61fb19a416 , 10a6173f16 , 4766121716 }IHV40= 2D857B4E0479B7259F7662D47771220B= {4e7b852d16 , 25b7790416 , d462769f16 , 0b22717716 }

δIHV4
δb4

= {0, δb4 , δb4 , δb4 }= −25 − 27 − 213 + 215 − 218 − 222 + 226 − 230

D.2

Birthday attack

69

70

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3

Differential Paths

D.3.1

Block 1 of 8

Table D-6: Differential Path - block 1
Using δm11 = +220t
Bits Qt : b31 . . . b0
−301001110 01111011 10000101 00101101−20-00+-11 0-100-10 0++100-+ 0++10111−1++010+00 -+100-10 0++1011- +0-11111
00-100+01 1-11-+11 0++11001 -0-00100
1+0...+-. 1-+.++.- .......1 -.-.1+.0
2
1+...-+. 1.-.1..- .10^..!1 ..-^00.1
30+.0^-1. -1-011.- ^11+..^- 1.++01.+
4
11.1++1. -.01.... +0.0..-1 ..10+1.+
5010-01.0 +00.0000 0-010001 000--00.
6
1-1+1+01 +1.01111 ++1+11++ 11.00-10
7.0.+.0.- .1....-- 1+.-..+0 .-.11--.
8.1...0.1 0-....00 100-..0+ 1+..0.-.
9.0.10..1 .-....1+ .-1...++ 0+..101.
10.10.0011 0.0000.0 01+00!1. +.00+.01
110010+11+ 10111111 1+0.11-0 111110+012
1-0.-1+1 0101..01 00+.00+1 001.10013
00+10-0- --+0^^+- 000^1+0- -1+.0-++1411000+-- -------- +.+----- +--1+--15+01-0100 0-1-10-0 -.1010-1 0+10100+
16
1001-11+ 01010001 +.000000 000+10017
1.10...0 .1.0..-. 1.1...+. .0.-..1018..+.^..- ...1.... +.-...+. ...1..+019^^.....- .0.+..^. +....0-. ...-....
20..^....0 01...0.. 0.^..1-. .0...0^.
21..0....1 1-.^.1.. ^....-0. .1.^.1..
22..1..... +....+.. ......^. .+...-..
23..+.0... .^...... 0....^.. ........
24....1... ^....^.. 1...0... .^...^.025..^.-... ........ -...1... ........
26........ ...0.... ....-... ......0+27....^... ...1.... ^....... ......1+28........ ...+.... ....^... ......+29........ ...0.... ........ .......030........ ...-.... ........ ......^131........ ...-.... ........ ........
32........ ........ ........ ........
33........ ...!.... ........ ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62.+...... ........ ........ ........
63.+...... ........ ........ ........
64.+...... ........ ........ ........

#
32
32
32
32
16
18
25
19
29
30
17
17
16
25
31
27
31
31
31
31
14
10
10
12
12
6
5
8
4
4
5
4
2
3
1
0
1
0

D.3

Differential Paths

Table D-7: Block 1 found using path in Table D-6
M5= A4 74 25 81 8D C8 4F 86 73 6E 90 72 28 BB E8 77
02 03 85 8D 8C F1 83 7A FF 5E 6C 22 13 03 6A F3
D9 5C 77 E9 C2 23 7D 60 8C C4 A9 FB 97 30 7B BF
98 28 61 2F 15 99 E2 61 5B CC DE DA 59 30 53 2F= { 812574a416 , 864fc88d16 , 72906e7316 , 77e8bb2816 ,
8d85030216 , 7a83f18c16 , 226c5eff16 , f36a031316 ,e9775cd916 , 607d23c216 , fba9c48c16 , bf7b309716 ,2f61289816 , 61e2991516 , dadecc5b16 , 2f53305916 }M50= A4 74 25 81 8D C8 4F 86 73 6E 90 72 28 BB E8 77
02 03 85 8D 8C F1 83 7A FF 5E 6C 22 13 03 6A F3
D9 5C 77 E9 C2 23 7D 60 8C C4 A9 FB 97 30 8B BF
98 28 61 2F 15 99 E2 61 5B CC DE DA 59 30 53 2F= { 812574a416 , 864fc88d16 , 72906e7316 , 77e8bb2816 ,
8d85030216 , 7a83f18c16 , 226c5eff16 , f36a031316 ,e9775cd916 , 607d23c216 , fba9c48c16 , bf8b309716 ,2f61289816 , 61e2991516 , dadecc5b16 , 2f53305916 }IHV5= E745A147086391F0910F3B97AE85BE73= {47a145e716 , f091630816 , 973b0f9116 , 73be85ae16 }IHV50= E745A14768C24DF4F16EF79A0EE57A77= {47a145e716 , f44dc26816 , 9af76ef116 , 777ae50e16 }

δIHV5
δb5

= {0, δb5 , δb5 , δb5 }= −25 − 27 − 213 + 215 − 218 − 222 + 226

71

72

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.2

Block 2 of 8

Table D-8: Differential Path - block 2
Using δm11 = −216t
Bits Qt : b31 . . . b0
−301000111 10100001 01000101 11100111−201110+11 -+111-10 1++00101 -0-01110−11001+-1- ++11-+11 0++0111- 1++10001
011110+00 -+0-++01 +1-0001- 0++01000
1
0.+.11.- ++1--+.. 0+1...1- .++.....
2
0.+0+0.1 -.+.-... 1+0..!+. ..-.....
3+1+10+.+ 10+1-0.. 0++...11 .00.....
4
1.+.--.+ 1.+0.... .+1...-. ..+0.^..
5
1.11-10. -0.-0000 01-000-0 00110+00
6110.0110 -11+1111 1-+111+1 11--1011
7+0111-.. -..-.1.. --+.0.-. ..00.0..
8001.+-.. +.!-.+.. +...+.-. ..-+....
9+00.1-.. 0..+.1.. -10.0... ..-+...0
10++100-0. 00.+.-00 -.000000 !1+.00.0
11-0110+10 010-0-11 -001.111 ^11111012
1000+000 101+1-^0 -.+0.00^ ++10010+
13----00-- ++---+-+ +^+11--- 0-0++++14
110--+++ ++++1000 +---1100 -+++++++
15
1110+100 +++0101+ +010+110 010111-0
16..1+1101 1++1...1 1001-.0. 110000-017!.1.1.1. 100..+.0 1...1.1. ..-..100
18..-^..-. .^+..+.1 ....1.-. ..-...1019........ ..+..-.- ....-... .0+....+
20.0^...^. ..0.1-.. .0....^. .1+..0..
21.1....0. ..^.1-.^ .1..^... .+0..1.^22.+....1. ....-1.. .-...... ..^..-..
23......-. 0...10.. ....0... .^......
24.^.0.... 1...0... .^..1... 0....^..
25......^. +....... ....+... 1.......
26..0-.... .......0 ........ +.......
27..1-.... ^......1 ....^... ........
28..-+.... .......- ........ ^.......
29...0.... .......0 ........ ........
30..^1.... .......+ ........ ........
31........ .......+ ........ ........
32........ ........ ........ ........
33........ .......! ........ ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62.....-.. ........ ........ ........
63.....-.. ........ ........ ........
64.....-.. ........ ........ ........

#
32
32
32
32
18
15
20
14
29
31
17
14
15
26
31
30
32
32
32
25
16
12
7
11
12
7
6
8
4
4
5
4
2
3
1
0
1
0

D.3

Differential Paths

Table D-9: Block 2 found using path in Table D-8
M6= B3 DD 11 72 78 E4 94 40 14 33 63 0E 74 61 C1 DC
9B 80 1B 2E 55 20 15 A5 13 FF 7A E7 97 3E F4 4B
83 52 E4 E0 49 79 B3 1E B6 00 65 4D 51 F4 A4 81
CE BE 3F 0B D0 99 D1 30 D1 45 6F AB E0 4A 3E 98= { 7211ddb316 , 4094e47816 , 0e63331416 , dcc1617416 ,
2e1b809b16 , a515205516 , e77aff1316 , 4bf43e9716 ,
e0e4528316 , 1eb3794916 , 4d6500b616 , 81a4f45116 ,0b3fbece16 , 30d199d016 , ab6f45d116 , 983e4ae016 }M60= B3 DD 11 72 78 E4 94 40 14 33 63 0E 74 61 C1 DC
9B 80 1B 2E 55 20 15 A5 13 FF 7A E7 97 3E F4 4B
83 52 E4 E0 49 79 B3 1E B6 00 65 4D 51 F4 A3 81
CE BE 3F 0B D0 99 D1 30 D1 45 6F AB E0 4A 3E 98= { 7211ddb316 , 4094e47816 , 0e63331416 , dcc1617416 ,
2e1b809b16 , a515205516 , e77aff1316 , 4bf43e9716 ,
e0e4528316 , 1eb3794916 , 4d6500b616 , 81a3f45116 ,0b3fbece16 , 30d199d016 , ab6f45d116 , 983e4ae016 }IHV6= 6900F0DD0821F13B2AF6DF5D3521BFC7= {ddf0006916 , 3bf1210816 , 5ddff62a16 , c7bf213516 }IHV60= 6900F0DD6880AD3B8A559C5D95807BC7= {ddf0006916 , 3bad806816 , 5d9c558a16 , c77b809516 }

δIHV6
δb6

= {0, δb6 , δb6 , δb6 }= −25 − 27 − 213 + 215 − 218 − 222

73

74

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.3

Block 3 of 8

Table D-10: Differential Path - block 3
Using δm11 = +212t
Bits Qt : b31 . . . b0
−311011101 11110000 00000000 01101001−211000111 -+111-11 +0-0000- +0-10101−1
01011101 1-0111-- -1-101-+ +0-01010
000111011 1-1-++01 +0-0000- 0++01000
1.......- .+.-01-- 1---..10 --+.1...
20..!...0 .+..0-0- -1.+0..- +0-.-...
3
01.....1 .-.0-1+. +00+0..- -+1.0...
4+0.^.... .-..1--1 +...+... 0-+.1...
5
110+000^ 0.00+1+. 0001-001 00-0.010
6+110110+ 111110-0 -1111111 00-10111
7-..+..-0 ....00-1 +..01... -.-...-.
8-1!1..-0 .....1-. +..-.... 1..^..0.
9
10.1..+0 ..0..+-. ...+.0.. 1!1+0.0.
10
0.0.00+0 .01.00.0 100-0100 ..011..^111110111+ 01-01-01 011+1-11 0101-01+
12001.110- 10110-11 01001+.0 11+0-110
13-++^+++1 -+++++-+ -----+^1 +--10--1
14
010+1100 111+---- +-0+11-+ +++++++.
15
11+0110+ +000-111 010--011 -110-01.
16..+00.0- ..01-001 00.0..01 +100110.
17..00..11 ^.1.0.0. .-.0^... 1.1.1.+.
18..10..+^ ..+.1.1. .-.1.... 1.+...+.
19...-.... ......-. .+.+.... +....0-.
20.0...0^. ..^...0. 1+...0.. ..^..1-.
21.1.^.1.. ..0...1. 1+.^.1.. ^....-0.
22.+...-.. ..1..... +1...+.. ......^.
23........ ..+.0... 10...... 0....^..
24.^...^.0 ....1... 0....^.. 1...0...
25........ ..^.-... ........ -...1...
26......0+ ........ ...0.... ....-...
27......1+ ....^... ...1.... ^.......
28......+- ........ ...+.... ....^...
29.......0 ........ ...0.... ........
30......^1 ........ ...-.... ........
31........ ........ ...-.... ........
32........ ........ ........ ........
33........ ........ ...!.... ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ .+...... ........ ........
63........ .+...... ........ ........
64........ .+...... ........ ........

#
32
32
32
32
17
17
18
14
29
32
14
13
16
23
32
30
32
31
31
23
15
12
7
11
12
7
6
8
4
4
5
4
2
3
1
0
1
0

D.3

Differential Paths

Table D-11: Block 3 found using path in Table D-10
M7

= 85 C8 C4 FB 29 7B 86 B5 77 52 CD 64 19 80 9F E3
7E 62 86 F0 77 32 D1 E0 69 A5 B4 E5 66 70 B8 BB
BA E5 C2 11 74 2A 13 1D 05 71 1C F1 FE 22 AF 93
3F 1E EF 22 47 62 E3 AA DA C1 7C 40 E4 48 CA 41= { fbc4c88516 , b5867b2916 , 64cd527716 , e39f801916 ,
f086627e16 , e0d1327716 , e5b4a56916 , bbb8706616 ,
11c2e5ba16 , 1d132a7416 , f11c710516 , 93af22fe16 ,22ef1e3f16 , aae3624716 , 407cc1da16 , 41ca48e416 }M70= 85 C8 C4 FB 29 7B 86 B5 77 52 CD 64 19 80 9F E3
7E 62 86 F0 77 32 D1 E0 69 A5 B4 E5 66 70 B8 BB
BA E5 C2 11 74 2A 13 1D 05 71 1C F1 FE 32 AF 93
3F 1E EF 22 47 62 E3 AA DA C1 7C 40 E4 48 CA 41= { fbc4c88516 , b5867b2916 , 64cd527716 , e39f801916 ,
f086627e16 , e0d1327716 , e5b4a56916 , bbb8706616 ,
11c2e5ba16 , 1d132a7416 , f11c710516 , 93af32fe16 ,22ef1e3f16 , aae3624716 , 407cc1da16 , 41ca48e416 }IHV7= 6F48D9E5383E55D0FC43ED4D20ABF6F8= {e5d9486f16 , d0553e3816 , 4ded43fc16 , f8f6ab2016 }IHV70= 6F48D9E5989D51D05CA3E94D800AF3F8= {e5d9486f16 , d0519d9816 , 4de9a35c16 , f8f30a8016 }

δIHV7
δb7

= {0, δb7 , δb7 , δb7 }= −25 − 27 − 213 + 215 − 218

75

76

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.4

Block 4 of 8

Table D-12: Differential Path - block 4
Using δm11 = +28t
Bits Qt : b31 . . . b0
−311100101 11011001 01001000 01101111−211111000 11110-1+ -0-0101- +0-00000−1
01001101 11101-01 +-+00011 -1-11100
011010000 01010-01 +0-111-+ +0-11000
1.0..0.-0 ....-+.. .+1+..01 -1-...0.
2..!.+.0- ....10.. 0+0+..00 --+0..0.
3!...0.++ .0.010.. .+.+...- +-10..+.
4....11++ .1!0...^ .-.+...1 -.0-..-.
50010.0.+ 0+.+00.- 010-0000 -0.-00-0
611110+1- 0+0-1101 101-1111 .10+11+1
7
10+..1.0 +..+..00 ..1-.... 10.+..1.
8
110..-.0 +1.+..+1 ..0...1. .-....0.
9-1-..+.. 1.....+. ..-01.01 .-.0.^..
10-010.+0. 11^0...0 .01.00+0 0-..0-00
1100+10110 -1+10001 011001++ 1.011011
12+0101100 1-100110 01+0+111 1011011.
13-1-1---- 0--++--1 --++-100 00+----.
14
0-++10+- -+++++++ +1-11-++ ++0++10.
15
1-110010 00-.-001 011-10-1 -01101-.
16
0110..+1 011^111+ 1.1+.0+1 10+00.1.
17.1.....+ ..1.1... ...+..1. 1.+1..1.
18..0...^1 ..-....^ ...1..0. ..01..+.
19.00....- ......1. ...-.0.. ..^-....
20.1+..0.. ..^..... ....01.. .0....^.
21
0+1..1.^ ......+. ...^1+.. .1.^....
22..0..+.. ......+. ....+... .+......
23+^...... ......-. 0...1^.. ....0...
24+....^.. ...0..0. 1...0... .^..1...
25-....... ......1. -....... ....-...
26-....... ..0+.... .......0 ........
27
1....... ..1+.... ^......1 ....^...
28
0....... ..+-.... .......+ ........
29........ ...0.... .......0 ........
30........ ..^1.... .......- ........
31........ ........ .......- ........
32........ ........ ........ ........
33........ ........ .......! ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ .....+.. ........ ........
63........ .....+.. ........ ........
64........ .....+.. ........ ........

#
32
32
32
32
15
17
16
15
27
31
15
14
14
23
31
31
31
31
30
26
10
10
8
8
11
5
7
8
4
4
6
4
2
3
1
0
1
0

D.3

Differential Paths

Table D-13: Block 4 found using path in Table D-12
M8

= A8 79 A0 3D 3C F6 65 F2 39 C7 F3 FE 82 B3 84 E8
35 E7 C9 E8 BD EE 30 C2 68 A2 12 12 84 78 9D F4
2F 44 90 6F 19 B7 90 26 46 44 36 E1 DA 64 FA 0C
53 A3 77 FA 0D 2B 01 2B 7D DC 28 55 DA E5 B5 51= { 3da079a816 , f265f63c16 , fef3c73916 , e884b38216 ,e8c9e73516 , c230eebd16 , 1212a26816 , f49d788416 ,
6f90442f16 , 2690b71916 , e136444616 , 0cfa64da16 ,
fa77a35316 , 2b012b0d16 , 5528dc7d16 , 51b5e5da16 }M80= A8 79 A0 3D 3C F6 65 F2 39 C7 F3 FE 82 B3 84 E8
35 E7 C9 E8 BD EE 30 C2 68 A2 12 12 84 78 9D F4
2F 44 90 6F 19 B7 90 26 46 44 36 E1 DA 65 FA 0C
53 A3 77 FA 0D 2B 01 2B 7D DC 28 55 DA E5 B5 51= { 3da079a816 , f265f63c16 , fef3c73916 , e884b38216 ,e8c9e73516 , c230eebd16 , 1212a26816 , f49d788416 ,
6f90442f16 , 2690b71916 , e136444616 , 0cfa65da16 ,
fa77a35316 , 2b012b0d16 , 5528dc7d16 , 51b5e5da16 }IHV8= 80D9AE060626A79399F4E05A0E7F318F= {06aed98016 , 93a7260616 , 5ae0f49916 , 8f317f0e16 }IHV80= 80D9AE066685A793F953E15A6EDE318F= {06aed98016 , 93a7856616 , 5ae153f916 , 8f31de6e16 }

δIHV8
δb8

= {0, δb8 , δb8 , δb8 }= −25 − 27 − 213 + 215

77

78

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.5

Block 5 of 8

Table D-14: Differential Path - block 5
Using δm11 = −25tBits Qt : b31 . . . b0
−300000110 10101110 11011001 10000000−210001111 00110001 +1-1111- 0++01110−101011010 1110000+ -1-10-++ 1++11001
010010011 10100111 +0-001-+ 0++00110
1
0....0.. +..-.1.1 -.0+.1-+ 1++.....
200.!.+.. -..0.-.. -.+-.... -0-.....
3+1..^1.. 1..1.-.. -.1+..00 +-+.....
400..+1^. 0....-.! +.1-.... +-+.....
5
10000.-0 -0000+0. 10.00000 0++00.00
6+1111001 -1111110 01001111 +0+11011
7+.....10 .....00. ..0..0.- +1+..00.
8-00....1 0..!..+. .^-....0 .-0..-0.
9
110....+ .0....+. .+0....0 011..--.
10
0.+0100+ 0000^0.0 0010...0 .1.!01+0
11
10+10111 1+11-101 11.10000 00001++1
120000+00- .++10101 0+00101+ 000101-1
13-+011--- .--+---- --10+--- +----+114
10---1-- .0111011 -+++++++ -------15
11000101 .+01110- 010+000+ 0-..-1+0
160-001.10 .0.0.1.. 111+1111 10^^10017.-1..-.. .11..1.^ ...0...+ .0.!-.-18^+...-.. ..0..-.. ...1...0 ....-..0
19.0..0+.. ..+..... .......- 0...+.^20.0..1+.. .....^.. .......+ 1...+..021....+0.. 0.^..... .0.....1 +...1..1
22...0.0.. 1....... .1.....- ....-...
23....^... -....... .-.0.... ^......024..0+.... 0.....0. ...1...^ ..0.^..1
25..1+.... 1....... .^.+.... ..1....+
26..+-.... .....0-. ........ ..+.....
27...0.... .....1-. ...^.... ..0....^
28..^1.... .....-+. ........ ..-.....
29........ ......0. ........ ..0.....
30........ .....^1. ........ ..+.....
31........ ........ ........ ..+.....
32........ ........ ........ ........
33........ ........ ........ ..!.....
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ ........ -....... ........
63........ ........ -....... ........
64........ ........ -....... ........

#
32
32
32
32
15
13
15
14
28
32
13
14
14
25
31
31
31
31
29
26
14
9
9
8
9
6
6
9
7
5
6
5
2
3
1
0
1
0

D.3

Differential Paths

Table D-15: Block 5 found using path in Table D-14
M9

= 51 E2 80 34 11 21 20 B5 E7 9E C5 F2 6A 9F 69 DA
85 D7 4E F6 A9 7A 0B 11 64 EF A2 5F B1 AE 26 BA
45 1C CD A7 A2 E7 84 33 9C 44 7D 56 25 49 A6 0B
F0 67 62 94 BF 58 0C 91 9E C4 57 02 5D 3C 78 60= { 3480e25116 , b520211116 , f2c59ee716 , da699f6a16 ,f64ed78516 , 110b7aa916 , 5fa2ef6416 , ba26aeb116 ,a7cd1c4516 , 3384e7a216 , 567d449c16 , 0ba6492516 ,
946267f016 , 910c58bf16 , 0257c49e16 , 60783c5d16 }M90= 51 E2 80 34 11 21 20 B5 E7 9E C5 F2 6A 9F 69 DA
85 D7 4E F6 A9 7A 0B 11 64 EF A2 5F B1 AE 26 BA
45 1C CD A7 A2 E7 84 33 9C 44 7D 56 05 49 A6 0B
F0 67 62 94 BF 58 0C 91 9E C4 57 02 5D 3C 78 60= { 3480e25116 , b520211116 , f2c59ee716 , da699f6a16 ,f64ed78516 , 110b7aa916 , 5fa2ef6416 , ba26aeb116 ,a7cd1c4516 , 3384e7a216 , 567d449c16 , 0ba6490516 ,
946267f016 , 910c58bf16 , 0257c49e16 , 60783c5d16 }IHV9= 73A70AC09AC9B2233ECC7BE4C30C6488= {c00aa77316 , 23b2c99a16 , e47bcc3e16 , 88640cc316 }IHV90= 73A70AC0FAA8B2239EAB7BE423EC6388= {c00aa77316 , 23b2a8fa16 , e47bab9e16 , 8863ec2316 }

δIHV9
δb9

= {0, δb9 , δb9 , δb9 }= −25 − 27 − 213

79

80

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.6

Block 6 of 8

Table D-16: Differential Path - block 6
Using δm11 = +23t
Bits Qt : b31 . . . b0
−311000000 00001010 10100111 01110011−210001000 01100-++ +++01100 --+00011−111100100 01111011 1-+01-++ +0-11110
000100011 10110010 1-+0100- 1++11010
1.1..0-+. +..+..0. .....00- 0++.10..
200..-0+. +..-..+. .11..1.. .-1.+0..
31-1.-1.1 ...-..+. ^.1..0.0 .1-.0+..
4
1+....11 0.!..... +^+..... .++.1-1.
50-00101+ 10.00^00 0+000000 0++0-100
61011110+ 01011-11 10101111 1.0100-1
7
101...+0 -....0.. .1.-.... .1-.11+.
80.+...10 +.!..0.. .-.+.... ..00+0+.
9
0.+.!.1- -.0..... .0.1...0 ..-.++..
10
10-0.001 -00.^000 0-.0.001 ..01.-00
11
11-10100 -1-0-111 1000011+ 00010-111200+000-1 10-11111 1-00000+ 101-0100
130000++-1 0-0+++++ +1+++0-- -+++0-++14+------+ -----111 0+------ 1------0
15
1111111- 1+101011 00011-.0 110-1010
16+01-0101 0100+..0 .00011^- .011001.
17...0...+ .1..0..1 .....1.. ...-.--.
18^..+...+ ....0..- ...0...^ 0..-....
19...+..01 ....-... ........ 10.1.^^.
20...0.01- ..0....^ ...+.... +1.0..0.
21...1..-. ..1.^... ...+.0.. 1-....1.
22.....-0^ ..+..... 0..-.... 0.....+.
23.0...-1. ........ 1..-.+.. .^......
24.1...+.. ..^..... -..1.+.. ......^.
25.-...+.. ........ 0..0.-.. ........
26.....+.. ........ 0....0.. ....0...
27.^...1.. ........ 1....1.. ...01...
28.....0.. ........ +....... ...1-...
29........ ........ ........ ...-1...
30........ ........ ^....... ...1-...
31........ ........ ........ ...-+...
32........ ........ ........ ...0....
33........ ........ ........ ...!!...
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ ........ ..+..... ........
63........ ........ ..+..... ........
64........ ........ ..+..... ........

#
32
32
32
32
15
15
16
14
31
31
14
14
13
25
32
32
32
32
31
27
9
9
9
11
9
8
7
7
5
4
6
4
2
3
2
0
2
0

D.3

Differential Paths

Table D-17: Block 6 found using path in Table D-16
M10

= B9 82 96 C0 AB 9F E5 B1 D3 53 88 2E 26 C1 F7 21
B4 18 99 D9 72 B5 A1 D5 05 0B 68 45 36 44 80 10
AF 8C 7A FF 7C E8 EA CC B9 B1 FB BD C9 29 D4 F5
D4 99 FB 81 29 24 DF 30 2C B3 C4 50 23 38 62 97= { c09682b916 , b1e59fab16 , 2e8853d316 , 21f7c12616 ,d99918b416 , d5a1b57216 , 45680b0516 , 1080443616 ,
ff7a8caf16 , cceae87c16 , bdfbb1b916 , f5d429c916 ,81fb99d416 , 30df242916 , 50c4b32c16 , 9762382316 }0
M10= B9 82 96 C0 AB 9F E5 B1 D3 53 88 2E 26 C1 F7 21
B4 18 99 D9 72 B5 A1 D5 05 0B 68 45 36 44 80 10
AF 8C 7A FF 7C E8 EA CC B9 B1 FB BD D1 29 D4 F5
D4 99 FB 81 29 24 DF 30 2C B3 C4 50 23 38 62 97= { c09682b916 , b1e59fab16 , 2e8853d316 , 21f7c12616 ,d99918b416 , d5a1b57216 , 45680b0516 , 1080443616 ,
ff7a8caf16 , cceae87c16 , bdfbb1b916 , f5d429d116 ,81fb99d416 , 30df242916 , 50c4b32c16 , 9762382316 }IHV10= DE56FC8A3A0A1FEBBE6E537DB6629AC4= {8afc56de16 , eb1f0a3a16 , 7d536ebe16 , c49a62b616 }

0
IHV10

= DE56FC8A9A091FEB1E6E537D16629AC4= {8afc56de16 , eb1f099a16 , 7d536e1e16 , c49a621616 }δIHV10δb10= {0, δb10 , δb10 , δb10 }= −25 − 27

81

82

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.7

Block 7 of 8

Table D-18: Differential Path - block 7
Using δm11 = +229t
Bits Qt : b31 . . . b0
−310001010 11111100 01010110 11011110−2
11000100 10011010 01100010 -0-10110−1
01111101 01010011 01101110 -0-11110
011101011 00011111 000010-+ +0-11010
1..0..0.. ....11.. 0-0-..01 -1-.....
2.1.!0+.. ....1+.. -0++..00 --+.....
3.1!.01.. .0..+-.. 1-0-.... --+.....
4!-..-1.. .0..+-!. +1++.... .+......
5!-00-.00 ^-001-.0 101+0000 1+000000
6!+11-011 ++11--01 1.+-1111 1.111111
7!1..-... 00.^--.! -.01.... .1^.^...
8!1..+... 10!-.... -.0-.0.. ..+0+..0
9..!.1... ...010.. -..+.0.. .!001^.0
10
00.!-010 00.1..10 .00+!+.0 .01+1-111
110.-111 1100^011 01110+01 001-000+12.11^00+1 0010+1+^ 00^1111. 1-0-0+-0
13^1+----0 1-0+0+0- +++++++1 +--+-++0
14--1110-+ +++++0+1 00000010 +--0---.
15
1+1+1-1- 011-1+10 0000000- 011-.10.
1601...00+ 10111+1. ..+..1.. 100-^01.
17.0.^.+.1 .1.^.+.. ..-..1.^ .0.0..0.
18.......1 .+...+.. ..1..+.. .1.1..1.
19
0....^.+ ....0-.. ..-..... .-....-.
20
1...0... .^..1-.. 0....^.. .1.....0
21+...1..^ ...0-0.. 1.^..... .0....^022....+... ...1.^.. +....... .1.....+
23^......0 ..0-^... 1....... .+.0....
24....^..1 ..10.... 0.....0. ...1...^25.......- ..-+.... ........ .^.-....
26..0..... ...-.... .....0+. ........
27..1....^ ..^1.... .....1+. ...^....
28..+..... ...0.... .....+-. ........
29..0..... ........ ......0. ........
30..-..... ........ .....^1. ........
31..-..... ........ ........ ........
32........ ........ ........ ........
33..!..... ........ ........ ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ ........ ........ +.......
63........ ........ ........ +.......
64........ ........ ........ +.......

#
32
32
32
32
13
15
14
13
30
30
15
15
14
25
31
30
32
31
30
21
13
8
8
9
11
6
8
8
5
4
7
4
2
3
1
0
1
0

D.3

Differential Paths

Table D-19: Block 7 found using path in Table D-18
M11

= 93 96 B3 A4 6C D0 FF 7F 14 26 71 1C 45 92 97 B6
5D 1C EF 66 C1 87 51 E0 94 BF 08 F3 B2 98 1C 5C
CE 52 D9 63 D5 A4 25 9A 64 55 7E 4D 1B 9E FE 0D
9A 51 6D 1E 6E C8 BB 37 06 68 25 AE A6 36 16 60= { a4b3969316 , 7fffd06c16 , 1c71261416 , b697924516 ,
66ef1c5d16 , e05187c116 , f308bf9416 , 5c1c98b216 ,63d952ce16 , 9a25a4d516 , 4d7e556416 , 0dfe9e1b16 ,
1e6d519a16 , 37bbc86e16 , ae25680616 , 601636a616 }0
M11= 93 96 B3 A4 6C D0 FF 7F 14 26 71 1C 45 92 97 B6
5D 1C EF 66 C1 87 51 E0 94 BF 08 F3 B2 98 1C 5C
CE 52 D9 63 D5 A4 25 9A 64 55 7E 4D 1B 9E FE 2D
9A 51 6D 1E 6E C8 BB 37 06 68 25 AE A6 36 16 60= { a4b3969316 , 7fffd06c16 , 1c71261416 , b697924516 ,
66ef1c5d16 , e05187c116 , f308bf9416 , 5c1c98b216 ,63d952ce16 , 9a25a4d516 , 4d7e556416 , 2dfe9e1b16 ,
1e6d519a16 , 37bbc86e16 , ae25680616 , 601636a616 }IHV11= DCA82596835B2D4F2EDB818BFEE0D521= {9625a8dc16 , 4f2d5b8316 , 8b81db2e16 , 21d5e0fe16 }

0
IHV11

= DCA82596635B2D4F0EDB818BDEE0D521= {9625a8dc16 , 4f2d5b6316 , 8b81db0e16 , 21d5e0de16 }δIHV11δb11= {0, δb11 , δb11 , δb11 }
= −25

83

84

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.3.8

Block 8 of 8

Table D-20: Differential Path - block 8
Using δm11 = +227t
Bits Qt : b31 . . . b0
−310010110 00100101 10101000 11011100−200100001 11010101 11100000 11-11110−1
10001011 10000001 11011011 00-01110
001001111 00101101 01011011 -++00011
1..1..... ......0. ..+-.... 0-+.....
2..00.... ....0^-. ..1+.... 1-+.....
3!.+0..1. ....0-+. ..1+.... .0-.....
4.!0+..0. ....-1-. ...+.... .-+.....
5..+-..-. ....+1-. .1...... .1-.1...
6!.0-..0. ....1... .0.1.!.1 .10.00..
7..1+..01 ....0.0. !+.....0 ..0.+1.1
8!..0..-1 .......! .-.^...- ....-+.0
9.!.0..0+ ......0. .+1-...+ ....1-.10......1+ .1....1. .100...+ 0.0.0-.11.1...11+ .00101-1 !1+0.1.+ 0.101-10
1200^0000- .-101111 .0-000.1 +^-10001
13
0+-00-+1 ^0--++-- ^-1+1-.- ++++---14+110+--- ---+0+-- -----100 .1110100
15
101-1-11 101010.0 1+1001.1 11110-016
10010010 +00-.1^1 00101+.0 .......17
01.-.0.. ...0...+ .0..0..1 .....^.1
18
1+.-.... ^..+...+ ....0^.- ...0...019+0.1.... ...+..01 ....-... ........
20.-.0..0. ...0.01- ..0....^ ...+....
21^-....1. ...1..-. ..1.^... ...+.0..
22.0....+. .....-0^ ..+..... 0..-....
23.1...... .0...-1. ........ 1..-.+..
24......^. .1...+.. ..^..... -..1.+..
25........ .-...+.. ........ 0..0.-..
26....0... .....+.. ........ 0....0..
27...01... .^...1.. ........ 1....1..
28...1-... .....0.. ........ +.......
29...-1... ........ ........ ........
30...1-... ........ ........ ^.......
31...-+... ........ ........ ........
32...0.... ........ ........ ........
33...!!... ........ ........ ........
34 − 60 ........ ........ ........ ........
61........ ........ ........ ........
62........ ........ ........ ..+.....
63........ ........ ........ ..+.....
64........ ........ ........ ..+.....

#
32
32
32
32
7
10
11
10
10
13
13
11
12
13
24
29
31
31
30
23
11
11
7
10
9
8
7
7
5
4
6
4
2
3
2
1
2
0

D.3

Differential Paths

Table D-21: Block 8 found using path in Table D-20
M12

= 2B D7 D1 16 25 A0 6A 90 73 9B 4D 0A 06 EA 87 2A
3A F9 EB A1 26 29 BE D6 79 40 56 1B D9 37 4A 89
D6 0F 0D 72 2C 9F EB 68 33 EC 53 F0 B0 FD 76 A2
04 7B 66 C9 0F CE B1 D2 E2 2C C0 99 B9 A4 B9 3E= { 16d1d72b16 , 906aa02516 , 0a4d9b7316 , 2a87ea0616 ,a1ebf93a16 , d6be292616 , 1b56407916 , 894a37d916 ,
720d0fd616 , 68eb9f2c16 , f053ec3316 , a276fdb016 ,
c9667b0416 , d2b1ce0f16 , 99c02ce216 , 3eb9a4b916 }0
M12= 2B D7 D1 16 25 A0 6A 90 73 9B 4D 0A 06 EA 87 2A
3A F9 EB A1 26 29 BE D6 79 40 56 1B D9 37 4A 89
D6 0F 0D 72 2C 9F EB 68 33 EC 53 F0 B0 FD 76 AA
04 7B 66 C9 0F CE B1 D2 E2 2C C0 99 B9 A4 B9 3E= { 16d1d72b16 , 906aa02516 , 0a4d9b7316 , 2a87ea0616 ,a1ebf93a16 , d6be292616 , 1b56407916 , 894a37d916 ,
720d0fd616 , 68eb9f2c16 , f053ec3316 , aa76fdb016 ,
c9667b0416 , d2b1ce0f16 , 99c02ce216 , 3eb9a4b916 }IHV12= 505D9746FAB00B328018DBC34A87DF11= {46975d5016 , 320bb0fa16 , c3db188016 , 11df874a16 }

0
IHV12

= 505D9746FAB00B328018DBC34A87DF11= {46975d5016 , 320bb0fa16 , c3db188016 , 11df874a16 }δIHV12= {0, 0, 0, 0}

85

86

D CHOSEN-PREFIX COLLISION EXAMPLE - COLLIDING CERTIFICATES

D.4

RSA Moduli
Table D-22: Upper Partial RSA Modulus 1

Sb kSc= XkY kZkM5 kM6 kM7 kM8 kM9 kM10 kM11 kM12
= 1A09B4CB 40C7267A AF017F9B A4742581 8DC84F86 736E9072 28BBE877 0203858D
8CF1837A FF5E6C22 13036AF3 D95C77E9 C2237D60 8CC4A9FB 97307BBF 9828612F
1599E261 5BCCDEDA 5930532F B3DD1172 78E49440 1433630E 7461C1DC 9B801B2E
552015A5 13FF7AE7 973EF44B 8352E4E0 4979B31E B600654D 51F4A481 CEBE3F0B
D099D130 D1456FAB E04A3E98 85C8C4FB 297B86B5 7752CD64 19809FE3 7E6286F0
7732D1E0 69A5B4E5 6670B8BB BAE5C211 742A131D 05711CF1 FE22AF93 3F1EEF22
4762E3AA DAC17C40 E448CA41 A879A03D 3CF665F2 39C7F3FE 82B384E8 35E7C9E8BDEE30C2 68A21212 84789DF4 2F44906F 19B79026 464436E1 DA64FA0C 53A377FA
0D2B012B 7DDC2855 DAE5B551 51E28034 112120B5 E79EC5F2 6A9F69DA 85D74EF6
A97A0B11 64EFA25F B1AE26BA 451CCDA7 A2E78433 9C447D56 2549A60B F0676294
BF580C91 9EC45702 5D3C7860 B98296C0 AB9FE5B1 D353882E 26C1F721 B41899D9
72B5A1D5 050B6845 36448010 AF8C7AFF 7CE8EACC B9B1FBBD C929D4F5 D499FB81
2924DF30 2CB3C450 23386297 9396B3A4 6CD0FF7F 1426711C 459297B6 5D1CEF66
C18751E0 94BF08F3 B2981C5C CE52D963 D5A4259A 64557E4D 1B9EFE0D 9A516D1E
6EC8BB37 066825AE A6361660 2BD7D116 25A06A90 739B4D0A 06EA872A 3AF9EBA1
2629BED6 7940561B D9374A89 D60F0D72 2C9FEB68 33EC53F0 B0FD76A2 047B66C90FCEB1D2 E22CC099 B9A4B93E

Table D-23: Upper Partial RSA Modulus 2
Sb0 kSc0000= X 0 kY 0 kZ 0 kM50 kM60 kM70 kM80 kM90 kM10
kM11
kM12
= EE73E7D6 B3B34FBA A1393D02 A4742581 8DC84F86 736E9072 28BBE877 0203858D
8CF1837A FF5E6C22 13036AF3 D95C77E9 C2237D60 8CC4A9FB 97308BBF 9828612F
1599E261 5BCCDEDA 5930532F B3DD1172 78E49440 1433630E 7461C1DC 9B801B2E
552015A5 13FF7AE7 973EF44B 8352E4E0 4979B31E B600654D 51F4A381 CEBE3F0B
D099D130 D1456FAB E04A3E98 85C8C4FB 297B86B5 7752CD64 19809FE3 7E6286F0
7732D1E0 69A5B4E5 6670B8BB BAE5C211 742A131D 05711CF1 FE32AF93 3F1EEF22
4762E3AA DAC17C40 E448CA41 A879A03D 3CF665F2 39C7F3FE 82B384E8 35E7C9E8BDEE30C2 68A21212 84789DF4 2F44906F 19B79026 464436E1 DA65FA0C 53A377FA
0D2B012B 7DDC2855 DAE5B551 51E28034 112120B5 E79EC5F2 6A9F69DA 85D74EF6
A97A0B11 64EFA25F B1AE26BA 451CCDA7 A2E78433 9C447D56 0549A60B F0676294
BF580C91 9EC45702 5D3C7860 B98296C0 AB9FE5B1 D353882E 26C1F721 B41899D9
72B5A1D5 050B6845 36448010 AF8C7AFF 7CE8EACC B9B1FBBD D129D4F5 D499FB81
2924DF30 2CB3C450 23386297 9396B3A4 6CD0FF7F 1426711C 459297B6 5D1CEF66
C18751E0 94BF08F3 B2981C5C CE52D963 D5A4259A 64557E4D 1B9EFE2D 9A516D1E
6EC8BB37 066825AE A6361660 2BD7D116 25A06A90 739B4D0A 06EA872A 3AF9EBA1
2629BED6 7940561B D9374A89 D60F0D72 2C9FEB68 33EC53F0 B0FD76AA 047B66C90FCEB1D2 E22CC099 B9A4B93E

D.4

RSA Moduli

Table D-24: Lower Partial RSA Modulus Sm
Sm= 0000000F 54A89517 6E4C295A 405FAF54 CEE82D04 3A45CE40 B155BE34 EBDE7847
85A25B7F 894D424F A127B157 A8A120F9 9FE53102 C81FA90E 0B9BDA1B A775DF75
D9152A80 257A1ED3 52DD49E5 7E068FF3 F02CABD4 AC97DBBC 3FA0205A 74302F65
C7F49A41 9E08FD54 BFAFC14D 78ABAAB3 0DDB3FC8 48E3DF02 C5A40EDA 248C9FF47482850C FDFBDD9B C55547B7 404F5803 C1BB8163 2173127E 1A93B24A FB6E7A80
450865DB 374676D5 76BA5296 CCC6C130 82D1AB36 521F1A8A D945466B 9EF06AF4
3A02D70B 7FB8B7DC 6D268C3D BA6898F6 552FA3FB B33DCBFA DA7B33FA 75D93AFE
262BD37A FF75995F D0E9774B A5A26A7C 443FF34E 461502A2 CB777E98 2D007375
14B88ED2 8D61F428 E88387DF 2BF02230 AD17A9D4 4FF36485 0A07DB42 A7826AC2
EE3899CA C3EC2747 21D476D9 6658F537 16676587 F8FF14DB 8DE6741A FA2206DB
A3B11828 BA87C6E1 E88A022F 1AA8DDD0 37EAB049 B5C7D305 3D0A63D7 861DEA07
B3D8B720 DE068CF4 7E657BB4 4450B85D 52F749D5 9572DF0C 0E3433B4 7C9AA19A
856F1DC3 CDADBAFB 143035C8 5A53AF57 22038F76 5C0D621B 66B69FFF FD091D4A
661A453B F1DAED1A 3A2341B3 7D7F623B 158F6EC0 2B49A253 64430FCB 5861483E
1E9543ED 2EE7E54A 4C108A6E 64194098 0EE60D14 AEE559AF 30037E75 B2309CE0
21FFE310 9BF20538 92AB0AE4 03516E2A B58067F7

Table D-25: RSA Moduli
n1n2= Sb kSc kSm= Sb0 kSc0 kSm= p1 · q 1= p2 · q 2

Where
p1

= FF6E89C1 C29EC1B6 DCAC6227 EAD2226C E7E07D35 3F2296F7 940E6154 17A8363C
482171DE ECC75091 E5934F7E 7C1D6EAC 90B3A8D7 AD7C39CD A6364D79 CE8D9063
906933C9 64EAACF5 003B5D3A 1DF30C83 74C3CE80 4E54B4A8 DB6AEF33 166E282F
8425B5A9 9E640BC0 F87C3507 C888119E 2479DCF4 4E88538B CE9E7BC3 A7D7A454
78F69937 9FA845DB 43636513 FB3C2468 D32AB56F FD4A49C4 D73EB135 6C6FFEAA
921B8A27 6DF4CA34 512835C4 CCC3E6B2 77A689F5 73009A2B 90E985FD E63CE7F3
59D30AC1 92A2C97F 05C9DCEC 46B17355 0F926164 9F4613E8 B349B5C4 CB090692
8278DBFF 534B02E8 5A305B93 069BA793 5893BE68 F9C197

p2= F134344B 72A468C3 EA7A5B2F 97CDFE2F DB9194CE 47B03C85 9A4E8A0F BE2B1B1B
55CE1E96 5409BB5F 0F07F2CF B67C3FE3 27853D37 8D0038A6 94A16AAD 84038E18
D69746A4 C1126D21 D5839065 F0885C60 BB174114 B76B003F 368AB2EF 6FF46A59
34DBCBE1 1517FD9E 6F418A06 F4F3BE6A ABB77B2F 999B4FE9 76C8096E C0133761
AFD0149B 4816EAC9 2C06E1AF 60C05F19 FDA2A23A B4A5CA4A 05403033 EB65FB3C
648B0536 09C5C43A 4EE308CA BA8E639C EB7C297D 56A398DD C35E42B7 31AFC9C022414B8F 6A94A280 E4D9EF28 F995553B 3FA3E308 19911F98 43276163 91336C18
85EC8062 A1D2CA68 990C0174 561DAE3F 6B3C7378 2D53BD

87