Finding MD5 Collisions With Chinese Lottery

Stanislav Shalunov writes "Jean-Luc Cooke posted a Usenet article describing a distributed webpage-based effort (Chinese Lottery) to find a collision in the MD5 function. All you need to do to participate in the effort is visit the URL that loads the code. The author comments: 'What is interesting about this approach - when we reach final release stage - is that any website that adds this small snippet of code to their pages will have their visitors working on the problem for the duration of their visit to the site'."

Re:How do I add this to my site?

[coene]

Just embed the applet into your HTML, view the source of that page - you'll get it.

That's really interesting...

[herrvinny]

That's a really interesting way of doing it. For the people who don't know, here's a quick explanation:

Java Applets, because of the sandbox they're run in, can't open up a network connection to any website, except for the websie they came from. Presumably, what they're doing is creating a small Java applet, that when loaded, executes some logic, then opens up a network connection back home and sends the results.

Fascinating. This way, you don't have to bother installing something and hope it doesn't fsck up your computer. It might be slightly less efficient than a dedicated, installed program, but this way, they can harness the power of a computer just casually browsing a web page. Very innovative.

Not very intensive.

[LoneIguana]

It certainly isn't using very many cpu cycles, the OS reports that my webbrowser is using less than 1% of the available cpu power

Re:Normal Thread Priority

[mlk]

Java applets run as a different process to the browser, and it can (and very likely does) create a new thread, and set its priority to low.

For anyone wanting the code...

[Vaevictis666]

Here's the code:

<!-- try IFRAME, else use LAYER -->
<IFRAME SRC="http://www.jlcooke.ca/psearch/dmd5l.html" SCROLLING="NO" FRAMEBORDER="0" WIDTH="100" HEIGHT="32">
<LAYER SRC="http://www.jlcooke.ca/psearch/dmd5l.html" WIDTH="100" HEIGHT="32" CLIP="0,0,100,32"></LAYER>
</IFRAME>

It' s making an iframe that loads the applet, and just does its own thing - by loading in the iframe it can call back to their host, rather than yours :P

Someone should let him know that he needs to make his server parse .html files through PHP, 'cause he's got a PHP header that isn't being sent - oh yeah and better html please.

Re:./ effect = benefit??

[Darth Fredd]

Yeah, but do we all run Java enabled browsers? (lynx, links, etc)

I'm running No-Java-Opera right now:because the java enabled opera was 11 more megs.. ..and I have dialup.

Point is, geeky as we are, we're probably all expirementing with stuff.

NOT LIKE THAT YOU PERVERTS!!/

Re:really bad idea for real system administrators

[focitrixilous P]

Dude. Do you want to know the tax on your server? 3 lines of simple HTML. That doesn't sound like much of an extra complication, or CPU usage. Even the tiny applet is loaded off Their Server, meaning you do nearly no work to help these guys. You can debate the ethics, sure, but saying this is a mistake because of server issues is wrong.

Re:Oh, lovely, distributed Javascript computing

[sinistral]

It's not JavaScript, it's Java. Despite the names, they're vastly different.

Argggh! It's not ready yet!

[phr1]

It's really too early for Slashdot readers to try to run that code. As the usenet post said, it's alpha test. I'd actually call it pre-alpha. The usenet sci.crypt discussion is about ways to change the design so it can be hosted on multiple sites at the same time. Really, it would have been a lot better to wait for the author to make an announcement, before linking an ongoing discussion about a work in progress to the front page of Slashdot as if the code was ready for prime time. Ow!

Re:RFI: "collision" means?

[tstoneman]

MD5 is a hashing algorithm. It will take an input of theoretically any size and create a 16 byte number that maps to this string. Most security algorithms use MD5 (or SHA-1 or some other hashing algorithm) to verify that the plaintext or cryptotext has not been altered during transit.

Obviously, since a string can be an almost infinite length, there has *got* to be collisions somewhere, but so far, no one has found any.

Realize that 16 bytes = 128 bits = 3.40282367e38 different outputs of MD5. Given that the half-life of a proton is 10e31 years, you need to do about 1 per second before half of the universe ends for good. Or, if you want to finish it in 100 years, you would need to 10e20 per second.

You better start some time soon!

Anti-Javascript Post...

[evilviper]

This is just ONE MORE REASON YOU SHOULD DISABLE JAVASCRIPT.

Why is it when I say this stuff, nobody believes me?

If that's not enough, check-out my .sig (WARNING: Sig link is not FRIGGIN SAFE for work, home, or anywhere else).

Re:That's really interesting...

[Rich0]

Keep in mind that many websites use two-way communications with a Java applet. How is this a privacy violation?

A Java applet can't see what you're doing on your computer. It can't see your hard drive. It can't see what other processes are running, etc. It can only communicate within the confines of the browser window and well-marked pop-up windows that it can spawn. Security is enforced by the local JVM - which the user installs from a trusted source.

Java was designed the "right way". This isn't ActiveX - in which an applet can rummage though your files and send a copy of every one of them to whoever the applet author wants. Java applets run in a sandbox and can only execute a subset of the full Java language.

There really isn't anything to see here... Move along...

Re:Are there any known MD5 collisions today?

[lostchicken]

It can't be reversed. That's the point of MD5.

However, it is trivial to prove the fact that there are strings that have the same MD5 hash due to the fact that you can't represent 2^65 different numbers with only 2^64 keys.

Re:RFI: "collision" means?

[jrstewart]

The chance of an MD5 collision if MD5 were an ideal hashing algorithm is astronomically small. To get a 1% chance of a collision you'd have to test on the order of 2^63 samples (for the math behind this google for the birthday paradox; it's of the order of the sqrt of the size of the hash space) to find two that match. Never mind finding an MD5 which matches a chosen hash value.

This is a really big number.

Nobody's really concerned about MD5 hash collisions of reasonable corpii (corpuses?, forgive my pseudo-latin) if MD5 is actually a perfect hash, or somewhat close to it. What people are really concerned about is there being some weakness in MD5 where you can reverse the algorithm and given some MD5 hash (maybe not any hash, maybe just certain ones) and come up with strings which hash to that value.

For example, suppose that 2^127-1 is prime (it may well be but I'm too lazy to check). Then if you start pulling out random strings foo and using the remainder of foo mod 2^127-1 as your hash you'll also have a 1% chance of a random collision with a sample size of the order of roughly 2^63, as above. However there are some trivial collisions you can calculate, like 0*(2^127-1), 1*(2^127-1), 2*(2^127-1) all hash to the same value.

If the data you're feeding your hash algorithm is random (more or less) there's no reason to prefer the modulus algorithm over MD5. But if you're using it for cryptographic things the modulus algorithm is pretty useless, and it may turn out to fall down on many common inputs that MD5 gives good results for.

I may have goofed some of this, and there's lots more to be said about it but I've wasted enough time on this post as it is.

Re:RFI: "collision" means?

[tstoneman]

Actually, I think in the "Chinese Lottery" scenario, there is one string/hash pair that is chosen, and all the clients try other combinations of strings. Whoever gets the same hash will "win" the lottery. Thus, the web site wouldn't have to store anything except the returned plaintext that hashed to the same MD5 value.

I think the original "Chinese Lottery" scenario was if everyone one in China had a radio that was set to do encryption, and the Chinese government broadcasted a particular ciphertext that it wanted to encrypt, every radio would do the decryption using different strings until one of them got the answer. I think it would be under the guise of a lottery, so whichever citizen came back with the winning radio would receive a prize, and the Chinese government would have their cracked ciphertext.

Re:RFI: "collision" means?

[lxs]

You're basically correct. Theoretically many different inputs have the same md5 hash. However, the chances of finding two such inputs are very small. There is no real practical value to finding such a collision, other than to give a rough idea of what it takes computationally to find one. Since md5 is used to check the integrity of files like linux isos, it is important to know how secure the algorithm is.

It is a bit like SETI@home, It is very likely that we're not alone in the universe, but until we have empirical proof that we're not, nobody is truly satisfied.

Besides, if this was of true significance for national safety, funding would be found to run this on dedicated machines.

WARNING! WARNING! DANGER WILL ROBINSON!

[Crypto Gnome]

I dunno what they think they're doing, but they managed to consistently crash my browser in under 5 seconds.

YOU HAVE BEEN WARNED

• Windows XP PRO
• Athlon XP 2200+
• 1GB RAM
• Firebird 0.7+

Re:Short answer: yes

[jlcooke]

a collision in MD5's transform was found. But not on the whole hash.

Difference? The md5() function includes padding. The md5_compress() collision is cited here:

http://citeseer.nj.nec.com/denboer93collisions.h tm l

Re:Electrons in universe

[jlcooke]

read the sci.crypt post, I site a paper from van oorschot from 1994 describing exactly how to get MD5 collision. In today dollars/moores law, it would cost $100,000....anyone with good credit can find collisions in MD5.

Re:I don't get it

[jlcooke]

Read van oorschot's paper cited in my sci.crypt post. You'll start gettign mad at VeriSign, Amazon, SourceForge, et al for using MD5.

Re:RFI: "collision" means?

[jlcooke]

No respectable cryptographer uses MD5 for signatures anymore, they havn't for years - the industry hasn't caught up yet (TripWire, VeriSign, .rpm, .deb, md5sum, some PRNGs, etc)

This is the essance of why I'm doing this.

Look around for evidance of this movment in crypto circles (ie don't listen to /. posters... :) )