Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Bibliography on MD5 attacks

144 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

0 new messages