When the Bitcoin mining craze hit its peak, people felt the tug to join this new community and make some easy 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 we explain how to set up and use a password-cracking computer. In this first piece, We focus on the principles behind password cracking and the overall hardware setup. We’ll cover the specific attacks and command-line examples in the following article.
Before we 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:
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.
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.
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.
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:
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.
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
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. 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.
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.
For those of you who, like me, believe in open-source software, this next section may be a bit disappointing. To get hardware-accelerated password-cracking software working on your system, you need to install the proprietary video drivers from either AMD or NVIDIA. That said, if you already have been using your system for Bitcoin mining, you already have the drivers and libraries you need, so you can skip to the next section about Hashcat. Honestly, you also could just follow the Bitcoin mining HOWTOs for Linux, and that would describe how to get all the drivers and libraries you need.
Many modern desktops make it relatively easy to pull down and install the proprietary video drivers ( and they may even be included in your current driver version). For instance, an Ubuntu desktop will prompt you that restricted drivers are available to install both for AMD and NVIDIA cards. Most other popular distributions provide good documentation on how to pull down the proprietary drivers as well. In the worst case, you may have to download the software directly from the AMD or NVIDIA and install it that way—they both have clear instructions and software available for Linux just like for other OSes.
Once you have the proprietary drivers installed, you also need the AMD APP SDK for its OpenCL libraries or the NVIDIA CUDA libraries, depending on who made your video card. You likely will need to get these libraries directly from AMD or NVIDIA Web sites. The install is straightforward though.
Many different password-cracking suites exist both for CPU- and GPU-based cracking. After reviewing all the options, We decided on the Hashcat family of cracking tools available at http://hashcat.net . On the site, you will see that a number of different tools are available. At first glance, it can be a bit confusing, as you can choose from hashcat, oclHashcat, oclHashcat-plus, oclHashcat-lite and even software called maskprocessor. Each program has its purpose though, depending on what you intend to do.
Even with the above lists, it may not always be clear which software to use. Basically, it comes down to what type of password you want to crack and what kind of attack you want to use. The page on hashcat.net devoted to each piece of software provides a list of the hashing algorithms they support along with benchmark speeds of how many comparisons they can do per second on different types of hardware. For a given password hash, go through those pages and see which type of Hashcat software supports your hash and has the highest benchmarks. Beyond that, use oclHashcat for mask or brute-force attacks against multiple hashes, oclHashcat-lite for single hashes or oclHashcat-plus if, as was the case with me, it’s the only GPU-accelerated version that supported your hash.
Once you decide which type of Hashcat software to use, installation is relatively simple, if old-school. Just download the .7z package that corresponds to the software, and use the 7za command-line tool (which should be packaged for your distribution) to extract it. The software will extract into its own directory that provides 32- and 64-bit versions for both Linux and Windows. If you have NVIDIA hardware, you will use the binaries that begin with cuda; otherwise, you will use the versions that start with ocl. The directory also will contain a number of example hashes and dictionaries and example shell scripts you can use to make sure your libraries and drivers are in place. For instance, here’s the example provided with the oclHashcat-plus software for cracking a phpass hash on a 64-bit system:
cat example.dict | ./oclHashcat-plus64.bin -m 400 example400.hash
Here’s another example of what the command output can look like
cat example.dict | ./oclHashcat-plus32.bin -m 400 example400.hash oclHashcat-plus v0.06 by atom starting... Hashes: 1 Unique salts: 1 Unique digests: 1 Bitmaps: 8 bits, 256 entries, 0x000000ff mask, 1024 bytes Rules: 1 GPU-Loops: 128 GPU-Accel: 16 Password lengths range: 1 - 15 Platform: AMD compatible platform found Watchdog: Temperature limit set to 90c Device #1: Cayman, 2048MB, 0Mhz, 22MCU Device #1: Allocating 52MB host-memory Device #1: Kernel ./kernels/4098/m0400.Cayman.32.kernel (274238 bytes) Starting attack in wordlist stdin mode... $H$9y5boZ2wsUlgl2tI6b5PrRoADzYfXD1:hash234 Status.......: Cracked Input.Mode...: Piped Hash.Target..: $H$9y5boZ2wsUlgl2tI6b5PrRoADzYfXD1 Hash.Type....: phpass, MD5(WordPress), MD5(phpBB3) Time.Running.: 1 sec Time.Util....: 1008.2ms/0.0ms Real/CPU, 0.0% idle Speed........: 65009 c/s Real, 619.7k c/s GPU Recovered....: 1/1 Digests, 1/1 Salts Progress.....: 65543 Rejected.....: 0 HW.Monitor.#1: 0% GPU, 47c Temp Started: Mon Dec 5 21:12:03 2011 Stopped: Mon Dec 5 21:12:04 2011
In this case, the password was hash234. For all of the hashcat commands, it’s simple enough just to open a terminal and change to the directory you extracted and run the commands locally from there. At the beginning of the command output, you will be able to see what GPUs the software can detect. If you have multiple GPUs in use (even if they aren’t chained), it should find them automatically. If it can’t find your GPU, you will need to revisit how you installed your proprietary drivers and extra libraries.
The first attack you should try is a dictionary attack. With a dictionary attack, you provide the cracking software with a dictionary full of possible passwords to try, such as all the words in the English dictionary. The cracking software then tries each dictionary word until one matches your hash. Since the number of combinations in a dictionary attack is much smaller than with a brute-force attack, dictionary attacks complete much faster. As an example, when I was first researching this article, I let a brute-force attack run for days against a sample set of hashes without cracking one of them. I was able to crack three out of the five hashes with a dictionary attack in less than a minute.
To run a dictionary attack with oclHashcat-plus, first run the command with the
--help argument. That will provide you with the number that corresponds to the algorithm you want to crack. In the case of phpass, that number is 400. Then, run the command a second time and specify the password hash to use with the
-m option, the file in which to store the recovered passwords with the
-o option, and then list the file that contains your hashes and the file or files you want to use as a dictionary. Here’s an example dictionary attack against phpass hashes:
/path/to/oclHashcat-plus32.bin -m 400 -o recovered_hashes ↪example400.hash example.dict
If I had multiple dictionaries, I could list all of them on the command line or even use a shell glob. A dictionary attack is only as good as its dictionaries, but a number of good password dictionaries are available on the Web that you can find with a quick search for “password cracking wordlist”.
Before I discuss brute-force attacks in detail, it’s important to learn how to estimate how long a particular brute-force attack will take. With a brute attack, you aren’t just going through a dictionary of words, you are actually trying all possible combinations of a set of characters. In researching the article, I wasted days attempting a brute-force attack against an eight-character password before I finally did the math and realized it was completely impractical.
The first step is to figure out how fast your hardware can crack a particular type of hash. As you will discover, the number of comparisons per second your hardware can perform will vary widely depending on the hash type, so start a sample brute-force attack just long enough to get a bit of progress output, and then press Ctrl-c to exit. In my case, because I’m using oclHashcat-plus, I needed to download and extract the maskprocessor software from hashcat.net, so it, combined with oclHashcat-plus, could perform a brute-force attack against phpass (don’t worry about the command syntax for now, I discuss the specifics later):
/path/to/mp32.bin -1 ?d?l?u ?1?1?1?1?1?1 | \\ /path/to/oclHashcat-plus32.bin -m 400 \\ -o recovered_hashes phpass-hashes oclHashcat-plus v0.06 by atom starting... Hashes: 6 Unique salts: 6 Unique digests: 6 Bitmaps: 8 bits, 256 entries, 0x000000ff mask, 1024 bytes Rules: 1 GPU-Loops: 128 GPU-Accel: 16 Password lengths range: 1 - 15 Platform: AMD compatible platform found Watchdog: Temperature limit set to 90c Device #1: Cayman, 2048MB, 0Mhz, 22MCU Device #1: Allocating 264MB host-memory Device #1: Kernel ./kernels/4098/m0400.Cayman.32.kernel (274238 bytes) Starting attack in wordlist stdin mode... Status.......: Running Input.Mode...: Piped Has h.Type....: phpass, MD5(WordPress), MD5(phpBB3) Time.Running.: 10 secs Time.Util....: 10001.4ms/180.8ms Real/CPU, 1.8% idle Speed........: 315.3k c/s Real, 351.4k c/s GPU Recovered....: 0/6 Digests, 0/6 Salts Progress.....: 3153920 Rejected.....: 0 HW.Monitor.#1: 96% GPU, 54c Temp
The output line to pay attention to is the line that begins with
Speed As you can see from that output, my GPU can do around 350,000 comparisons per second, so I’ll use that number for the rest of my calculations.
One good site I’ve found for doing cracking estimates is http://www.lockdown.co.uk/?pg=combi . This site describes all sorts of different character sets and password lengths, and it describes how long anything from a single Pentium CPU to a mythical government supercomputer might take to brute-force all combinations. Otherwise, the math is pretty straightforward. Just take the number of characters in your character set (for instance, all lowercase letters would equal 26), then figure out how long of a password you want to brute-force, then raise the first number to the power of the second.
So, for instance, all mixed-case alphanumeric characters (A–Za–z0–9) equals 62 characters. If I wanted to brute force a six-character password, that would be 62 6 = 57 billion combinations.
If you divide 57 billion combinations by a system that can do 350,000 comparisons a second, you get approximately 45 hours to complete the brute-force attack. That’s not bad, but let’s do the same math for eight-character passwords: 62 8 = 218 trillion combinations.
At 350,000 comparisons per second, it would take me approximately 7,200 days, or 19 years, to complete the attack. On the plus side, for another $250, I could complete the attack in less than 10 years! If you add symbols to your brute-force attack, the number jumps to 7.2 quadrillion combinations, or around 652 years.
Once you’ve figured out whether a brute-force attack will complete in your lifetime, the next step is to run maskprocessor and tell it what kind of word list to generate. The maskprocessor command supports a number of common character sets by default with the following symbols:
?d= all decimals (0–9).
?l= lowercase characters (a–z).
?u= uppercase characters (A–Z).
You also can define a custom character set with
-3 ) and then use
?1 to use that custom set. For instance, if I wanted to enumerate through all three-character passwords made up of lowercase characters and numbers, I could type:
/path/to/mp32.bin -1 ?d?l ?1?1?1 000 001 . . . zzy zzz
In our example brute-force attack, we wanted to run through all combinations of uppercase, lowercase and numbers in a six-character password. The resulting maskprocessor command would be:
/path/to/mp32.bin -1 ?d?l?u ?1?1?1?1?1?1
Then, I would pipe the output of that command to oclHashcat-plus:
/path/to/mp32.bin -1 ?d?l?u ?1?1?1?1?1?1 | \\ /path/to/oclHashcat-plus32.bin -m 400 \\ -o recovered_hashes phpass-hashes
As with our dictionary attack, the
-m option specifies I want to crack phpass hashes, the
-o lists the file in which I want to store my recovered hashes, and finally, I specify the file that contains the phpass hashes to crack. On my hardware, it took around two days to run fully through the above brute-force attack.
Now you should be ready to get cracking, but as you’ll find, the world of password cracking can get pretty dense, pretty quickly.
The first area where you can fine-tune your attacks is to put more or less load on your GPU. The
-n option, when passed to oclhashcat, changes how much of your GPU will be used for an attack. The documentation says that this value is set to 80 by default; however, on our computer, it seemed like the default was set closer to 40. When we first ran a brute-force attack, the output told us it was using around 70–80% of my GPU. Once we added
-n 80 to our oclhashcat command, we noticed we were using between 96–98% of our GPU and had added an extra 40,000 comparisons per second:
/path/to/mp32.bin -1 ?d?l?u ?1?1?1?1?1?1 | \\ /path/to/oclHashcat-plus32.bin -m 400 -n 80 \\ -o recovered_hashes phpass-hashes
Experiment with passing different values to
-n , and see whether your comparisons per second and the percentage of GPU used increases. Be careful though; the higher the number, the more power your GPU is going to use (and if it’s not well-cooled, the hotter it will run). Also, if you plan to use the system for other things while you crack passwords, you may notice a greater impact on graphics performance.
Although it may seem like increasing the
-n setting is a no-brainer, it turns out that a higher setting really only benefits brute-force attacks. The hashcat documentation recommends you try lower
-n values when attempting dictionary attacks. Ultimately, the key is to experiment with both high and low values and see what gives you the best results.
With a dictionary attack, you provide the cracking software with a dictionary full of possible passwords to try, such as all of the words in the English dictionary. A brute-force attack iterates through all possible combinations for a password of a certain length. Because a dictionary attack generally has way fewer passwords to try, it is much faster than a brute-force attack. Although a brute-force attack takes a long time, it also ultimately will find the passwords you are looking for.
It turns out you aren’t limited by either a fast, possibly ineffective, attack or a highly effective, but slow, attack. With mask attacks, you can combine the speed of dictionary attacks with some of the thoroughness of a brute-force attack. Mask attacks work by making some educated guesses about the characters that might be used in a password. With a mask attack, you perform a brute-force attack only with a far smaller list of combinations to try all based on a pattern.
Mask attacks make more sense once you see an example. Let’s say that you are attempting to crack a password, and you know the password policy requires the user to select at least one uppercase letter and at least one number. As we mentioned before you can calculate how many combinations are in a particular type of password by taking the number of characters in the character set, figuring out how long the password is going to be, then raising the first number to the power of the second. So, for instance, if you wanted to do a thorough brute-force attack against the above password policy, you would have 62 characters in your character set (A–Za–z0–9) and with an eight-character password, the number of combinations would be: 62 8 = 218 trillion combinations.
At 350,000 comparisons per second on our password-cracking hardware, it would take us approximately 7,200 days, or 19 years, to complete the attack.
The fact of the matter is, when you tell most users to create an eight-character password that has at least one uppercase character and at least one number, most users aren’t going to generate a truly random password. Instead, they likely will make the first letter uppercase and then use lowercase characters until they get to the end of the password, where they either will add a single number to the end of the password or they will put a four-digit year at the end—usually the year they were born, the year they graduated high school or the current year. A mask attack against the same password policy would build a brute-force pattern where you would just try an uppercase letter as the first character, lowercase for the next three, then either lowercase or numbers for the final four characters. In that case, the number of combinations would be: (26) * (26 3 ) * (36 4 ) = ~ 767 billion combinations.
On our hardware, that would take a bit more than 600 hours, or 25 days. Although that’s a long time to crack a password, it’s still a lot better than 19 years and likely will be effective against a large number of weaker passwords.
To describe this pattern, we use the same custom pattern language with maskprocessor that we used in the previous example for regular brute-force attacks, only in this case, we combine a custom pattern that includes all lowercase characters and numbers with a regular set of character patterns. The final maskprocessor command would look like:
/path/to/mp32.bin -1 ?d?l ?u?l?l?l?1?1?1?1
As you can see, I defined a special mask of
?d?l (0–9a–z) and assigned it to 1, then we created a password pattern where the first character was
?u (A–Z), the next three were
?l (a–z), and the final four were
?1 (0–9a–z). The complete command to attempt this mask attack against our phpass hashes with our new custom GPU tuning would be:
/path/to/mp32.bin -1 ?d?l ?u?l?l?l?1?1?1?1 | \\ /path/to/oclHashcat-plus32.bin -m 400 -n 80 \\ -o recovered_hashes phpass-hashes
The final way to improve your attacks further is by applying rules to your dictionary attacks. A rule allows you to perform some sort of transformation against all the words in your dictionary. You might, for instance, not only try all your dictionary words, but also create a rule that adds a single digit to the end of the dictionary word. That will catch even more weak passwords and only increases the number of overall combinations by ten times.
Here’s an even better example of how rules can help crack more tricky passwords. With the new requirement that users must have numbers in their password, a lot of users have resorted to “leet speak”. For instance, instead of using “password” they might use “p455w0rd”. The fact of the matter is, they still are using a dictionary word—they are just applying a basic transformation to it where a becomes 4, s becomes 5, o becomes 0, e becomes 3 and so on. When you want to crack such a password, all you have to do is add the
-r option to hashcat and point it to a file that contains the rule you want to apply. Hashcat uses a custom language to define rules, but it’s not too tricky to figure out, and the installation directory for oclhashcat has a rules directory that contains a number of rule files you can use as a reference. It even already includes a rule for leet speak, so if you wanted to perform a dictionary attack that took leet speak into account, it would look something like this if you ran it from within the oclhashcat-plus directory:
/path/to/oclHashcat-plus32.bin -m 400 \\ -r ./rules/leetspeak.rule \\ -o recovered_hashes example400.hash example.dict
For more information about rules, check out the documentation on the Hashcat Wiki at http://hashcat.net/wiki/rule_based_attack .
You now should have everything you need to refine your (completely legitimate and white hat) password-cracking attacks. On the Hashcat Wiki, you will find even more examples of types of attacks and examples you can use to improve your odds of cracking a password #ash.