Hack and /

Password Cracking with GPUs, Part II: Get Cracking

Kyle Rankin

Issue #214, February 2012

Your hardware is ready. Now, let's load up some software and get cracking.

In Part I of this series, I explained how password cracking works in general terms and described my specific password-cracking hardware. In this article, I dig into the software side of things and describe how to put that hardware to use cracking passwords. I also discuss the two main types of attacks: dictionary and brute-force attacks. As I describe each attack, I also give specific examples of how I used the software to attack phpass, the hashing algorithm currently used for PHP-based software like WordPress.

For the purposes of this article, I created a sample WordPress blog on my server and created a few custom accounts—some with weak passwords and others with truly random passwords. Then, I went into the database for the site and pulled out the phpass password hashes for each account and put them into a file that looked like this:

$P$BpgwVqlfEwuaj.FlM7.YCZ6GQMu15D/
$P$BGMZP8qAHPjTTiTMdSxGhjfQMvkm2D1
$P$BOPzST0vwsR86QfIsQdspt4M5wUGVh.
$P$BjAZ1S3pmcGOC8Op808lOK4l25Q3Ph0
$P$BPlIiO5xdHmThnjjSyJ1jBICfPkpay1
$P$BReStde51ZwKHVtiTgTJpB2zzmGJW91

The above hashes are legitimate phpass hashes created from six-character passwords. I could tell you the passwords, but that would defeat the fun of cracking them yourself.

Proprietary Video Drivers

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. 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. In my case, I downloaded the AMD-APP-SDK-v2.5-lnx32.tgz file from AMD, extracted it, and ran the provided Install-AMD-APP.sh shell script as root.

Hashcat

Many different password-cracking suites exist both for CPU- and GPU-based cracking. After reviewing all the options, I decided on the Hashcat family of cracking tools available at 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.

hashcat:

  • CPU-based, so slower than the GPU-based software.

  • Supports the widest range of hashing algorithms.

oclHashcat:

  • GPU-based password cracker.

  • Supports a moderate number of hashing algorithms.

  • Built-in support for dictionary, brute-force and mask attacks.

oclHashcat-plus:

  • GPU-based.

  • Supports the most hashing algorithms of the GPU-based hashcat crackers.

  • Optimized for dictionary attacks against multiple hashes.

  • Can support dictionary input from a pipe, so brute-force is possible.

oclHashcat-lite:

  • GPU-based.

  • Optimized for attacks against a single password hash.

  • Fastest of the hashcat family, but with the most-limited password hash support.

maskprocessor:

  • Generates dictionaries based on patterns you supply.

  • Not a password cracker in its own right, but can pipe output to oclHashcat-plus for a brute-force attack.

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 what the command output looked like when I ran the example against the 32-bit version on my test rig:

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.

Dictionary Attacks

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 hash 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”.

Calculating Cracking Speed

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
Hash.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 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 626 = 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: 628 = 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.

Brute-Force Attacks

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

  • ?s = symbols.

You also can define a custom character set with -1 (or -2, -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 my example brute-force attack, I 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 my 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. In my next and final part of the series, I will discuss how you can tune the above attacks to get better performance, and also how to blend both dictionary and brute-force attacks to get the best of both worlds.

Kyle Rankin is a Sr. Systems Administrator in the San Francisco Bay Area and the author of a number of books, including The Official Ubuntu Server Book, Knoppix Hacks and Ubuntu Hacks. He is currently the president of the North Bay Linux Users' Group.