Slashdot Mirror

← Back to Stories (view on slashdot.org)

Generating Fast MD5 Collisions With ATI Video Cards

Posted by timothy on 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."

12 of 72 comments (clear)

  1. Re:first by Yvan256 · · Score: 4, Funny

    Generated with the help of an ATI card, I assume.

  2. Easier Way by Hal+The+Computer · · Score: 4, Insightful

    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.

    --

    int main(void){int x=01232;while(malloc(x));return x;}
    1. Re:Easier Way by Anonymous Coward · · Score: 5, Interesting

      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.

    2. Re:Easier Way by kestasjk · · Score: 4, Funny

      CAs are incorruptible, we all know this.

      --
      // MD_Update(&m,buf,j);
  3. Sensible collissions that don't affect size? by Animaether · · Score: 4, Interesting

    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?

    1. Re:Sensible collissions that don't affect size? by Brian+Gordon · · Score: 4, Insightful

      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.

    2. Re:Sensible collissions that don't affect size? by Anonymous Coward · · Score: 5, Insightful

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

    3. Re:Sensible collissions that don't affect size? by bhima · · Score: 4, Insightful

      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.

      --
      Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.
    4. Re:Sensible collissions that don't affect size? by kasperd · · Score: 3, Insightful

      So I suppose it is time to work out a migration plan for whatever uses MD5

      The first collision was demonstrated about five years ago. Anything that relied on collision resistance, should have been migrated away from MD5 at least four years ago. The attack in 2004 just wasn't taken serious enough.

      --

      Do you care about the security of your wireless mouse?
  4. Re:1.6 1.9 by kundziad · · Score: 3, Insightful

    or 2.2 billion MD5 hash/sec with reversing

    Keep in mind I have completely no idea what "reversing" means.

  5. Re:So Who Said That ATI Cards Aren't Programmable? by Pinky's+Brain · · Score: 5, Informative

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

  6. Re:1.6 1.9 by kasperd · · Score: 3, Insightful

    The numbers don't add up no matter how I turn them. He claims to be getting 14% more performance from each graphics card than from each PS3. That means he need 12 machines with 24 graphics cards each to match the speed of a 215 node PS3 cluster. So because he get 14% more performance per node, he only need 34% more nodes to achieve the same performance. That does just not make sense to me. The 24 graphics cards in each machine also sounds unlikely. Maybe it was 24 in total, so 2 per machine. In that case 14% more performance per node means he need 89% fewer nodes. That does not make sense either. So, how are the numbers supposed to be interpreted?

    I don't understand why anybody still finds it newsworthy when somebody come up with faster collision attacks against MD5. We already know, that collisions can be generated for MD5, and they can be generated fast enough, that we have to worry about it. It no longer matters exactly how fast they can be generated. If somebody managed to come up with a practical second preimage attack against MD5, then it would be newsworthy.

    --

    Do you care about the security of your wireless mouse?