Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Encryption Security The Internet

Finding MD5 Collisions With Chinese Lottery 303

Posted by simoniker
from the soon-to-be-distributed-slashdotting dept.
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'."
This discussion has been archived. No new comments can be posted.

Finding MD5 Collisions With Chinese Lottery

Comments Filter:
  • Uhh.. (Score:5, Insightful)

    by TCM (130219) on Wednesday December 31, 2003 @06:24PM (#7849470)
    From the link:

    You run an Applet, it reports to us the search results. Distributed computing without installing anything...and without people knowing you're stealing their idle CPU time. ;)

    I don't know about you but I wouldn't lean out the window with the fact that I'm stealing from others.

    Idle CPU time might be unused but I still want to know what my box is doing and why.
    • Idle CPU cycles are used to pre-zero pages, among other little tasks.
    • Re:Uhh.. (Score:4, Insightful)

      by Phillup (317168) on Wednesday December 31, 2003 @06:50PM (#7849662)
      I personally wouldn't call it "stealing". You pretty much agreed to run Java. Yes, you could be a clueless noob and knot *know* that your browser has it enabled... but, nobody is *making* you run java applets.

      I don't shove it down your pipe... you ask for it.

      Of course this line of reasoning could be extended too far... like the case of all the porn pop-ups... but, even there... I tend to feel that the user is ultimately in control (or should be!) of their own computer. Install Mozilla and don't suffer the pop-ups.

      Better yet... and this is the approach I myself practice... go away. Any time I find a site that ticks me off (bad Java/JavaScript that causes browser naughtiness), I add them to my banned list on my proxy... and never have to suffer the site again.

      Not even unintentionally.

      ---

      Not only that... but my CPU monitor went to a hundred percent.

      Yeah, it is a low priority thread... but... I did notice.

      P.S. "you" does not mean you personally...
      • Re:Uhh.. (Score:4, Insightful)

        by cmallinson (538852) * <c.mallinson@ca> on Wednesday December 31, 2003 @07:43PM (#7850008) Homepage
        I personally wouldn't call it "stealing". You pretty much agreed to run Java. Yes, you could be a clueless noob and knot *know* that your browser has it enabled... but, nobody is *making* you run java applets.

        I don't shove it down your pipe... you ask for it.

        OK, come on. Leaving Java enabled is a very poor definition of "asking for it". What percentage of internet users know the difference between Java and JavaScript, and can determine which one if any should be turned off or on? I would say less than 1-2%. Taking advantage of the rest is just not cool.

  • by Anonymous Coward on Wednesday December 31, 2003 @06:25PM (#7849474)
    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!
  • by GGardner (97375) on Wednesday December 31, 2003 @06:25PM (#7849478)
    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?
  • Or any other movie that makes heavy use of CG. While fans are visiting the fan site, they'll be helping to produce the sequel.

    Might be cheaper than render farms.
    • Have you ever tried even using a dedicated renderfarm? The complications that can arise if you don't have all the textures and files locally, not to mention the fact that rendering is so heavy a tax on the CPU people would NEVER want to do it. Plus, that would involve them releasing files that go into making the movie. And so on and so forth, The idea is so terrible I couldn't imagine anyone ever trying it. Peace out and try to talk about something you konw for once.
      • At 24 frames per second.

        No kidding; some of this stuff weighs in that heavily. This was before fibre channel too.

        Think Balrog scenes done with particle simulations... (it didn't last).

      • Holy crap what a nightmare. HELLO, PEOPLE, PUT YOUR TEXTURES ON THE SERVER!! Sorry, just a little rant. If I see one more 500 frame render with lovely black nothing mapped to the objects...I will hurt people. Seriously though, rendering does not lend itself very well to non-dedicated distibuted computing. The work units would be huge...but maybe some suckers would do it.

        Hmmm....Maybe if you wrote some sort of encrypted mental ray or renderman client, in that it does the render from encrypted source fi
    • No, it would take too long just to upload the scene data to the client, let alone render anything useful within the average person's attention span.
    • "Would be great for LOTR"

      What, distributed royalty payments to somebody that's been dead for over 30 years?
  • by herrvinny (698679) on Wednesday December 31, 2003 @06:28PM (#7849497)
    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.

    • 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.

      Right. Now you visit a web page and hope it doesn't fsck up your web browser. Fun.
      • 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.
  • Hmmm. (Score:2, Funny)

    by valkraider (611225)
    Imagine a Beowolf cluster of these things... It would be the same as if Slashdot put the applet in the header or something - all of us geeks computing stuff for free... That would be a lot of computing, I think a couple people visit slashdot daily!
  • Whoever made this... (Score:3, Interesting)

    by coene (554338) on Wednesday December 31, 2003 @06:30PM (#7849514)
    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 ;)
  • by Anonymous Coward on Wednesday December 31, 2003 @06:31PM (#7849521)
    First thing it does when the applet loaded was to bitch at me for not accepting cookies. Just like my wife.
  • Not ethical (Score:3, Insightful)

    by Bill_Royle (639563) on Wednesday December 31, 2003 @06:32PM (#7849529)
    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.

    Be upfront with people - tell them why it's so important, what can be accomplished with it, and what it does. You'd be surprised - people might help out of *gasp* the goodness of their own hearts. A good example might be SETI, etc.
    • Re:Not ethical (Score:5, Interesting)

      by pla (258480) on Wednesday December 31, 2003 @06:56PM (#7849702) Journal
      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.
    • Re:Not ethical (Score:5, Insightful)

      by Phillup (317168) on Wednesday December 31, 2003 @07:03PM (#7849755)
      While I completely agree with your sentiment about being upfront... I don't agree with calling it "stealing".

      Who clicked on the link?

      Who has Java enabled on their browser?

      Who has cookies enabled on their browser?

      It isn't like he is doing anything "tricky" or using some "bug" to pull this off. The page doesn't "trap" you. It doesn't eat your CPU and make it impossible to quit the app or go to another page. And, for me, it didn't crash anything.

      I *really* don't understand how this can even remotely be considered stealing. Every single item is being used *as*designed* both by the web author and you.

      The way I see it... someone jumped in a pool... and now they are bitching about your clothes being wet?
    • Good point; if we wanted to break the key to somebody's crypted code, we just put up a web bug on a pr0n site and wait for their cpu's to come to us.

      5096 bit keys, here I come.
  • Not very intensive. (Score:4, Informative)

    by LoneIguana (681297) on Wednesday December 31, 2003 @06:33PM (#7849538)
    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
  • by bluelip (123578) on Wednesday December 31, 2003 @06:33PM (#7849539) Homepage Journal
    put the snippet on slashdot.org. The collisions should all be found within an hour.
  • by cybermancer (99420) on Wednesday December 31, 2003 @06:35PM (#7849558) Homepage
    Interesting idea, but most distributed computing tasks that run in the background run at low priority. Since this is running inside your browser (more or less) it will run at the priority of the browser. Unless your browser is running at low priority then this process will push all the lower priority processes out of process cycles.

    This could prevent contact with ET!
  • by Peeet (730301) on Wednesday December 31, 2003 @06:35PM (#7849563)
    It's about time that the monster (us) is used for good and not evil.

    Oooh! I thought of another way...
    Just Click here. [sco.com]

    -P
  • I nearly got suspended from school because I installed seti@home on all the machines. With this, I can still maintain my EVIL distributed computing campaign, and do it without them knowing!
  • Is this applet crashing anyone else's browser?
  • by Vaevictis666 (680137) on Wednesday December 31, 2003 @06:46PM (#7849635)
    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.
  • by LostCluster (625375) * on Wednesday December 31, 2003 @06:46PM (#7849639)
    Let's put the research effort asside here and thing about the underlying concept here... basically, this is a distributed computing app being buried within webpages. Could commercial interests use this concept to get access to computing resources from their web users without telling them?
  • by Anonymous Coward on Wednesday December 31, 2003 @06:49PM (#7849654)
    1. Create very small website with CPU draining applet and post a link to said website to Slashdot.
    2. ??
    3. Profit!
  • by bigberk (547360) <bigberk@users.pc9.org> on Wednesday December 31, 2003 @06:51PM (#7849674)
    I believe the term was parasitic computing. Ideally the web master makes visitors aware to what's going on. You're using visitors' computing power to accomplish a neat sort of distributed computing. Great idea, if you're not just stealing resources
    • Combine this with the CPU cycles needed to send SPAM messages under MSFTs new hashing system, link it to a popular site and all the email tax in the world ain't gonna stop the UBE.
  • no thanks (Score:4, Interesting)

    by mercuryresearch (680293) on Wednesday December 31, 2003 @06:52PM (#7849680) Journal
    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.
  • cross domain cookies get rejected by lots of people, and is going to be the default behavior under xp sp2 and 2k3. I'll accept a cookie from the site I am trying to use, but 3rd party folks better stand down, either provide a service for that info or some money, its what everyone wants from me these days. $$$'s for a long distance land line service I have never used but can't avoid, number portability for a cell # that I don't publish and never plan on taking anywhere with me...surcharges for handling and p
  • by IBitOBear (410965) on Wednesday December 31, 2003 @07:13PM (#7849820) Homepage Journal
    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.
  • by phr1 (211689) on Wednesday December 31, 2003 @07:14PM (#7849833)
    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!
  • 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.
    • The source code isn't provided, unfortunately. But I am a Java guy, and the Java language does include encryption functionality. However, after reading the entire Usenet thread [gogole.com], he makes note that bandwidth is an issue, and even says he might host it on SourceForge because it has MySQL capability. Since he wants to conserve bandwidth, and most probably CPU time (reserve all he can for the calculations), my guess is he didn't use encryption, and just compresses and does something else funky with the stream b
  • I like the idea, but (Score:3, Interesting)

    by tulare (244053) on Wednesday December 31, 2003 @07:21PM (#7849872) Journal
    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
  • by digitalgimpus (468277) on Wednesday December 31, 2003 @07:25PM (#7849893) Homepage
    Not that I mind technology, and new tricks.

    But the last thing I want to see is every website hogging my CPU. Either selling computing power of their web visitors for profit, or using it for themselves.

    Imagine the next series of Spyware Trojans... rather than spy, they harness your CPU and sell the power. All without the knowlege of the computer owner.

    Interesting business model, but not something I want to see. I like my CPU. Note the word "my".
    • Imagine the next series of Spyware Trojans... rather than spy, they harness your CPU and sell the power. All without the knowlege of the computer owner.

      But then some enviromentalist finds that the progams kills a few birds and is shutdown.

  • I'd like to see the next poll: Did you click on the link to run unknown code recently posted on Slashdot? * Yes, I'm a moron * Yes, but I audited it first * Yes, but I did it from enemy's computer * Yes, and I did it proudly from work, who knows how many security policies I broke, and who cares. * I click on EVERYTHING! * Nope
  • is a good thing.
  • by ledbetter (179623) on Wednesday December 31, 2003 @07:44PM (#7850016) Homepage
    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.

  • by Crypto Gnome (651401) on Wednesday December 31, 2003 @08:11PM (#7850210) Homepage Journal
    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+
  • by waferhead (557795) <waferhead@@@yahoo...com> on Wednesday December 31, 2003 @08:44PM (#7850379)
    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.
  • by Dausha (546002) on Wednesday December 31, 2003 @10:19PM (#7850780) Homepage
    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.
    • by Glorat (414139)
      My standard reply to this is that there are 2^128 possible hash sums which is many magnitudes more than the number of electrons in the universe! So you'd have a pretty hard time storing them all.

      As for the set of short strings, because this is such a limited set, if MD5 is any good (which it is), you won't find a collision in such a small subset.

Every successful person has had failures but repeated failure is no guarantee of eventual success.

Working...