Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Encryption Security Graphics Software Technology

Generating Fast MD5 Collisions With ATI Video Cards 72

Posted by timothy from the how-to-get-grants-for-game-hardware dept.
An anonymous reader writes "Yesterday at Black Hat USA 2009, a talk entitled MD5 Chosen-Prefix Collisions on GPUs (whitepaper) (Both PDFs) presented an implementation written in assembly language for ATI video cards that achieves 1.6 billion MD5 hash/sec, or 2.2 billion MD5 hash/sec with reversing, on an ATI Radeon HD 4850 X2. This is faster than the much-publicized 1.4-1.9 billion hash/sec figure that was supposedly reached on a PlayStation 3 by Nick Breese at Black Hat Europe 2008 (he later noticed an error in his benchmarking tool). Compared to the cluster of 215 PlayStation 3s that was used to create a rogue CA in December 2008, Marc Bevand claimed a cluster of 12 machines with 24 video cards would be a bit faster, consume 5 times less power, and be 10 times cheaper."
This discussion has been archived. No new comments can be posted.

Generating Fast MD5 Collisions With ATI Video Cards More

Generating Fast MD5 Collisions With ATI Video Cards

Comments Filter:

  • Easier Way (Score:5, Insightful)

    by Hal The Computer ( 674045 ) on Saturday August 01, 2009 @03:56PM (#28911301)

    If all you want is a signed SSL certificate, I suspect it would be easier to bribe an employee at a CA to skip a few steps when validating you.

    • Hey, if that's all you want, I'll give you a signed certificate, and my mother will recognize the signature too. No bribe required, but tips will be graciously accepted, of course.

    • Re:Easier Way (Score:5, Interesting)

      by Anonymous Coward on Saturday August 01, 2009 @04:14PM (#28911439)

      It would be harder than you seem to think. It's not just any old fake cert they created. They created a CA certificate. That is, a certificate that can be used to issue other certificates. You can issue any many of these "other" certificates as you want and they will look legitimate.

      It's very rare for a real CA to issue a certificate like that. That is the "top of the food chain" in certificates so to speak. You would have to bribe a fairly high level employee to get something like that. They keep those high level keys very well protected and there are only a few people that even have access to them.

      • Re: (Score:2)

        by Feyr ( 449684 )

        yeah

        if by high level you mean just about any of their sysadmin with access to the website? getting access to the actual key is unneccessary. you only need to be able to get something signed without them checking for some fields (ie, existence of CN, or capabilities bits..)

        sure you might not be able to bribe verisign (though i doubt that) but in this case you only need to bribe one sysadmin from one of the big-name CA (any which has a certificate in your browser will do)

      • Re: (Score:2)

        by kju ( 327 ) *

        Totally bullshit. For signing another CA the CA can (and will) use the same key as they use to sign "ordinary" certificates. After all the difference between a CA and a non-CA certificate is just a flag in the X509v3 extensions in the cert. There is no special "high level key" which is only used for signing a CA certificate. Any key/certificate which build a certificate chain up to a root cert will do.

    • Re:Easier Way (Score:5, Funny)

      by kestasjk ( 933987 ) * on Saturday August 01, 2009 @04:50PM (#28911681) Homepage
      CAs are incorruptible, we all know this.

  • Sensible collissions that don't affect size? (Score:5, Interesting)

    by Animaether ( 411575 ) on Saturday August 01, 2009 @03:59PM (#28911321) Journal

    Somewhat off-topic, but I guess related all the same...

    Nobody should use MD5 for authentication and whatnot... and even as a 'checksum' of sorts you have to be careful (i.e. make sure that the source of the MD5 text/file isn't the very same source as the file it was generated for, as a compromised file probably means the MD5 string would be equally compromised).

    But I'm curious.. are any of the attacks capable of injecting new data that..
    1. doesn't affect filesize - the wiki mentions that successful attacks can prepend and append, but presuming you'd include the file size with the MD5 string, that would be another parameter to check
    2. actually does something.. be it useful or nefarious, rather than just crash the app or insert gibberish in a text document, etc.

    e.g. if I took the declaration of independence as a .txt file, are there any attacks that could subtly, or non-subtly, change the wording without increasing or decreasing the size of the file, and still match an original MD5?

    --

    On-topic: cool; but not particularly new? Most everybody knows that GPUs are great at taking in a tiny bit of data, crunching it, and spitting a result back out. Kudos for actually writing optimized code for the given platform (in this case an AMD/ATi GPU), but it's still the same number crunching instead of an improved method.. correct?

    • Presumably (and I'm making a lot of assumptions here, I don't know enough about the subject), you could just snip the file by however many bytes the process would append to it, so when it does all of the calculations and appends it, it ends up the same size.
      Also presumably, it would mean the last few bytes of the text file would be utter garbage.

    • Re:Sensible collissions that don't affect size? (Score:5, Insightful)

      by Brian Gordon ( 987471 ) on Saturday August 01, 2009 @04:09PM (#28911405)

      actually does something.. be it useful or nefarious, rather than just crash the app or insert gibberish in a text document, etc.

      The point of the attack is that you can change the file to whatever you want, prefix some ignored garbage, and end up with a file with the same md5. So yes you could do something useful or nefarious by changing the file usefully or nefariously.

      • Re: (Score:2, Informative)

        by kasperd ( 592156 )

        The point of the attack is that you can change the file to whatever you want, prefix some ignored garbage, and end up with a file with the same md5.

        What you are describing is a second preimage attack. Nobody have achieved that against md5. What has been achieved so far has only been collision attacks. The first collision attack against md5 was demonstrated in 2004. Later some better collision attacks were demonstrated, in which you can choose the prefixes. The chosen prefix attack works in the following way

    • Re:Sensible collissions that don't affect size? (Score:5, Insightful)

      by Anonymous Coward on Saturday August 01, 2009 @04:19PM (#28911471)

      The attack that is mentioned in the story, the creation of the rogue CA certificate, is an example of a successful MD5 collision attack with a practical application. The "random" garbage was inserted in a part of the certificate signing request which is opaque to the certificate authority. That was also an example of a useful collision attack, so these are actually dangerous (not just pre-image attacks).

    • Nobody should use MD5 for authentication and whatnot...

      Signing a hash is a very common method in cryptography. DSA for example signs with SHA-1 (SHA-2 these days), if you sign the unhashed message it isn't DSA.

    • I don't think folks have to avoid MD5 as strongly & immediately as you suggest... the attacks are for the most part theoretical or require more compute power / patience that people outside of this blackhat con can muster. It was my understanding the PS3 cluster actually got a cert which could be used nefariously... and this guy showed he could do it cheaper and faster. This is perfectly inline with my understanding: Attacks always get better, they never get worse. So I suppose it is time to work out a migration plan for whatever uses MD5

      On your closing comment: I think the author was suggesting that if people had been paying attention a lot more of them would be using ATI GPGPU clusters for stuff they used to use Vector processors and now use fleets of X86 variants for.

      I don't completely disagree with him but there a lot of small GPU clusters out there and there are a lot of reasons why more people haven't really got with the program. I think the biggest reason is the difficulty developing for GPGPUs. It's not the hardest thing I've ever done but it really takes a deliberate effort to get into a different state of mind. And the ATI SDK just plain sucks. I'll take the performance hit and develop using a C superset with a NVIDIA target. The process can run during that extra time I am not pounding my head against a hard flat surface. Actually now that I think of it, I've just kept a lot the old FORTRAN code I have and used the NVIDIA kit... rather than porting to the ATI SDK.

      Having said that I don't think that this state will last long at all. The rate of increase of performance in GPUs is steeper than that of CPUs; AMD & NVIDIA are really serious about getting into the general compute market (with the same or similar chips to what they already market); The power consumption, cooling, and noise are all really favorable.

      I am sort of curious what OpenCL will be like, being a Mac user... but here lately Apple has been going further out of their way to make things suck, so I am not holding my breath.

    • Re: (Score:2)

      by llamalad ( 12917 )

      I did some custom file 'fingerprinting' work some time ago when management didn't want to spring for Tripwire. For each file, the system stored both the md5sum and an shasum in addition to the file size. Figured that it was sufficiently improbable that a single altered file could collide in both hashing functions, particularly without changing in file size.

      Granted, a rootkit could probably mess with return values to make it look as though the file hadn't changed at all, but at that point monitoring binaries

    • Nobody should use MD5 for authentication and whatnot... and even as a 'checksum' of sorts you have to be careful (i.e. make sure that the source of the MD5 text/file isn't the very same source as the file it was generated for, as a compromised file probably means the MD5 string would be equally compromised).

      If you're using MD5 as a way to verify that the file isn't festooned with viruses. I don't think that was the intention of MD5 from the beginning, though, as it's a pretty useless way of going about it..

      • Re: (Score:2)

        by tepples ( 727027 )

        If you want to ensure that it's got no viruses or malicious code in it, then invest in a proper antivirus, keep it up to date, and scan everything you download.

        Newly released viruses don't appear in antivirus programs' signature lists.

    • if I took the declaration of independence as a .txt file, are there any attacks that could subtly, or non-subtly, change the wording without increasing or decreasing the size of the file

      Just add politicians and wait...
  • There supposed to be faster, right ?

  • ...consume 5 times less power, and be 10 times cheaper

    *sigh*

    • Clearly nuclear powered with an overall electrical output enough to supply four other units.
  • In one machine? Really?
  • So who has been saying all along that GPU compute on ATI cards just isn't up to snuff? I doubt that they picked out an ATI video card to use because it was too difficult, or the programming tools too immature, or the programming interface documentation too incomplete or secret, to provide an effective demonstration? I would expect rather the opposite to be true and that GPU compute on ATI cards already works well and will only get better over time.

    • Re:So Who Said That ATI Cards Aren't Programmable? (Score:5, Informative)

      by Pinky's Brain ( 1158667 ) on Saturday August 01, 2009 @06:16PM (#28912261)

      ATI cards are programmable, Brook+ is just a little too high level for writing simple computational kernels (you drop too much performance) and CAL too low level for most people (it's basically assembly). So generally people just stick to CUDA, even in the few cases where ATI's architecture is superior.

      This problem is ideal for ATI, very little input necessary (NVIDIA has more texture samplers) and no inter thread communication necessary (ATI does not have random writes on it's local data share at the moment, making that communication harder than it is with NVIDIA). So basically it just comes down to FLOPS and ATI wins big there.

      Basically this was done in CAL because it was done by a hacker and not by an academic researcher (who doesn't really care about performance if he can just as easily get his paper published on a slower GPU with less effort, easier in fact since editors know CUDA).

    • So who has been saying all along that GPU compute on ATI cards just isn't up to snuff?

      Mainly people who haven't been paying attention to what ATI has been doing since AMD bought it and began merging tech ~3 years ago, along with the usual business/management changes that go with that kind of consolidation. Basically today's ATI isn't the ATI of just a few years ago.

      To be fair to those folks, the Radeon HD 4800 series is, roughly speaking, less than 2 years old, with the 4850 X2 being only ~1 year old. Before the HD 4800 series came out (based on the RV770 [wikipedia.org]), which was the *second* generatio

  • It would be very interesting to see if this class of algorithm ports easily to OpenCL - the GPGPU technology built into the upcoming 10.6 version of Mac OS X:
    http://www.apple.com/macosx/technology/#opencl [apple.com]

    If so, this kind of attack suddenly becomes very easy to gather the compute power for and a lot easier to code as you don't need to do the low-level stuff yourself.

  • Why is this news? This is worse than distributed.net brute forcing 56bit keys. Yes MD5 is crap, we don't need an example of everytime someone hooks up some new processors to break it.

  • Huh, so that's who bought all those PS3s.

  • Back when CPUs didn't include an FPU (aka mathematical co-processor) by default, there used to be different choices by different chipmakers.
    It'd be interesting to have a modern days mathematical monster installed in every PC for a number of different tasks, from 3D rendering to ... ehm ... secury experiments :-)

Slashdot Top Deals

E = MC ** 2 +- 3db

Close