Slashdot Mirror
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."
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).
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?
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."