Possible MD5 Collision Found

[dawithers]

http://slashdot.org/articles/04/08/17/0030243.shtml (http://slashdot.org/articles/04/08/17/0030243.shtml)

SHA-0, MD5, HAVAL-128, and RIPEMD-128 all in 7 days time!

This is a VERY VERY busy time in crypto!

JLC

[Digital Parasite]

The researchers who broke this hash algorithms will be presenting the results tonight at 7pm PDT at the Crypto 2004 conference in California. The rump session is going to be streamed on the web:
http://www.mail-archive.com/cryptography@metzdowd.com/msg02585.html

The paper about the hash collisions has just been posted on eprint here:
http://eprint.iacr.org/2004/199.pdf

[Guilherme]

Does this discovery change anything on the MD5CRK Project? For example, will this discovery be used to find MD5 collisions with MD5CRK software?

[jlcooke]

The full paper will likly be needed.

It kinda renders md5crk moot.

When the paper is released showing exactly how it was done; I'll release a md5crk v1.0.8 which will not be distributed, but rather a utility to find more collisions in md5.

It's looking like MD5 is wide open to collisions now, far more then many thought possible. A review of hash-function design may be required. Much like how early block ciphers had to adapt to DC and LC.

JLC

[Digital Parasite]

Note, the paper on eprint was updated today with new values I think to correct their endian problems.

[fgrieu]

Indeed the paper is correct.

The MD5 hashes of the (different) 1024 bit strings with hex dump:
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a0851 25e8f7cdc99fd91dbdf280373c5b960b1dd1dc417b9ce4d897f45a6555d535739ac7f0ebfd0c3029f166d109b18f75277f79 30d55ceb22e8adba79cc155ced74cbdd5fc5d36db19b0ad835cca7e3
and:
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a0851 25e8f7cdc99fd91dbd7280373c5b960b1dd1dc417b9ce4d897f45a6555d535739a47f0ebfd0c3029f166d109b18f75277f79 30d55ceb22e8adba794c155ced74cbdd5fc5d36db19b0a5835cca7e3
is identical:
a4c0d35c95a63a805915367dcfe6b751

I've included a ZIP with these files.

Deriving other collisions now is easy (a trivial method is to extend these).

François Grieu

[Guilherme]

Originally posted by jlcooke
The full paper will likly be needed.

It kinda renders md5crk moot.

When the paper is released showing exactly how it was done; I'll release a md5crk v1.0.8 which will not be distributed, but rather a utility to find more collisions in md5.

It's looking like MD5 is wide open to collisions now, far more then many thought possible. A review of hash-function design may be required. Much like how early block ciphers had to adapt to DC and LC.

JLC

DC and LC? I think DC = "Distributed Computing". What is LC ?

[jlcooke]

Originally posted by Guilherme
DC and LC? I think DC = "Distributed Computing". What is LC ?

Differential Cryptoanalysis and Linear Cryptoanalysis with respect to block ciphers.

[hammingweight]

My feeling is that Wang et al's results have made this project, to use JLCs's adjective, "moot".

It was certainly fun while it lasted and I'd like to thank JLC for the immense effort he put into this project.

[Minty]

Wow - this is dynamite - is anything safe from Chinese crackers?! :) :allhail:
Should we go ahead and purge our DPs now just for completeness? I suppose this means we're going to have to find another distributed computing project :cry: Also, I guess the discovery qualifies for the whole $10,000 prize? Old Chinese saying (in best Chinaman accent) "Much quiet about prize keep many dollar in bank!!!" :rotfl: You never know - if they did claim it they'd probably have to give it to the state, so shhhhhh! :D

[jlcooke]

Yes I agree. md5crk doesn't have much point. "Mission accomplished" in an optimistic sense. But really, it was Wang who make finding a collision a < 1day process.

I will be making an announcment and blocking DPs from submitting in a little over 24hrs. Then I will have the entire md5crk database available (download or snail-mail - havn't decided) as a md5crk.msql script.

Cheers, and thanks for all the fish!

JLC

[Guilherme]

Originally posted by jlcooke
I will be making an announcment and blocking DPs from submitting in a little over 24hrs.

Hey man, give me 3 days, so I can finish and upload my last workunit. :cheers:

[Jewbacca]

Sad to see this project go and I hope there will be more great ideas coming out of the folks behind MD5CRK.

I've had so much fun making strides through the rankings too, to the 50s in just a matter of a month and a half here.

I came here after giving up on SETI@Home when their initial release of BOINC was so buggy. I used to do GIMPS (http://www.mersenne.org/) and may go back there, maybe?

What project now do you all see yourselves graciously giving up your idle cycles to? Please post some suggestions.

Jewbacca
38K DPs

[Bok]

I'd noticed your steady rise up the ranks in the team and the project!! :smoking:

Are you mainly interested in crypto work, how about medical science? D2OL could use some help :)

:cheers:

Bok

[Jewbacca]

:D Thanks, Bok. I was due to "barbeque" you in just under 16 days anyway. I smell conspiracy :umm:

I'll check out D2OL

Jewbacca
39K DP

[Death]

If you guys don't want to abandon DC after md5crk ends check this

http://seventeenorbust.com

very interesting project...

[Guilherme]

I joined "Find-a-Drug" (http://www.find-a-drug.org/). My idle computer cycles will help people, in research for drugs against cancer, malaria, AIDS, etc.