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 Hardware

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.

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.

Comments

Comment viewing options

Have gone the easy money has Bitcoin my dear. Today there are many people involved, the competition is great. I've also had my glory days, but I'm currently involved in other projects Camiseta Personalizadas

I'm glad to see bitcoin making strides in mainstream media. I started mining in early 2011 but after reading about how easily people could get their coins stolen from hackers, I considered how devastated I would be if I lost everything AND it wasn't FDIC insured. Regardless of my reluctance, it seems more people are catching on in an attempt to avoid the impending hyperinflation coming to America. Anyway, I found this article on Reddit about a processing company to conducted the most bitcoin transactions in a single day recently. Pretty interesting stuff: http://ow.ly/ckXlN

I'm truly enjoying the design and layout of your website. It's a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a developer to create your theme? Fantastic work!