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

19 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 lorenlal · · Score: 2, Interesting

      Achieved new skill Digital Signing (apprentice)!

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

    3. 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: 2, Informative

      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. Attacker chose two different prefixes of the same length. They can be anything, they don't even have to be the same file format. Then use the collision attack to produce some random data to append to the two prefixes about 128-192 bytes are appended to each file. After this the attacker can append anything he wants to both files, but this part has to be the same on both files. The two files will have the same md5 hash. The attack can also be used with a set of more than two files. You have a bunch of prefixes, you then use the attack on the smallest two of them, at which point those two files will be colliding, so you group them together and for the rest of the attack consider them as one. They grew a bit longer, so when you then go ahead and choose the two smallest files again, that could be two different files. Repeat the attack over and over again until there is only one group with all the files. If you started out with prefixes of identical length, you would be pairing the files in a binary tree structure and append a number of bytes that was logarithmic in the number of files.

      --

      Do you care about the security of your wireless mouse?
    5. 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:posible whit nvidia too by Pinky's+Brain · · Score: 2, Interesting

    Yep, there are both collision checkers and crackers for CUDA too ... ATI is significantly faster though (this kind of computation bound stuff is ideal for them).

  6. Re:Basic English skills? by eclectro · · Score: 2, Funny

    consume 5 times less power, and be 10 times cheaper

    Actually I'm more concerned about the rise of the eco-cracker. The "green cracker" who wants to have a low carbon footprint and crack into your bank account inexpensively.

    --
    Take the cheese to sickbay, the doctor should see it as soon as possible - B'Elanna Torres, "Learning Curve"
  7. Re:Not again by Jarjarthejedi · · Score: 2, Interesting

    It's not an error. Times Less = 1/x times as much in language, and has done so for 3 centuries

    "Jonathan Swift, for instance, used it in 1711, writing "I am resolved to drink ten times less than before." It wasn't till the 20th century that language commentators - not mathematicians - came up with the notion that "three times closer" and "100 times slower" were illogical and confusing."

    from http://www.boston.com/news/globe/ideas/articles/2007/10/21/do_the_math/

    Just because it sounds like it can be misinterpreted doesn't mean it's wrong. "5 times less" in english is the same as 1/5 in mathematics.

    --
    There are two kinds of fool One says 'This is old therefore good' Another says 'This is new therefore better'- Dean Ing
  8. 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).

  9. 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?
  10. Todays new: CPUs processes data! by myforwik · · Score: 2, Funny

    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.

  11. Re:1.6 1.9 by Savior_on_a_Stick · · Score: 2, Informative

    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.

    No. He didn't say that.
    The performance difference was the cluster of 12 pc's with 24 cards, to the cluster of 215 PS3's

    So, how are the numbers supposed to be interpreted?

    Why are you interpreting them? They seem pretty clear as written.

    I don't understand why anybody still finds it newsworthy when somebody come up with faster collision attacks against MD5.

    It was newsworthy in January when it was first presented to the CA's.
    It's newsworthy now because it's a significant per processor performance increase.
    If you had read the article and not interjected your flawed interpretation, that would be obvious.

    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.

    It's newsworthy due to the application to certain mathematical processes.
    No one said this was "zomg - the internet is falling."