Hack and / - Password Cracking with GPUs, Part I: the Setup
Bitcoin mining is so last year. Put your expensive GPU to use cracking passwords.
When the Bitcoin mining craze hit its peak, I felt the tug to join this new community and make some easy money. I wasn't drawn only by the money; the concepts behind Bitcoin mining intrigued me, in particular the new use of graphics processors (GPUs). With a moderately expensive video card, you could bring in enough money to pay off your initial investment and your electricity bill in a relatively short time.
Then Bitcoin tanked. That's okay though, because I hadn't gotten around to building my mining rig yet, and what's more, I found an even more interesting use for Bitcoin mining hardware: password cracking. Bitcoin mining and password cracking are quite similar operations, and a GPU can crack passwords much faster than a CPU or even a small cluster of CPUs. In this two-part article, I explain how to set up and use a password-cracking computer. In this first piece, I focus on the principles behind password cracking and the overall hardware setup. I'll cover the specific attacks and command-line examples in the following article.
Legitimate Reasons to Crack Passwords
Before I get started, let's admit that there are some pretty shady reasons to crack passwords. Every so often you will hear a story of a Web site that was hacked, a password database that was compromised and the thousands of weak passwords that were discovered. Often people get into password cracking because they are trying to break into someone else's system, or they already broke into someone's system, stole their password hashes and are cracking the passwords so they can attack yet another system.
That said, like with lock picking, there are legitimate reasons to crack passwords, particularly for a sysadmin or Webmaster:
Test local users' password strength.
Prove that users follow your password policy.
Understand what your password policy should be.
Cryptography is interesting.
Bitcoin mining is no longer profitable.
In fact, many Linux systems will run a basic dictionary attack when you change your password to evaluate how weak it is. Although it's true that these days most password systems will not allow users to enter passwords that don't fit the password policy, some systems simply let users know their passwords are weak but store them anyway. In either case, it makes sense to audit your passwords at a company just to ensure that a random hacker with a $300 video card can't crack your passwords in a day or two. When you put yourself in the role of the password cracker, you'll start to realize which passwords are easy to crack and which ones are almost impossible, and that will help inform you when it's time to update your password policy.
An Introduction to Password Hashes
Password hashes were created to solve a particularly tricky problem. If users must enter passwords to log in, you have to store those passwords on the system somehow. How do you store those passwords so that they're not plain text, yet when users enter their passwords, you can tell that they are correct? The solution is to encrypt passwords with a one-way hash. The idea behind a one-way hash is that it is relatively easy for input to get encrypted into the hash, but almost impossible to convert the hash back to the original input. If you've ever downloaded a Linux .iso and ran md5sum on it to make sure it matched the original, you were using a very popular one-way hashing algorithm, MD5. Other popular one-way hashes include the SHA family (SHA1, SHA256 and SHA512), and phpass is the modern default for PHP-based sites like WordPress.
When you log in to a Linux system, the password you enter gets converted into a hash with the same algorithm originally used when you first set your password. The system compares this new hash with the hash it has stored on the system, and if they match, it assumes you entered the correct password and you are logged in. So for instance, on a modern PHP site, if your password was 123456, it might get stored as $P$BPlIiO5xdHmThnjjSyJ1jBICfPkpay1.
How Password Cracking Works
On a very basic level, password cracking works much like a regular login. You take a password guess, run it through a hashing algorithm and compare it to the existing hash. If it matches, you cracked the password. The main difference between cracking and a regular login is that you are doing hundreds of thousands if not millions of these comparisons a second.
/etc/passwd and /etc/shadow
The most important thing you need before you crack a password is the password hash. Because we are talking about perfectly legitimate uses of password cracking, this is simple. After all, you should have root access on your own systems or databases, and it should be easy to retrieve the password hashes. In the case of Linux logins, these password hashes used to be stored in /etc/passwd. That seems like a logical place to store passwords on a Linux system. The problem is, that file also stored the user names and user IDs in use on the system, and because of that, the file needs to be world-readable. Back when passwords were stored in that file, any local user could pull the full list of password hashes and start cracking. These days, Linux stores the password hashes in /etc/shadow, where they are readable only by root. In the case of Web site passwords, the hashes usually are stored either somewhere on the filesystem itself or often in a special user table in a database.
The second important thing you need is to know what hashing algorithm was used for those hashes. Without that, you won't know what type of hashing algorithm to use for your attack. In the case of login hashes, the hash type is stored in the password hash itself. If you look at a password hash in /etc/shadow, you'll notice a log of strange characters along with a few $ thrown in. These $ characters delimit different sections of the hash as follows:
$id $salt $encrypted
The id section tells you what hash is being used:
1 = MD5
5 = SHA-256
6 = SHA-512
These days, you are most likely to run into SHA-256 and SHA-512 passwords. Because the hashing algorithm and the salt are stored along with the password itself, Linux password hashes are pretty portable. If you have one hash, you can copy it to another system and use the same password to log in.
Why Use a GPU?
The simple reason to use a GPU instead of a CPU for password cracking is that it's much faster. It turns out that cracking passwords is a lot like mining Bitcoins, so the same reasons GPUs are faster for Bitcoin mining apply to password cracking. The short answer is that there are many more specialized chips on a GPU that perform 32-bit operations really quickly. Although a CPU can perform a lot of general-purpose calculations, the chips on a GPU can perform specific types of operations much faster, and in a much more parallel way. If you want more specifics, this site explains in more detail from the perspective of Bitcoin mining: https://en.bitcoin.it/wiki/Why_a_GPU_mines_faster_than_a_CPU.
The most important piece of hardware you need to crack passwords is a fast GPU. Because cracking passwords is like mining Bitcoins, you can get a good idea of how your GPU would perform by how well it would mine Bitcoins.
This site provides a good list of available video cards and describes their performance: https://en.bitcoin.it/wiki/Mining_hardware_comparison. When you look at that site, what you'll notice is that AMD GPUs tend to be much faster than NVIDIA GPUs, even though for gaming often the reverse is true. The reason for this is explained in detail in the explanation of why a GPU mines faster than a CPU, but in short, AMD GPUs tackle the problem of graphics rending with a lot of small, simple chips that perform 32-bit operations quickly. NVIDIA GPUs have fewer, but more sophisticated chips that are closer to a CPU in complexity. For the purposes of Bitcoin mining or password cracking, which can be highly parallel, those larger number of simple chips work the fastest. Also note that cracking software can take advantage of multiple GPUs, so if you can afford it, and your motherboard can support it, you may find you'll get the same performance out of two cheaper GPUs than a single expensive one.
In my case, I didn't have a desktop PC lying around I could use for this, so I built a special desktop just for password cracking. In case you want to follow in my footsteps, here is my exact hardware along with prices:
GPU: SAPPHIRE FleX 100312FLEX Radeon HD 6950 2GB: $280
Power supply: RAIDMAX HYBRID 2 RX-730SS 730W: $60
Motherboard: ASUS M4A88T-V: $95
CPU: AMD Phenom II X6 1090T Black Edition Thuban 3.2GHz: $170
RAM: Corsair CMX4GX3M2B2000C9 4Gb 240-pin DDR3: $55
Storage: Seagate ST95005620AS 500GB 7200 RPM Hybrid Drive: $100
Case: already owned
Total: $760, $930 with monitor, $340 just GPU + PS
If you already have a desktop that supports a modern video card, you may need to purchase only the GPU and power supply. Keep in mind that modern high-performance video cards require a lot of power, so you'll want at least a 700W power supply in your case, and more than that if you intend to chain two video cards together. I found that the AMD 6950 had good performance for my budget, plus this particular model can theoretically be turned into a 6970 with a firmware update. If you have a larger budget though, you may want to buy two or more 6950s and chain them together.
So there you have it. You now have a month to get your hardware together, and next, I'll discuss the software side of password cracking, explain dictionary, brute-force and mask attacks, and give specific examples with my password-cracking system.
Why a GPU Mines Faster Than a CPU: https://en.bitcoin.it/wiki/Why_a_GPU_mines_faster_than_a_CPU
Mining Hardware Comparison: https://en.bitcoin.it/wiki/Mining_hardware_comparison
Password image via Shutterstock.com.
Kyle Rankin is a director of engineering operations in the San Francisco Bay Area, the author of a number of books including DevOps Troubleshooting and The Official Ubuntu Server Book, and is a columnist for Linux Journal.