Password cracking, mining, and GPUs

People imagine that sophisticated hacking requires sophisticated computers. The truth is that almost everything a hacker does can be done with a cheap notebook computer, or even a mobile phone.

The major exception is password cracking, and related crypto tasks like bitcoin mining and certificate forgery. In these cases, a minor investment in hardware can be warranted.

In particular, those who need to crack passwords (pen-testers, sysadmins, hackers) should buy a gaming graphics card in order to speed up cracking. Or, when buying notebooks for pen-testing, they should choose those with graphics processors.

What’s a GPU

Computers, as we know them, used to contain a single processor, called the central processing unit or CPU".

Now they contain a second processor, called the graphics processing unit or GPU. As the name implies, GPUs are intended for graphics, which means games and video.

But GPUs aren’t just for graphics; they are good for any highly repetitive task. Typical GPU applications include video transcoding, statistical modeling, physics simulations, medical imaging, financial modeling, and cryptography. Password cracking is just one form of cryptography.

It’s important to keep in mind that graphics processors are no more powerful than central processors. Trying to run non-repetitive tasks on the graphics processor results in a speed decrease. Foolish hackers regularly attempt this, and are regularly disappointed. Instead, graphics processors are optimized for calculations that are highly repetitive, whereas normal processors are optimized for the major of code that isn’t very repetitive.

These days, most computers come with a GPU. The iPhone has an ARM CPU and a PowerVR GPU. The latest Intel "Sandy Bridge" CPUs come with a custom Intel GPU built into the chip. AMD processors (formerly called "Athlon") have a version of the Radeon GPU on the chip. Except for AMD’s built-in GPUs, these aren’t programmable by the user, and therefore, can’t be used for anything other than graphics (although Intel keeps promising to make their GPU more programmable). Even AMD’s built-in GPU is slow relative to add-on GPUs.

Instead, when this paper mentions GPUs, it refers to the gaming cards with the fastest GPUs. Such cards can easily accelerate password cracking by 20 times. Using such cards, people are putting 8 GPUs in a system, accelerating password cracking by 160 times. That means a password that would otherwise take 6 months to crack can now be cracked in a day -- assuming you are willing to spend $3000 on graphics cards.

Radeons are better than GeForce

There are only two manufacturers of high-end gaming cards: nVidia with their GeForce cards, and AMD with with their Radeon cards. Both sell a wide range of cards, from the very cheap (but slow) to the very expensive (but fast). Prices typically range from around $100 for the cheaper ones, to $800 for the most expensive, with the best price-performance ratio around the $250 mark (two $250 cards will likely be faster than a single $700 card).

For gaming, Radeons and GeForces have roughly the same performance, with the fastest GeForce cards being the slight favorite. For super computer applications, like weather modeling or physics simulations, the GeForce cards are the clear favorite. However, for crypto, it’s the Radeon cards that come out on top. For equivalently priced cards, a Radeon card will be over twice as fast as a GeForce card when cracking passwords.

There are a few reasons for this. Radeons have more theoretical power, but suffer from a "VLIW" instruction set that makes it hard to realize that power in practice. Password cracking is VLIW friendly, though, and can tap into that power. In addition, Radeons have specific integer instructions like "bitalign" (aka. "rotate") and "BFI_INT" ("bitselect") that speed up popular crypto operations.

Thus, a cheap model of the Radeon like the HD 5770 costing $109 will outperform an expensive GeForce model like the GTX 590 costing $749. The most expensive Radeon model, the HD 6990 costing $739, will be over three times as fast at cracking passwords.

Thus, the consequence is that if you want to crack WiFi WPA2 passwords, Windows NTLM password, Unix salted MD5 hashes, or Bitcoin hashes, then you should probably invested in one of these GPUs. Even a cheap $100 card can increase speed over your desktop processor by 20 times. Ideally, you should buy a Radeon card for this rather than a GeForce card.

Moore’s Law

The above discussion applies to June 2011. Next year, CPUs and GPUs will be twice as fast.

But it’s the relative performance that matters. Next year’s $250 graphics card will likely outperform next year’s CPU by 20 times. Unless AMD or nVidia makes radical changes to their chip architectures, the next generation of the Radeon will still likely outperform the next generation of GeForce cards.

Therefore, when you finally get around to buying that graphics card for password cracking, you’ll have to look on the web for password cracking benchmarks to see which card is currently giving the best price/performance ratio.

Notebook GPUs

The above discussion have been for desktop computers that consume a lot of electricity. Pen-testers often don’t have that luxury -- they often only have a notebook (running something like BackTrack Linux). In that case, they want to buy a "mobile" version of the Radeon or GeForce chips. They can’t buy such chips as addons, but instead, have to choose a noteboook that has their desired chip.

According to recent benchmarks, mobile Radeons are still faster than GeForces, but it’s highly variable. Notebook GPUs have an enormous range, as batttery life is traded for gaming speed. Thus, one notebook with a powerhungry GeForce may be a better choice than another notebook with a battery conserving Radeon. You’ll have to look at benchmarks, or theoretical numbers (based on clock speeds and core counts) to figure out which is best for your needs.

Also note that there are three classes of laptops: the normal laptops, the low end netbooks, and the high-end gaming laptops. Historically, only the high-end gaming laptops contained graphics processors, but now graphics processors are appearing throughout a wider range.


High-end gaming laptops are the best choice for password cracking power. The biggest ones have graphics processors that rival desktop cards. You can buy an Alienware M18x with a Radeon mobile GPU that is faster than all but the fastest desktop GPU. It’s also 18-inches across, weighs 8 pounds, lasts only a few minutes on battery, and costs $2400.

GPUs are becoming more popular in average notebook computers. Asus makes some nice, average sized laptops with GeForce GPUs for a good price. Of particular note are the current MacBook Pros (15 inch or 17 inch) which come with a good Radeon GPU. The GPU is far slower than desktop GPUs, but of course, they don’t drain the battery, and don’t jack up the price. My MacBook Air has a GeForce GT320M that triples password cracking speed over the built-in processor (benchmarks below).

Curiously, GPUs are becoming popular for cheap "netbook" computers. That’s because the low-power central processors do not handle video well. Therefore, manufacturers are including low-power GPUs for video. Some Intel netbooks have Intel graphics, which can’t (yet) be programmed for password cracking. Some contain nVidia’s ION graphics, which is hardly faster at cracking passwords than the Atom CPU. The best choice these days are the new AMD netbooks with the C-30, C-50, and E-350 processors that are a combination of x86 CPU with a Radeon GPU on the same lower-power chip. A $280 Asus EEE PC 1015B or an $430 HP dm1z are the best netbooks for pen-testers at the moment.

What about FirePro, Quadro, and Tesla?

Both AMD and nVideo make more expensive cards for high-end customers. These are actually the identical chips in the gaming cards, but sold for 10 times the price. They would be a foolish choice for password cracking.

There is a reason for the higher price. The companies put features into the chips for high-end customers, then disable those features for gamers. Thus, if you are a graphics artist using software to draw the next 3D movie, the version with the high-end features enabled are probably worth the price. But these features mean nothing to password cracking. Indeed, the high-end chips are slightly worse at password cracking: because high-end customers care about reliability, they run the chips at speeds slight slower (and cooler) than for gamers.

The more expensive version of the Radeon card is called "FirePro". The more expensive version of the GeForce card is called "Quadro".

But, there is a third high-end version of the GeForce card called "Tesla". This is just like the "Quadro" card (all high-end features) enabled -- but it’s missing a the output port. You can’t connect a monitor to it. It’s purpose is just for GPU processing, like geological simulations to help find oil, or financial models to figure out the best stock price. Because they are missing the "display" portion, they use slightly less electrical power. People building supercomputers out of GPUs tend to choose the Tesla cards. If you rent "cloud computing" time using GPUs, they will probably be Tesla cards. I find this all a bit foolish -- GeForce or Radeon cards would be far more cost effective.

GPUs vs. FPGA vs. ASIC

Rather than doing password cracking in software, it should be possible to do it faster, cheaper, and with less electrical power using hardware like FPGAs or ASICs.

While this works in theory, it doesn’t work so well in practice. CPUs and GPUs are so cheap because their manufacturers sell them in enormous quantity. You could design your own chip that is 100 times faster than a cheap GPU, but it would cost you 200 times as much, per chip.

Some people do great things with hardware, such as Pico Computing, but most of the time, it’s just easier writing software for a mainstream chip, then let Moore’s Law make the chips go faster every year.

Building the ideal password cracking rig

Let’s say that you want to build the fastest computer (for cracking) for the cheapest price. Such a system will be driven by the cost of the graphics cards.

A relatively cheap, and simple, solution would be to buy three or four Radeon HD 6990 (as of June 2011) cards and stick them into a homebuilt computer. You’ll need a bigger power supply, a motherboard that supports four PCIe slots (spaced correctly for cards that are two-slots wide), and a slightly bigger case, but all of these are relatively common. Other than that, you only need a standard CPU, memory, and boot drive -- the cheaper the better (the less you spend on these, the more you can spend on more graphics cards).

This solution is probably best for pen-testers. Our time costs money. It doesn’t take long to assemble.

But for hobbiests who enjoy messing around with hardware, the economics are a bit different. They might want to get fancy, for example, building a custom case using PCIe extender cables or even a PCIe splitter to fit 32 cards in a system. You only need PCIe 1x speed for password cracking, not the full PCIe 16x speed that’s used for gaming.

Regardless of the system you build, you probably need to worry about cooling. Such systems are going to produce a lot of heat. Moreover, you need to worry about where your cool air comes from, and where the hot air is going. It’s going to be an annoyance whether you are in a data center, in a lab, or installing it at home.

All this cooling will cause of a lot noise (unless you are in a data center). Hobbiests buy expensive components that cut down on the noise, like water cooling systems. I stick my computer in a closet that happens to have an air conditioning duct. In labs or at home, you may find yourself playing with ducts to get the cooling right and the noise reduced.

Windows, using commercial software like that from Elcomsoft, takes the least effort to setup and run, but Linux using free software gives you more control over what’s going on. For example, some people (such as Bitcoin miners) have reported that Windows can’t recognize more than 4 cards, whereas Linux has no problem. There is also the issue of systems only being able to use cards connected to monitors -- which requires either a monitor be plugged into each card, or a "dummy plug" be used to make the card think there is a monitor installed.

But, the thing to keep in mind is decreasing marginal returns. Buying a $250 Radeon card will increase cracking speeds by 20 times. Buying a second $250 Radeon card will only double the previous card’s speed. A single desktop with four Radeon HD 6990s for $3000 will increase cracking speed by 160 times. Buy a second such system, for another $3000, will only double your cracking speed after that.

Overclocking

Hobbiests spend a lot of time trying to overclock their systems. If they work hard enough at it, they can get an extra 20% performance increase.

The trick for password cracking is to increase the speed of the GPU, but at the same time, decrease the speed of memory. Unlike graphics, GPU cracking doesn’t use the memory. By lowering the memory speed, you lower power consumption, and lower the amount of heat generated. That power/heat can then be used to increase the speed of the GPU calculations.

Radeons come with an overclocking application on Windows, but it doesn’t allow you to change much. This utility will only let you overclock by 10%, but won’t let you underclock the memory.

A graphics card vendor named MSI has its own Radeon overclocking utility "Afterburner" that you can use for all Radeon cards, not just those sold by MSI: http://event.msi.com/vga/afterburner/download.htm. This will allow you do overclock the chip more, as well as underclock the memory.

If you are overclocking the card, it may cause your system to crash. If that happens, you may need to increase the voltage sent to the card.

If overclocking, and if you have increased voltage, your card will produce a lot more heat. You’ll probably have to adjust the fan speed to compensate, to lower temperatures back down to reasonable levels. You probably do not want to run your card above 80 degrees Celsius. On the other hand, fans aren’t designed to run at high speed for extended periods -- the more you jack up fan speed, the more likely it is for the fan to fail. If your card is running below 68 degrees Celsius, you might want to consider lowering the fan speed.

Overclocking, higher voltage, and higher temperatures will decrease the lifetime of the graphic chip before it fails. You probably don’t care: two years from now, when your overclocking madness causes the chip to fail, you’ll be upgrading to the latest GPU anyway.

The economics of cracking

Putting a single $250 Radeon card in your desktop for password cracking makes sense. Building multiple cracking rigs for massive number crunching probably doesn’t. The reason is that password cracking is an exponential effort.

Consider passwords chosen from an alphabet of UPPER and lower case, numbers, and $ymbols. That’s roughly 100 different characters. That means every letter we add to a password increases the difficulty of cracking by 100 times.

Let’s say you can crack all 8 character passwords within a day. It would then take you 100 days to crack a 9 character password and 27 years to crack a 10 character password. We can graph this effort on the following picture:

As you can see, it's a bit nonsensical. Below 9 characters, it's nearly zero effort to crack passwords. Above 9 characters, the line shoots almost straight upwards. Only around 9 characters do we see a line that isn't nearly-zero or nearly-infinite.

That means there are three classes of passwords: those we can crack easily with a desktop computer (8 characters or fewer), those we cannot crack at all (10 characters or more), and those we can crack more of if we purchase more expensive computers (9 character passwords).

There is decreasing marginal returns to buying GPUs. Buying a single card increases cracking speed by 20 times. Buying a second GPU willy only additionally increase speed by 2 times.

Buying a $3000 rig can increase cracking speed by 160 times. Buying a second $3000 rig will only increase cracking speed by an additional 2 times. All people have to do is add another character to the length of their password, increasing it’s complexity by 100 times, and defeating your investment.

On the other hand, there is the fact that your competitors have the same idea in mind. Let’s say that you go in and pen-test a company that hired a different pentesting firm last year. That other firm found passwords and cracked all the weak ones. You find the same password list. If you crack fewer passwords, you look like a poorer pentester than the previous firm. If you can crack a few more, you look like a better pentester.

The same is true of hackers. You can assume the target company has already fixed all it’s weak passwords -- but where "weakness" is defined as "crackable by one GPU". If you come in with two GPUs, you’ll find a few more passwords.

This is of particular interest to Bitcoin miners, where it’s essentially a race against other miners to find the latest hash. Whereas twice the computing power does not equal twice the number of passwords cracked, twice the power does mean twice the earning power for Bitcoins.

Bitcoin mining benchmarks

Password cracking and Bitcoin mining are essentially the same thing. You can therefore leverage their work in figuring out what hardware you want for cracking.

A good reference is the list of hardware at https://en.bitcoin.it/wiki/Mining_hardware_comparison.

I’ve selected a few of the numbers from the link above, as well as benchmarked my own computers.

MH/s	Hardware	Notes
0.2	ARM Cortex-A8	CPU in my iPhone
0.6	ARM Cortex-A9 dual	CPU in my iPad
1.1	Intel Atom N270	My pen-testing netbook CPU
1.8	nVidia ION	A common netbook GPU for Atom CPUs
2.5	Core 2 Duo 2.13 GHz	My MacBook Air CPU
6.1	nVidia GT 320M	My MacBook Air GPU
6.2	AMD C-30	Asus $280 netbook with GPU/CPU combo
11.0	AMD E-350	HP dm1z $450 netbook with GPU/CPU combo
17.0	Radeon HD 6490M	2011 MacBook Pro
19.2	Core i7 980x	My desktop, 6-core 3.3 GHz, hyperthreaded, top-of-the-line CPU
21.0	PS3	Playstation 3 using the Cell GPU
100.0	Tesla M2050	Amazon EC2 cloud computer w/ Tesla card
300.0	Radeon HD 5830	$109 card popular with miners -- if you can find one
314.0	Radeon HD 6950	$240 @Newegg and probably what you should buy
358.0	Radeon HD 6970	My desktop's graphics card, cost $330
800.0	Radeon HD 6990	Fastest single card, overclocked, roughly $740, with two GPUs

• SSE
  
  SSE is the name for GPU-like instructions that are part of the CPU. They operate on 4 numbers at a time, and therefore, are 4 times faster than normal instructions for repetitive tasks.
  
  Modern processors, like the Intel Atom, Core2, and Core i3/i5/i7, as well as AMD Athlon/Phenom/etc. processors, all can execute two SSE integer instructions per clock cycle. That means pretty much that you just need to look at MHz in order to figure out which processor will crack passwords faster.
  
  This also applies to Intel’s energy efficient Atom processor. While the Atom is notorious for being slower on most tasks, it’s just as fast, per-core and per-MHz, as the other processors. Thus, a 1.6 GHz Atom will perform the same as a 1.6 GHz Core2 or 1.6 GHz AMD processor at password cracking -- but at about half the power. In addition, the GeForce-based ION graphics chip designed to go with the Atom hardly accelerates password cracking.
  
  
• MacBook Air
  
  
  
  Whereas I use netbooks for pen-testing, I use a MacBook Air for everything else (programming, writing blogposts). I’m not a fan of Apple’s operating system, I usually run Windows or Linux on it.
  
  My MacBook is faster at password cracking than the older netbooks, but is quite a bit behind the latest Radeon-based netbooks. My next pen-testing netbook is likely going to be the HP dm1z.
  
  
• HP dm1z
  
  
  
  At $429, this is expensive for a "netbook", but it has 4 features that make it stand out.
  
  1. It has the GPU/CPU combo from AMD. Not only is its CPU faster (dual core), but its GPU is a lot faster.
  2. It comes with 3-gigs of RAM, expandable to 8-gigs. Most "netbooks" come with 1-gig, expandable to 2-gigs.
  3. It comes with Gigabit Ethernet, whereas other "netbooks" come with only 100-mbps Ethernet.
  4. HP claims 9.5 hour battery life, which is at the top end of the range for "netbooks".
  
  Thus, while I’m tempted by its cheaper cousin the $279 Asus, I’ve ordered the dm1z to take to DefCon. I’ll be blogging successes/failures with it in a few days.
  
  
• MacBook Pro
  
  
  
  The 15-inch MacBook Pro is probably going to be the notebook of choice for a lot of hackers, and probably has the best password cracking speed of anything short of a specialized gaming notebook.
  
  Currently, there are some quirks with Mac OS X bitcoin mining software, compared to Windows or Linux. It should be getting as much as twice the benchmarks posted above.
  
  
• Radeon HD 6950
  
  If you do password cracking, you should get one, maybe two, of these cards and stick them in your existing desktop computer. They give the greatest bang-for-the-buck right now. An older Radeon HD 5830 are probably better bang-for-the-buck at half the price, but all the Bitcoin miners have snapped them up, so you can’t find any.
  
  The 6950 is slight slower than the 6970, but at 66% of the price. The fastest single card, the 6990, combines two 6950 GPU chips on a single card but at three times the price.
  
  Six months from now (Juned 2011) the situation will have changed, but in all probability, a $250 will still provide the best bang for the buck.
  
  
• Tesla
  
  
  
  As the benchmarks show, the Tesla card is 10 times the price, but 1/3 the performance, of a Radeon HD 6950 card. That’s 30x price-performance difference.
  
  The economics don’t get any better using a Tesla in Amazon’s EC2 instances. You can currently make money mining bitcoins using Radeon cards, but you’d lose a lot of money trying to mine bitcoins on Amazon.
  

Password cracking vs. power consumption

The section above focused on capital costs, comparing graphics cards by their price performance. If you only run them occasionally to crack passwords, this is the most meaningful comparison. However, if you run them 24-hours a day, 365 days a year, then you’ll me more concerned by how much electricity they use.

A high performance graphics cards uses around 200-watts, but itself (not counting the rest of the computer). The average price for electricity in the United States is 11-cents per kilowatt-hour. Therefore, running that card for a year will cost $192.72. Of course, you need a system to stick that into. You might consider something like a computer based on an Intel Atom processor that only consumes 10-watts by itself. Modern processors, like a low-powered Nehalem, is also good at running at lower power. But, most desktops run at around 100-watts of power while doing password cracking.

Usually, the card that wins on price/performance also wins at electrical power usage. The Radeon HD 6950 mentioned above turns out to be at the top in terms of passwords cracked per watt.

But there are other things to consider. Some states, notably California, punish people who use too much electricity. In some cities, using more than 400 kilowatt-hours per month kicks you up to the next bracket, where electricity could cost 20-cents, 30-cents, or even more per kilowatt-hour. You may find it cheaper buying a generator than buying electricity from the grid.

Or, being that it’s California, you can get a heavily subsidized solar power generating unit for pretty cheap. You can hook it up to power your computer while the sun shines, and either turn off your computer at night or run it from the grid. Some places are now have “smart grids” that monitor electricity on a minute-by-minute basis rather than a monthly basis, and will charge you different amounts depending on the time of day. The price for electricity can be half during the night than during the peak hours during the day. You might configure your computer to run cracking software only at night, and to go to sleep during the day. 

Industrial electricity costs less than residential. A lot of cities have “hacker collectives” where people get together and rent industrial space, for typical non-criminal hacker activities like building robots or taking apart iPhones. They can supply the cheaper industrial rates for electricity for your password cracking or bitcoin mining needs.

Or your can move to a cheaper state. Here is a good reference for electricity prices by state.

What you crack

I thought I’d list the common things that hackers find themselves needing to crack. It’s not really relevant to GPUs, but I thought I’d mention it for completeness.

Bitcoin mining: A fixed number of new bitcoins are generated per day, and it’s a race to find the matching hash before anybody else does. The winner gets the bitcoins. It uses SHA256, which is exactly like SHA256 passwords. There is a lot of free bitmining software on the Bitcoin forums.

WPA passwords: Home users, and many businesses, use WPA, which is protected by only a simple password. In order to make it more difficult, the WPA standard requires a minimum of 8 characters, and rather than protect it by hashing the password once, it re-hashes it 4000 times -- making the computational difficulty to be around a 10-character password. Ten letters in a password is probably beyond the ability for "brute-force" cracking, which tries all combinations, unless you make certain assumptions, such as assuming the person used only lower-case and numbers (which is a valid assumption for most passwords). Most cracking is therefore done using a dictionary of known passwords, followed by "mutations" (such as adding a 4-digit number onto the end). Because the password is "salted" with the SSID, you can’t use rainbow tables to get the hash. There is lot of good software for doing this. I’ve used the free software "pyrit" and the commercial package from "Elcomsoft" in the past. The graph above of relative WPA cracking speeds is for the Elcomsoft package using last year's cards.

NTLM challenge-response: Windows passwords aren’t "salted", which means it’s easier to Rainbow crack them than to crack them. However, you often see "challenge-response" exchanges on the wire. This requires cracking in order to break. You see these with Windows-specific protocols like SMB and MS-RPC. In addition, you’ll see these as an optional authentication on other protocols, such as LEAP authentication for WiFi, or NTLMv2 inside e-mail and HTTP headers.

Salted passwords on a hacked server: When a hackers (or pen-tester) breaks into a server, they will grab the password file or database. Stupid sysadmins either have the passwords in cleartext (no cracking needed) or in simple MD5 hashes (cracked with Raindbow tables). Smart sysadmins "salt" the passwords, which requires cracking. Software: oclHashcat

Documents: PDF, ZIP, RAR, and Word/Excel files are often encrypted. Such files might contain secrets useful for a hacker. Reportedly, Wikileaks had to decrypt an encrypted ZIP file containing the famous "Collateral Murder" video from Iraq. Cracking password-protected documents is the most common feature of commercial software, since home users and businesses need it when they forget their password. There are lots of companies that sell GPU accelerated software for this, such as Elcomsoft.

Conclusion

Buying a $250 GPU that increases password cracking speed 20 times is a no-brainer. Buying a notebook computer based on GPU is probably a wise idea for pen-testers.

But passwords are a little strange. They grow exponentially in complexity, which means you get decreasing marginal returns from buying more hardware. Thus, while buy a graphics card (or maybe two) is cost effective, massive investments in hardware are unlikely to crack that many additional passwords.

Of course, if you are Bitcoin mining, then the more GPUs the better. Even after recent wild fluxuations in bitcoin prices, it’s still profitable at the moment.