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

Comments

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