Bibliography on MD5 attacks

136 views
Skip to first unread message

Francois Grieu

unread,
Apr 2, 2004, 11:30:03 AM4/2/04
to
Below is my annotated bibliography on attacks against MD5
(or its round function).

Anyone knows something else worth mentioning ?


François Grieu

--

Hans Dobbertin: Cryptanalysis of MD5 Compress (1996)
<http://www-cse.ucsd.edu/users/bsy/dobbertin.ps>
<http://citeseer.ist.psu.edu/dobbertin96cryptanalysis.html>

This gives a numerical example of I, X1, X2 with
MD5compress(I,X1) = MD5compress(I,X2)
1-bit difference between X1 and X2.
Of course the value of I is not the initial MD5 value,
nor occuring in any known message, else the full MD5
would be broken.

--

Hans Dobbertin: The Status of MD5 After a Recent Attack
in CryptoBytes Volume 2 Number 2 - 1996
<ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf>
<http://citeseer.ist.psu.edu/243938.html>

More detailed account of the same result, with partial
explanation on how it was obtained.

--

B. den Boer and A. Bosselaers, Collisions for the compression
function of MD5.
Proceedings Eurocrypt'93
<http://citeseer.ist.psu.edu/289874.html>
<http://www.esat.kuleuven.ac.be/~cosicart/pdf/AB-9300.pdf>

This gives example, and method, to find I1, I2, X with
MD5compress(I1,X) = MD5compress(I2,X)
4-bit difference between I1 and I2.

--

P.C. van Oorschot and M.J. Wiener:
Parallel Collision Search with Cryptanalytic Applications
Journal of Cryptology, vol. 12, no. 1, 1999
<http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf>
<http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/pcs.pdf>

Expands on 1994 and 1996 works by the same authors.
This is an educated brute-force attack with cost about
2^64 hashes, and relatively little memory.
Best practical attack technique published, ongoing use at
<http://www.md5crk.com>

--

Thomas A. Berson: Differential Cryptanalysis Mod 2^32
with Applications to MD5.
Proceedings Eurocrypt'92
<http://cnscenter.future.co.kr/resource/crypto/algorithm/Symmetric/ec92Berson.pdf>

I do not even get what the author takes mod 2^32, nor what
results are claimed.

Jean-Luc Cooke

unread,
Apr 2, 2004, 12:36:52 PM4/2/04
to
Thanks Fran&ccedil;ois

I'll add these to the md5crk site. Except for Berson's find...that's
just silly. It's trying to to DC on the mod 2^32 + operation.

JLC


Francois Grieu <fgr...@francenet.fr> wrote:
> Below is my annotated bibliography on attacks against MD5
> (or its round function).

> Anyone knows something else worth mentioning ?


> Fran?ois Grieu

> --

> --

> --

> --

> --

--

Francois Grieu

unread,
Apr 5, 2004, 2:52:31 AM4/5/04
to
In article <c4k8bk$b9t$1...@driftwood.ccs.carleton.ca>,
Jean-Luc Cooke <jlc...@engsoc.org> wrote:

> Francois Grieu <fgr...@francenet.fr> wrote:
>> Below is my annotated bibliography on attacks against MD5
>> (or its round function).
>>
>> Anyone knows something else worth mentioning ?
>>

>> (..)


>> Thomas A. Berson: Differential Cryptanalysis Mod 2^32
>> with Applications to MD5.
>> Proceedings Eurocrypt'92
<http://cnscenter.future.co.kr/resource/crypto/algorithm/Symmetric/ec92Berson.pdf>
>>
>> I do not even get what the author takes mod 2^32, nor what
>> results are claimed.

> I'll add these to the md5crk site. Except for Berson's find...that's


> just silly. It's trying to to DC on the mod 2^32 + operation.

For each of the four MD5 round functions, Berson derives somewhat
systematically message differentials that give a high probability
of collision. He however claims no actual result on the full MD5.

While clearly not a breakthru, I do not discount Berson's work as
"silly". Reading it again, maybe now I get the idea:
consider f(m+d)-f(m) with operations caried mod 2^32, on each of the
four MD5 registers. I stand unconvinded that this approach is better
than redular DC in practice, but I'm ready to believe that it
simplifies derivation of differential probability in the case of MD5.

Sadly, I somewhat fail to exactly reproduce Berson's results.
For example the paper claims that for the message differential
W[ 8] += 1<<11;
W[12] += 1<<31;
W[13] += 1<<26;
the collision probability for the second round is 2^-2,
but experimentaly I get 2^-5. Did I miss something?


François Grieu

Reply all
Reply to author
Forward
0 new messages