Slashdot Mirror
SHA-1 Cracking On A Budget
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."
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 HTH.
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
>north
You're an immobile computer, remember?
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.
TC - My Photos..
That's nice, his own SHA-1 cracker. But, even with advanced cryptographic attacks, SHA-1 is still in the order of 2^63. Not something you would like to try with just a few FPGA's. What is meant here is a cracker to find out which plain text, with limited entropy, is used to create a certain hash value. A SHA-1-based password cracker would therefore be a better name, I suppose.
It seems from here 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.
But I have no idea what that summary or TFA are about.
For the record the company is Thomson and that is a peice of equipment known as the Princeton Engine used by the IC developers to quickly verify their software/algorythms. It was lying around in our computer room (known as the Princeton Engine room) for years. Its replacement is from Cadence and is called Palladium and has the power of several hundred of those old fpga boards.
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
Physicists get Hadrons!
http://www.bash.org/?701504
hmm... you seem to know a lot about FPGAs, so I'll ask you something I've been wondering for a while...
Coming from a traditional software end of things, I'm used to seeing "accelerating co-processors" available to do useful tasks much faster than the main CPU. I'm thinking not only the FPU (when it was a separate chip), but things like a modern GPU and such. Many of these have been slowly integrated back into the CPU as time has gone on, the FPU being the best example, so now it's something you can just call on with a special instruction.
From my understanding, FPGAs are mainly all generic logic blocks, arranged in fancy ways, and therefor are rather "generic" like the general CPU - you have to implement any fancy processing yourself.
My question is has anybody thought about putting fancy co-processing hardware local to the FPGA? I'm thinking some built-in FFT units and such that you could just include anywhere in your pipeline would be really useful, and might help that "timing critical" areas by having some common "higher level" functions computed in full hardware (ASIC?) speed.
Like, as a programmer, it sounds like it'd be cool to be able to buy an FPGA with built-in FFT, CRC/MD5/etc, maybe part of some encryption routines, etc to work with as common things that need to be accelerated.
Is this sane? Does it already exist and I just don't know about it? Is it totally incompatible with how FPGAs work?
Ce n'est pas une signature automatique.