Skip

Bruce Forcing
September 4, 2007 2:47 PM   Subscribe

NSA@home is a fast FPGA-based SHA-1 and MD5 bruteforce cracker. Based on HDTV equipment from eBay, "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." Previous well-publicized brute-force attacks include the EFF breaking DES in 56 hours and 1.6TB of md5 hashes you can search online.
posted by Skorgu (53 comments total) 12 users marked this as a favorite

 
Anyone care to sum this up for us non-acronym, non-techie folks?
posted by kuujjuarapik at 2:51 PM on September 4, 2007


What is that you are saying
posted by undule at 2:52 PM on September 4, 2007


Bruce Forcing? That just might be the best gay porn star name ever.
posted by billysumday at 2:55 PM on September 4, 2007 [7 favorites]


An FPGA is a processor chip with amnesia, it doesn't know what it is (or what it should do) until you tell it. This guy found that some obscure HDTV hardware had a bunch of (very expensive) FPGAs on them, and found one on eBay.

By some very clever hacking he was able to turn it into a device that can run through an insane number of hashes in a really short amount of time.

Hashes are used in a whole lot of places, namely for passwords. You don't want metafilter to know that your password is "lovrman", so mefi converts it into a hash (c108477996e50b43c2f736d29bd39dab) and stores that. You can go from lovrman to the hash, but given the hash you can't go backwards. This is a way of checking a huge number of possible "passwords" against a known hash in a really short time period.
posted by Skorgu at 2:57 PM on September 4, 2007


This is pretty cool... related (since Bruce invented it), does anyone know if blowfish has been cracked yet?
posted by synaesthetichaze at 2:59 PM on September 4, 2007


FPPBAR
posted by Poolio at 3:01 PM on September 4, 2007 [1 favorite]


Err, I botched that hash explanation a bit. You give metafilter (for example, I don't actually know how mefi stores passwords) your password. It gets the hash from that password and stores it, forgetting the password itself. When you want to log in, metafilter takes your password, hashes it, and compares the hashes. This way your password isn't stored anywhere (in case you used it for your bank, mathowie doesn't know it and can't use it to impersonate you somewhere else). This makes it more plausible to (potentially) reverse the one-way hash function and get "lovrman" from c108477996e50b43c2f736d29bd39dab, thus being able to impersonate you and transfer your monies to his offshore account in the caymans.
posted by Skorgu at 3:03 PM on September 4, 2007 [3 favorites]


"Anyone care to sum this up for us non-acronym, non-techie folks?"

It's time to change your paypal password to something much longer. (and change it often)
posted by TechnoLustLuddite at 3:03 PM on September 4, 2007


This is pretty cool... related (since Bruce invented it), does anyone know if blowfish has been cracked yet?

You don't mean "cracked" you mean "weakened" and the answer is no, nothing yet for the full-strength version.*

*64-bit keylength against large textblocks, yes, and for very small numbers of rounds (4 or less) as opposed to the full 16, also yes - both found almost immediately after publication
posted by Ryvar at 3:07 PM on September 4, 2007


Oh. Alright. Thanks!
posted by kuujjuarapik at 3:08 PM on September 4, 2007


Okay, how many people tried to logon as Skorgu just now?
posted by eriko at 3:11 PM on September 4, 2007 [2 favorites]


Bruce Forcing?

No, silly, Brute Schneier.
posted by eriko at 3:12 PM on September 4, 2007


Also, I'm not really sure this changes anything. Ever since DJB found that theoretical RSA weakness, responsible paranoids have been using at LEAST 4096-bit keys for anything of importance.
posted by Ryvar at 3:12 PM on September 4, 2007


so what they're saying is that the terrorists now have access to the info that the nsa swears it doesn't have on me?!
posted by shmegegge at 3:14 PM on September 4, 2007


Just try to crack this hash: #
posted by mrnutty at 3:17 PM on September 4, 2007


Bruce Forcing and Hash Longkey star in "The Rainbow Table." Only on Blu-Ray.
posted by damehex at 3:30 PM on September 4, 2007 [3 favorites]


Waitaminute, I thought BruteForce Cracker played defensive end on the Crimson Tide.
posted by FelliniBlank at 3:34 PM on September 4, 2007


I botched that hash explanation a bit.

Shorter/easier explanation: Ya' smoke it, you get the munchies, then youse eatz it. Hey, don't Bogart that joint, my friend.
posted by ericb at 3:43 PM on September 4, 2007


Wow, that hacked up FPGA-based system is amazing. Great post, thanks.
posted by signalnine at 3:45 PM on September 4, 2007


It gets the hash from that password and stores it, forgetting the password itself.

Actually, metafilter stores plaintext passwords.
posted by dmd at 3:48 PM on September 4, 2007


I'm gonna use this to hack the Gibson.
posted by quin at 3:50 PM on September 4, 2007 [4 favorites]


To clarify previous posts: an FPGA is more than a processor with amnesia. It's a configurable array of logic gates (field programmable, even!) that lets you accomplish logic operations in a fundamentally different way from a computer processor. Where a computer would use a few assembly instructions to calculate the XOR of two registers, an FPGA might have dedicated logic gates that spit out the answer much more quickly.

Because you can dedicate logic gates to accomplish specific tasks, you can often achieve a significantly higher throughput than you would using a conventional microprocessor.

Remember how, before PCs were fast enough to decode DVDs, there were hardware accelerator boards to help out? This is the same kind of thing.

</pedant>
posted by lalas at 3:55 PM on September 4, 2007


The nice thing about all of this is that if you brute force SHA-1/MD5 for a living, buying a bunch of FPGAs and hooking them together is suuuper cheap! Why bother with HDTV things when the actual custom hardware is well within the means of a small telco/local criminal syndicate/successful spam cartel/etc.? Easier than printing $20s, I'd say.
posted by tss at 4:00 PM on September 4, 2007


FPGA means 'Field Programmable Gate Array'; they're very expensive chips with malleable components. In essence, you program them, but you design a circuit instead of a software program.

An FPGA is never as fast as a custom IC: if you tried, for instance, to implement the x86 architecture in one, it would be much slower than a real x86 chip. But an FPGA can be tremendously faster than a software program, because a general-purpose microprocessor can't take any shortcuts when running a program. An FPGA can be optimized for exactly the problem at hand. In theory, they can even be reprogrammed on the fly to run different programs, but that's still mostly a research area.

By using the FPGAs he picked up for a song, the guy has a tool that's way faster at cracking passwords than even a whole farm of mainstream PCs would be. An application of serious brainpower, and poof! He turns junk into treasure.

At the rate password cracking is improving, we're gonna have to transition away from them almost completely within the next 10 or 20 years; you won't be able to memorize a password long enough to be secure for any length of time. They'll be cracking 20 character passwords before you can even memorize them.
posted by Malor at 4:05 PM on September 4, 2007


I always thought this was the silly part of those DES cracking challenges... PCs are pretty crummy at it, and FPGAs are really good. And a lot cheaper.
posted by smackfu at 4:06 PM on September 4, 2007


Hmm, after thinking about that a little more -- they'll just go to a tougher hashing algorithm.

It's good to think things through before hitting post. Honest. You'd think I'd do it more. :)
posted by Malor at 4:07 PM on September 4, 2007


Gee, I'm so thankful hackers are looking out for my safety and security by posting exactly how to crack security for the entire world to see and use.

Next up: thanking that homeless guy in the subway for continually pissing in the corner to demonstrate how anti-urination laws don't work
posted by Muddler at 4:09 PM on September 4, 2007


Muddler, you seem to think that what the hacker did is a Hard thing to do. It's hard, but it's not Hard. I mean, it's computationally hard in a takes-computers-a-long-time sense, but the well-funded parties have been doing this for ages.

What the subject of this post did is take the oldest and slowest method in the book, and throw some newfangled, really-bloody-fast, but also "defective", hardware at it. It also helped that he knew some basic electrical engineering. Banning this sort of thing wouldn't stop it from happening at all, but it would be monumentally stupid.
posted by TheNewWazoo at 4:18 PM on September 4, 2007


"Gee, I'm so thankful hackers are looking out for my safety and security by posting exactly how to crack security for the entire world to see and use."

Would you rather just a few evil haxors have the ability to crack your files, or for the knowledge to be out in the open, forcing everyone to be more careful and up the ante? (Realize, of course, that the cat and mouse game will never end- Moore's law be damnmed)
posted by TechnoLustLuddite at 4:25 PM on September 4, 2007


I'm barely understanding this, I think, but damn this thread is interesting.

FPGA means 'Field Programmable Gate Array'; they're very expensive chips with malleable components. In essence, you program them, but you design a circuit instead of a software program.

Malor, how and when is this done? Are these chips rewritable? Is it done on the fly? The Wikipedia article kind of lost me. I'm just kind of blown away by the idea of a "malleable" chip.
posted by brundlefly at 4:33 PM on September 4, 2007


brundlefly, FPGAs are usually programmed on bootup - in my experience, you have a small controller (CPU) that loads the "program" (but it's not really a program at all) when it gets power, but they may be more sticky nowadays. The FGPA will have a couple of pins that are dedicated to doing nothing but accepting programming. It can be done on the fly, but like someone said upthread, that's still pretty research-only.

If you want to play with some of the basic concepts of FPGA/CPLD programming, you may want to look into Functional Programming. A few of the thought processes are similar, and aren't anything like what you'll come across normally.
posted by TheNewWazoo at 4:47 PM on September 4, 2007 [1 favorite]


They'll be cracking 20 character passwords before you can even memorize them.

Not true -- this system cracks 8-character passwords taken from a set of 64 characters (uppercase, lowercase, digits, and some punctuation, I assume). That is something like 281 million million combinations (648 to be exact). Sounds like a lot, but this hardware chews through it in no time.

Now let's consider what happens when the character set is expanded to 94 (all printable ASCII characters, "space" not included). The number of combinations is now 948, which is about 6100 million million, or about 21 times more effort. You can wait 21 times as long, or buy 21 times more boards, or some combination of the two. (or wait for faster hardware -- Moore's "Law" suggests that 6 years might be long enough to get a 21-fold increase in speed.

Now consider increasing the length of the password from 8 letters to 20 letters, with the expanded 94-character set. 9420 is 2901 million million million million million million combinations, a number with 39 digits. That's 10 million million million million times more work than the original length-8, 64-character problem. You'll have to hope that Moore's "law" holds out for 40 years and buy 217 million times as many chips and wait 217 million times as long for one 20-character-long password to be cracked.

Of course, that's assuming that the 3x1039 passwords are equally likely. For instance, the passwords "For god so loved the world" and "all men are created equal" are more likely than "7+$?gzUEE3@ctVr#t-@." when passwords are created by humans.
posted by jepler at 4:53 PM on September 4, 2007 [1 favorite]


For those worried about having to memorize 100-digit passwords with 100 different letters or whatever, there is also Key Strengthening. Basically, instead of running the password through a one-way function once, you run it through that function say, 100 times. Now, to get the password, in theory you need to reverse that function 100 times, rather than just once.

The disadvantage of this is that it slows down verification by the same factor that it slows down brute forcing. But, if you keep upping the number at the same rate of Moore's law, you could, in theory, stay ahead of the curve, at least as far as pure brute-force approaches go.
posted by blenderfish at 5:00 PM on September 4, 2007


Muddler writes "Gee, I'm so thankful hackers are looking out for my safety and security by posting exactly how to crack security for the entire world to see and use."

They are "solving" a well-known problem. It had been proven earlier, but this is a step further. Cryptography does not need to rely on obscurity to be secure. The information needed to crack it was out there from the beginning. That's how cryptography works. It's math, not smoke and mirrors. And it's better if it gets out there as soon as it's known so that potential issues can be dealt with as soon as possible.
posted by krinklyfig at 5:04 PM on September 4, 2007 [1 favorite]


No love for the IP-address map? Certainly re-purposing hardware to do something new is really cool, but that map is cool too!

Simple introduction to FPGAs: first, all digital electronics -- your computer and MP3 player, but also your microwave oven and your DVD player -- is built from gates. These are just boolean functions: AND, OR, NOT, NAND, ...

An FPGA is a gate array -- a very large array of gates, usually all of one type (NAND is quite popular). You have a rectangular array of gates -- think of houses laid out in a city grid, with E-W and N-S streets. Connections between the gates can be made or broken in the field (i.e. not at the factory) -- you can put roadblocks on some streets, and leave others free. By judiciously selecting the roadblocks you can construct an arbitrary circuit.

The end result of programming an FPGA is a circuit. It could be a CPU or a DVD-player controller or ...
posted by phliar at 5:05 PM on September 4, 2007


Space Filling Curves are the new hotness.
posted by delmoi at 5:11 PM on September 4, 2007


No love for the IP-address map?

Meta.
posted by dmd at 5:13 PM on September 4, 2007


Malor, how and when is this done? Are these chips rewritable? Is it done on the fly? The Wikipedia article kind of lost me. I'm just kind of blown away by the idea of a "malleable" chip.

Yes, they're rewritable. It's basically a huge grid of logic gates that you can tell how they respond to inputs, and how they interact with each other (via programmable switches). All this is done with ordinary memory cells in each gate and switch so they know what to do - there's no actual rewiring.

To "run" a program on one you set up each stage successively across the chip, apply the input data to one side, and get the output on the other side very quickly. This means in effect, you can run a whole subroutine in one clock cycle, vs the many it takes to run on an ordinary CPU.
posted by cillit bang at 5:15 PM on September 4, 2007


Actually I was going to say that Space Filling Curves were the new X where X was something nerdy, but I couldn't think of anything. So it's a one way function, F(X) = "Space Filling Curves." So that's kind of ironic.

/ubernerd.

Connections between the gates can be made or broken in the field (i.e. not at the factory) -- you can put roadblocks on some streets, and leave others free.

Huh, I never knew thats how the word "Field" was meant in that phrase. At first I thought it was some electrical field that could reset the circuit, or maybe some kind of digital metaphorical representation of a field, or maybe just the grid that the gates were laid out on. That's pretty funny.
posted by delmoi at 5:17 PM on September 4, 2007


To "run" a program on one you set up each stage successively across the chip, apply the input data to one side, and get the output on the other side very quickly. This means in effect, you can run a whole subroutine in one clock cycle, vs the many it takes to run on an ordinary CPU.

Or you can just create a CPU right on the chip and run programs that way, which is much more satisfying.
posted by delmoi at 5:19 PM on September 4, 2007


TechnoLustLuddite writes "It's time to change your paypal password to something much longer. (and change it often)"

I would hope PP already uses something other than SHA-1 or MD5, and/or they use multiple hashes or very long keys. Still, not a bad idea to go with a long password, and change it often.
posted by krinklyfig at 5:23 PM on September 4, 2007


delmoi: Or you can just create a CPU right on the chip and run programs that way, which is much more satisfying.

If your application needs to do decision making (conditionals,) but would benefit greatly from a special-purpose operation, or can be treated as a program on highly vectorized data, (i.e., your ALU is wide and/or funky,) that is actually a reasonable approach.
posted by blenderfish at 5:31 PM on September 4, 2007


Okay, let me take a stab at explaining what FPGAs are and how they work. I've actually had a course where we designed circuits and then uploaded them to FPGAs to test, so I know how to build digital circuits to do things like add, subtract, make flip flops (memory units), state machines, and even whole CPUs.

It's very interesting, and while I could try to explain it, I would just go on and on forever. this is the latest version of the textbook I used, and skimming through it now it's very clear and easy to read. But um, it's $143. But, I loved the class and I thought that stuff was fantastic. And the book comes with an FPGA programmer and simulator so you can actually try it out yourself.

I'm not sure I could have learned this stuff outside of a classroom environment (I would have slacked off) but if you're a good self-learner you should do well. If you do you'll understand how computers work at the most fundamental level (which is probably why it was required for CS majors).

Anyway, fascinating stuff.
posted by delmoi at 5:38 PM on September 4, 2007 [1 favorite]


(err, sorry I actually didn't explain them at all, I just linked to the book. It's hard to know where to "start")
posted by delmoi at 5:41 PM on September 4, 2007


Just try to crack this hash: #

Streching: Ħ...

Here we go: ‡‡
posted by delmoi at 6:08 PM on September 4, 2007 [5 favorites]


Here is a board you can buy for $150 if you want to play around with FPGAs. Not a monster FPGA (you won't be cracking codes with it, in other words,) but cool nonetheless.
posted by blenderfish at 6:09 PM on September 4, 2007


I know metafilter stores plain-text passwords, but that still boggles my mind a bit. Of course, any site you go to that is able to send you your lost password (as opposed to resetting it to something random and sending you that) is also storing your password as plain text, something to consider.

My favorite is a site I joined with a throwaway password which sends you a monthly update that includes both your login and your password in plain text in the email...
posted by maxwelton at 7:55 PM on September 4, 2007


Well, they may be storing your password encrypted, rather than hashed. That's not quite the same as plain-text, although someone with access to the encryption key can decrypt them to plain-text.
posted by smackfu at 8:44 PM on September 4, 2007


I heard the real reason we can't change our passwords is Matt only stores them in has form on the server. The plaintext versions are printed out and stored in a big roledex kept on Fiona's desk.
posted by Mitheral at 8:58 PM on September 4, 2007


Matt only stores them in hash form on the server

Geez.
posted by Mitheral at 8:59 PM on September 4, 2007


Well, they may be storing your password encrypted, rather than hashed. That's not quite the same as plain-text, although someone with access to the encryption key can decrypt them to plain-text.

That doesn't help, since if they are storing it encrypted, and storing the encryption key, then it's still possible to recover the password
posted by delmoi at 9:13 PM on September 4, 2007


So he made that box from Sneakers?

Neat..
posted by Lord_Pall at 11:05 PM on September 4, 2007


Connections between the gates can be made or broken in the field (i.e. not at the factory)

Uh, I always thought it had to do with the relays within the routing fabric being MOSFETs, which are field-effect transistors.
posted by spiderskull at 10:33 PM on September 5, 2007


« Older FILM IS ABOUT TO START...   |   We sell fucking boxes Newer »


This thread has been archived and is closed to new comments



Post