SHA-1 Cracking On A Budget 92
cloude-pottier writes "An enterprising individual went on eBay and found boards with more than half a dozen Virtex II Pro FPGAs, nursed them back to life and build a SHA-1 cracker with two of the boards. This is an excellent example of recycling, as these were originally a part of a Thompson Grass Valley HDTV broadcast system. As a part of the project, the creator wrote tools designed to graph the relationships between components. He also used JTAG to make reverse engineering the organization of the FPGAs on the board more apparent. More details can be seen on the actual project page."
For the uninitiated... (Score:5, Informative)
This makes them fairly pointless for general computing, but when you need to crunch a bunch of numbers in the same way over and over, they can REALLY outperform a general cpu. Usually these are used to manipulate audio / video data streams in real time (the original purpose for the FPGAs used in this project) - but recently people have started using them to brute-force try to crack an encryption scheme. Where a general purpose cpu might take upwards of 40 clock cycles to check one possible answer, each of the FPGAs in this system can check at least one answer PER clock cycle.
This guy pulled a bunch of FPGA systems out of some (defective?) HDTV video processing systems - reverse engineered exactly how everything was wired together, reprogrammed the FPGAs to do SHA-1 hash cracking rather than HDTV video processing, and added some usb control circuitry so the system could take commands from / return results to a pc.
One could use this same board setup to do any sort of massively parallel data processing, but right now the system isn't wired up to really feed large amounts of data into / out of the system in real time. He can get away with that as hash cracking results are fairly small and infrequent, so the limited means he has for getting "answers" out of the system isn't too much of a problem.
Posted at 4:39AM on Sep 1st 2007 by smilr
Re:Benchmarks? (Score:5, Informative)
So it doesn't search all possible inputs to SHA-1, but maybe you could use it in this situation: Given hash and salt, you can find password by a brute force search on this hardware (assuming password is less than 9 characters in length). This could be useful for obtaining user passwords from
How fast is that? (Score:3, Informative)
Anybody, have an idea how fast that is compared to modern a CPU?
IIRC, the last time I did anything like this it took my 2200+ AMD about 24 hours to do a 6-character keyspace (from 64-character set) - with MD5.
SHA-cracker? (Score:5, Informative)
It seems from here [unaligned.org] that it searches a 64 ^ 8 = (2 ^ 6) ^ 8 = 2 ^ 48 keyspace in 24 hours. No small feat, it should therefore do about 3,257,812,230 hashes in a second. It does 800 concurrently, which makes for 4 million a second per SHA-1 unit. Ouch, that's really fast.
Note that this could be done with any hash or symmetric algorithm, as long as it can be implemented on FPGA. So the moral of the story: use very long password (or even better, pass phrases), or make sure that they won't be able to acquire the hash.
Re:How fast is that? (Score:3, Informative)
I've wondered about Cell performance myself for a while, but I haven't got the time to go out of the way to do some measurements. For SSE3/4: I would call it highly unlikely that we would see anything like the performance they are posting: 2 ^ 12 performance difference for MD5 alone is quite a lot. Maybe SSE5 might speedup SHA-2 as well. Anyway, you might want to add the T2 (Rock processor) from Sun to that list, it has 8 crypto hardware accelerators on board. My 1.2 GHz C7 with hardware accelerator is probably way to slow to get anything near the performance, but I'll test it anyway. MD5 is much faster than SHA-1, which in turn is much faster than SHA-2, so you would want to use SHA-2 anyway, as a stop-gap measure.
Re:SHA-cracker? (Score:2, Informative)
Re:SHA-cracker? (Score:3, Informative)
As said, the hash algorithm itself does not matter too much. The problem with all these schemes is that the amount of entropy in the passwords is simply too small. Creating an SSL channel before authentication and sending a (hashed?) password would do for mail services I suppose. That way there is no way to do the off-line cracking; they'll have to attack the server directly.
It's mainly logic, not analogue parts (Score:5, Informative)
An FPGA really is conceptually very simple, and they're not hard to "program" either... Contrived example:
Verilog design to add/subtract 2 numbers (you'd never do this, but...)
Compare that to a K&R "C" routine to do the same thing...
In both cases, of course, you'd just use the 'if...else...' part, but I wanted to show more language structure...
:-), you don't get world-beating overnight, but it's relatively easy to get the 80% solution, and that might be just fine. Eking out the last 20% is where it gets hard, as you have to understand the internal structure of the LUTs, and how they interact with the carry-chain, what the LUT->LUT delay can be useful for etc. None of this is at all relevant unless you're missing your timing on a critical circuit (eg: you need 133MHz so your DDR2 SDRAM can work, but the synthesis tools (equivalent to a compiler) only deliver 125 MHz for your design).
The key thing to remember is that in C, all things happen serially, unless you arrange otherwise with threading libraries. In Verilog, any block beginning with 'always @' happens in parallel with every other 'always @' block. Once you've mentally-mapped the concept of vast numbers of threads to the way hardware works, any competent multi-threaded programmer can become a competent hardware engineer.
Of course, there's "guru stuff" in there as well (as much as you want, trust me
The 'always@' part is the hint of just where the power lies. *Everything* can happen in parallel, so you can build pipelines (like CPU's are pipelined today) into your logic, thus reducing the time taken per step (while taking multiple steps), thus increasing your clock rate. The benefit of course is that although the *first* result comes out in the same time, every clock thereafter, you'll also get a result.
I wrote a JPEG decoder a couple of years or so ago, running at ~130MHz. That doesn't sound much, but that comes to ~65 MPixels/second because of the pipelining. Looking at the SSE-optimised intel libraries, a CMYK422->CMYK baseline decode (which is what the FPGA was doing) takes 371 clocks/pixel. The intel chip I was comparing to was a 3.6GHz P4, meaning it could do ~9.7 Mpixels/second. For motion-jpeg that's the difference between decoding SD frames (for the P4) and decoding HD frames (for the FPGA)...
So, FPGAs tend to run slowly (relative to today's CPUs) but can exploit parallelism in ways CPUs just can't, but of course for serial processing, you can't beat a tradition
Re:Benchmarks? (Score:3, Informative)
http://www.bash.org/?701504 [bash.org]