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'."

Comments

Oh, lovely, distributed Javascript computing

[Anonymous Coward]

Perhaps we could tie this to some sort of micropayment system. You come do distributed work on my website, and you get to view it. Some third party pays me for the cycles, and I have a new revenue stream!

Are there any known MD5 collisions today?

[GGardner]

Last time I looked into this, which was several years ago, there were no known different strings which had the same MD5 hash. I thought this was remarkable. Are there any known ones today?

Re:Are there any known MD5 collisions today?

[iggymanz]

more accurate to say it's very unlikely two string have same md5 value - but raise two to the power of the number of bits in an md5 hash, and there's at least that probability that two strings will have same hash. Of course, question is with real world strings is it even more likely than that huge 1:n number that 2 will match??? Hence this project, which I don't think is ethical or good way to find out.

Re:Are there any known MD5 collisions today?

[ilsa]

Reason #83 that MD5 is an inadequate method of identifying MP3s. Hashsums are only "practically unique."

Re:Are there any known MD5 collisions today?

[The Snowman]

Last time I looked into this, which was several years ago, there were no known different strings which had the same MD5 hash. I thought this was remarkable. Are there any known ones today?

MD5 is a hash. Hashes have three defining characteristics. First, the same input always produces the same output. Second, a small change in input produces a large change in output. Third, collisions are relatively rare -- it should be uncommon for two input strings to produce the same output string. Of course, with 2^128 output values and an infinite number of input values, there are an infinite number of inputs that produce the same output, theoretically.

Anyway, there are a few strings that produce identical outputs, using two dictionary words. I cannot find them at this moment, although I know where I saw them. Google and on-site searching mechanisms aren't helping. Oh well. I tried.

Re:Are there any known MD5 collisions today?

[Tom7]

Considering there are an infinite number of strings that will map to a single MD5

That's probably, but not necessarily, true.

I'd say there is a chance we'll find one sooner or later.

Yeah, it's about 1 in 2^128. There aren't even enough electrons in the universe to write down all the possible MD5 hashes, not to mention the strings that might hash to them.

Whoever made this...

[coene]

Make sure to take out the warning message "ok fine then, you don't want cookies..." that pops up when you disallow it yer cookies (buy yer own thx!). This was surely a debug message, it's not useful anymore ;)

Re:That's really interesting...

[herrvinny]

It's run in a sandbox, and the sandbox is pretty restrictive. No writing to the hard drive, no network access other than connecting back to the website the applet came from, a requirement that all applet created windows have a "WARNING: APPLET WINDOW" box on the bottom, etc. And the process of signing an applet is downright screwy and often doesn't work for all platforms.

no thanks

[mercuryresearch]

As someone who intentionally runs a low-performance box as a primary system (VIA Epia 533) I'd be pretty unhappy with some snarfing up a few cycles. Junked-up web sites with flash and excessive java/javascript are REALLY noticable when you're browsing at the low end of the power curve.

I run a cpu monitor in the background and when a site wants to run one of the more annoying classes of advertisements, utilization usually pegs... I can't imagine what something that intentionally sucked cycles would do.

Re:Not very intensive.

[smart_ass]

With Mozilla I got the same ... but when I opened it up in IE 6.0 it hogged all resources.

RFI: "collision" means?

[Anonymous Coward]

Newbie here. I searched around for "md5" and "collision", but only found sites that seemed to already understand what a collision is. Well, can someone explain what an md5 collision is? I'd like to continue reading the article....
Is it simply that, since the hashing is a reduction operation, that multiple (different) messages can have the same hash? If so, then can someone explain the utility of searching for such things?...I'm afraid I can't see the dark implications of such a functionality. Thanks in advance.

Re:Not ethical

[pla]

I respect the effort and ingenuity, but the rationale that "hey, we're helping solve a problem" somehow justifies stealing someone else's resources... it's just wrong.

Although letting visitors know about this would certainly seem nicer, I don't think I'd actually consider it as outright unethical.

For one thing, considering the number of websites out there that try to feed outright malicious code into our browsers, this looks very very tame by comparison. It uses a few CPU cycles, but has no long-term effects on the visitor.

For another, this seems no different that sending the visitor a few banner ads - Just a way of "paying" for the content. For most of the world, bandwidth costs far more than CPU time, so in effect, this "charges" the user less per visit than most advertisements. From some quick n' dirty calculations, the bandwidth for 35k of banner ads costs me 0.082 cents, while the electricity for a full hour of CPU time (on a PIII/933) costs me only 0.0045 cents... Literally 18 times more.


Finally, I can (and do) keep Javascript disabled in my browser. Advertisements, on the other hand, I do my best to block, but a few still manage to sneak through.

This plus popunders? ne The other way to pay.

[IBitOBear]

OK, so an evil webmister makes a pop-under containing this kind of code and puts it up when you visit his porn site (optionally by mistyping "google" in your address bar.)

Heck, (google|SlashDot|your legitimate business) just has a tiny inset on their page: "This box is using your spare CPU cycles to help us pay for this site or service. Subscribers do not see this box. Click here to subscribe."

It could work.

In the popunder case it is vile and abusive. In the legitimite and well advertised case it is totally fair.

seems a bit easy to highjack

[doublebackslash]

With this being posted here someone with more knowledge of java than me is going to have the idea to give back false results. That is the reason for an install, to give the project mamgers control.
I bet that sometime son they are going to be finding lots of collisions, all results from the same IP.
Hope they have some sort of filter.

I like the idea, but

[tulare]

It crashes Safari. Now, admittedly, I don't know whether this is a Safari bug, a Java bug, a bug in the applet, or some combination thereof, but here's what happens to me:
I load the thing in its own tab, have a look, look at the neat code that loads an IFRAME, etc. Ho-hum, nice idea, let's see where it goes, cmd-W to close the tab. Whups! The entire browser window closed, including all the tabs which I hadn't got around to checking yet! Safari is still running in the foreground, but I just lost its window.

Anyone interested enough to debug this? I'm not =P

Not Everyone is as quite so Advanced

[ledbetter]

Most people who browse websites are quite simply unaware that their computer even contains a concept called Idle CPU Cycles, or that there is any way to get a CPU % reading from their computer. Besides, not everyone is so miserly with their CPU time. Most users also have a short attention span.

If the user, whose browser visits such a website that opens up a number crunching applet, notices that their whole computer just became slower, then they'll leave the website. And the applet will be alive for less time. Therefore successful applet projects that are accepted and deployed by various webmasters, which want to obtain the most results would make sure that the applet is as unobtrusive as possible. Otherwise the user will browse away from the page (and or close the browser window all together), and the applet's lifespan will be short.

Finally a possible way to pay for web traffic?

[waferhead]

Once they have gotten this working, and assuming there is a commercial need for these cycles that exceeds the cost in bandwith, a site could do as others have suggested, and require you to run this app (ala netzero etc) in order to acess content on the site.

Beats pop up ads, anyway.

Ulterior Motives . . .

[Dausha]

But, could this not be used to build a hash table of all MD5 sums? If all possible MD5s were known by one source, what is to prevent them from using this as a simple lookup to crack MD5-based passwords? Even if they only focused on short strings (say, typical password length) they could go a long way to defeating another security mechanism.