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

For the uninitiated...

[MollyB (162595)]

If this story is hard to understand (was for me), then a comment following TFA might be useful, if you don't/didn't read that far:

5. FPGA - field programmable gate arrays are sort of like reconfigurable circuitry - they can be programmed to perform complex computations in one giant "step", rather than as a sequence of instructions (how a general purpose cpu like the pentium operates).

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.

Re:For the uninitiated...

[Poromenos1 (830658)]

How about if you write an FPGA simulator program and simulate an FPGA simulating a CPU running your program? Will the universe implode?

It's mainly logic, not analogue parts

[Space cowboy (13680)]

There are some FPGA's that can control their output impedance on pins, but an FPGA is really for digital electronics - you're using 4-way look-up tables to emulate arbitrary 4-input logic-gates for the most (99.99%) part. I've seen genetic-algorithms produce capacitance-based designs where unconnected circuits affect each other due to analogue effects, but not humans. We tend to stick to the straight and narrow...

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

module addsub (a, b, addnsub, result);
input [7:0] a;
input [7:0] b;
input addnsub;
output [8:0] result;
reg [8:0] result;

always @(a or b or addnsub)
begin
if (addnsub)
result = a + b;
else
result = a - b;
end
endmodule

Compare that to a K&R "C" routine to do the same thing...

void addsub(a, b, addnsub, result)
short a;
short b;
unsigned char addnsub;
short *result;

{
if (addnsub)
*result = a + b;
else
*result = a - b;
}

In both cases, of course, you'd just use the 'if...else...' part, but I wanted to show more language structure...

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 :-), 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 '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

FPGA question...

[Endymion (12816)]

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 cal

Re:

[Radicode (898701)]

There are many libraries you can put on your FPGA. Some are open source, some costs A LOT. It's similar to a dll or a jar: you have an interface you bind to and you program your stuff around it. You can get modules to process FFTs, encryption, ethernet, VGA, sound, video, pretty much anything you can imagine. You can even use a CPU library to have a gereal cpu like your x86 and execute assembler instructions. You can even turn an FPGA into an old defunct cpu to repair an old electronic hardware. Amazing stu

Re:FPGA question...

[Space cowboy (13680)]

Well, common FPGA's are basically look-up tables surrounded by a sea of interconnect logic. The designer specifies the function of each LUT, and the connections between them using a language such as Verilog or VHDL. They're not "generic logic", they're defineable logic. Example: On a CPU, you have the 'add x,y' instruction - that's a chunk of logic on-chip. On an FPGA, that chunk of logic doesn't exist until you write a design that needs it.

You can buy (though I think they're very expensive) "IP cores", which are pre-packaged modules ready to plug-in-and-go. There are some free ones available as well. You may have to do more work to get the free ones to work [grin].

There are also built-in hard cores on modern FPGA's. You never used to be able to synthesize the statement "a = b * c;" in a verilog design, for example. Now that FPGA's have hardware multiplier blocks in them, it synthesises to a bunch of wires connecting up the LUTs to the built-in hardware. For the more-complex examples you suggest, it's best to implement them in logic, because an FFT (of a particular radix, input format (complex or real), and output requirements) is a very specific piece of hardware, and not generally useful to most customers.

You get multipliers, blocks of fast dual-port RAM, even entire processors (PPC) embedded into the FPGA fabric these days. Of course, you pay more for things like embedded CPUs... Funnily enough, a CPU is one of the easier things to write for an FPGA IMHO. You'll never get the speed of the FPGA fabric to match the hard-CPU core though...

To do what you're talking about though, you'd need a way to interface the FPGA to the PC - there's a freely available PCI core, so you'd then just need a card which had a PCI interface (there's one from Enterpoint [enterpoint.co.uk] for ~$150... Then you just need to link the PCI core to your own cores (FFT, whatever) and write software to offload any FFT's to your co-processor. Xilinx offer the "Embedded Development Kit" to make this easier (you have to pay for this, the other tools are free to download). I don't know if anyone has made the freely-available PCI core into an EDK module though...

Simon.

Simon

How fast is that?

[tcdk (173945)]

NSA@home is a fast FPGA-based SHA-1 and MD5 bruteforce cracker. It is capable of searching the full 8-character keyspace (from a 64-character set) in about a day in the current configuration for 800 hashes concurrently.

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.

Re:

[owlstead (636356)]

"NSA@home is a fast FPGA-based SHA-1 and MD5 bruteforce cracker. It is capable of searching the full 8-character keyspace (from a 64-character set) in about a day in the current configuration for 800 hashes concurrently."

So your 2200+ AMD is beaten to little pieces by this monster.

Source, well, you had to click a single link to their homepage [unaligned.org]. That'll learn you to post early. Or not, since I supplied you the answer anyway.

Re:

[tcdk (173945)]

I actually quoted that myself...

I was wondering how it compared with the latest and greatest like x64 with SSE3/4 or a Cell processor...

(that'll learn you to actually read the post you are replying to. Or not)

Re:

[owlstead (636356)]

Arg! Whoops, sorry about that. Read the post, but thought you were quoting the summary.

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

Re:

[DaleGlass (1068434)]

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.

You should compare against VIA hardware. Their CPUs are crap for general usage, but the crypto acceleration is really good:
http://www.logix.cz/michal/devel/padlock/bench.xp [logix.cz]

Page doesn't seem to include MD5/SHA1 though, but you can compare that to AES on your box.

SHA-cracker?

[owlstead (636356)]

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

[MichaelSmith (789609)]

That's nice, his own SHA-1 cracker.

Its a bit like if you built your own cruise missile. Telling the whole world about it might not be the smartest thing to do.

Re:

[LarsG (31008)]

Telling the whole world about it might not be the smartest thing to do.

EFF [cryptome.org] seems to think it is the smartest thing to do.

Re:

[Rythie (972757)]

By comparison my Althon 64 3200+ does about 883,000 16byte hashes a second

$ openssl speed sha1
Doing sha1 for 3s on 16 size blocks: 2586683 sha1's in 2.93s
Doing sha1 for 3s on 64 size blocks: 2063294 sha1's in 2.90s
Doing sha1 for 3s on 256 size blocks: 1199179 sha1's in 2.75s
Doing sha1 for 3s on 1024 size blocks: 479901 sha1's in 2.84s
Doing sha1 for 3s on 8192 size blocks: 71496 sha1's in 2.87s
OpenSSL 0.9.8c 05 Sep 2006
built on: Tue Mar 6 08:16:57 UTC 2007
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cis

Re:

[archen (447353)]

Perhaps this gets brought up each time, but what are we supposed to use for password encryption anyway? MD5 seems to be inadequate. SHA-1 is also waning. I switched to Blowfish on all my FreeBSD servers partially because of MD5 problems, but also because it's not a common format to come across for anyone figuring they'd just have MD5 hashes to try - I understand however that blowfish was not intended for this purpose.

But it seems like MD5 and SHA are getting weaker by the day with computational power on t

Re:

[owlstead (636356)]

Don't forget that PKCS#5 v2.0 uses an iteration count and a salt. This means that the algorithm is not applied just once, but 1000 times (or more, 1000 is the minimum). This would mean a slowdown of 1000 on these kind of crackers *if* they implement the iteration count. A salt would make it hard to use a default configuration like this one found on internet as well.

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 i

Re:

[cancerward (103910)]

No-one has cracked Ken Thompson's UNIX password [google.com] yet, and he is a co-inventor of the algorithm...

Maybe I'm Not As Big A Nerd As I Thought...

[kaos07 (1113443)]

But I have no idea what that summary or TFA are about.

Re:Maybe I'm Not As Big A Nerd As I Thought...

[lindseyp (988332)]

What? You mean TFA didn't have the right TLA's or FLA's or maybe FPGA's are just not your COT and SHA-1 is no BFD to you but to URG it's a BFD.

what?

I recognise that pattern!

[6Yankee (597075)]

Cool diagram. [unaligned.org]

I used to draw patterns like that while suffering through triple Maths - draw a circle, mark off every 10 degrees (or 5 if it looked like being really boring today), then join every point to every other point. Mindless, yet strangely satisfying.

And what kind of nerd site doesn't let you use a degree symbol?

Re:Benchmarks?

[Cheesey (70139)]

Seems to me that it searches all possible 64-bit words that could be given to SHA-1. It cleverly reorders the search so that the Hamming distance of each block is at most 2 bits from the previous block, which allows Virtex block RAM resources to be used as part of the hash hardware. FPGA engineers often only use block RAMs for caches, FIFOs and scratchpads, so it is interesting to see them being used as part of the pipeline in this way despite the two-port limitation.

So it doesn't search all possible inputs to SHA-1, but maybe you could use it in this situation:

SHA-1(salt, password) = hash

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 /etc/shadow when something like md5crypt is in use, although md5crypt might well be designed to defeat/slow down this type of attack, for example by using multiple rounds of hashing (as done by the older DES-based crypt program).

Re:

[Tony Hoyle (11698)]

If you can read /etc/shadow you're root.. which means you aren't gaining anything by it.

In the old days when passwords were in /etc/passwd then it was a valid attack. Now much less so.

Re:Benchmarks?

[eli pabst (948845)]

If you can read /etc/shadow you're root.. which means you aren't gaining anything by it.

There are still arbitrary file disclosure vulnerabilities which *only* allow you to view files, not gain access to the server itself. If you pull the password hashes, you can then bruteforce the passwords and gain full root access to the system. Plus it would give you access to any *other* machines on the network which the admin used the same root password. Just rooting a single box wouldn't give you access to any other machines (assuming that didn't share the same initial vuln).

Re:

[BlueParrot (965239)]

You might be in the shadow group, and there might be a server application that is in said group in order to read /etc/shadow, so if you can exploit that service to gain access to the contents of the shadow file, you can then try to root the machine after cracking root's (or someone with sudo I guess) password.

http://www.bash.org/?701504 [bash.org]