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."
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?
Achieved new skill Digital Signing (apprentice)!
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.
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).
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