Generating Fast MD5 Collisions With ATI Video Cards

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

Easier Way

[Hal The Computer]

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.

Re:Sensible collissions that don't affect size?

[Brian Gordon]

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:1.6 1.9

[kundziad]

or 2.2 billion MD5 hash/sec with reversing

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

Re:Sensible collissions that don't affect size?

[Anonymous Coward]

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

Re:Sensible collissions that don't affect size?

[bhima]

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:Sensible collissions that don't affect size?

[kasperd]

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.

Re:1.6 1.9

[kasperd]

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.