The Road to Better Password Cracking (Part 1)

Or: how I learned to stop worrying and love AWS GPU clusters.

Passwords are terrible.

And I don’t mean just your Netflix password or your home Wi-Fi password. I’m talking about passwords as an idea. Passwords are existentially terrible. The reason passwords are terrible is simple: they’re meant to be easy for humans.

We must remember them and, if we’re tech-savvy individuals, we have a lot of them to remember. Their importance is not to be underestimated. A correct password is often the only thing standing between you and your bank account, your inbox or your tax filing software. By design, passwords demand to be simple and easy to remember.

It just so happens that this also makes them easy to guess or crack. If any of your passwords have been part of any one of the giant password breaches in the last decade, it’s in a list that anyone can download and use.

The process looks something like this:

This is easy to do and doesn’t require any expensive hardware. Even on a low-power setup, wordlists don’t take very long to go through. But what about when wordlists fail, and the password hash still hasn’t been cracked?

Brute-forcing is Great – Until It Isn’t.

Brute-forcing, or the process of trying every combination of every possible character, is time-consuming and has a low rate of success. If the password isn’t all digits or all lowercase letters (which we have almost no way of knowing, otherwise we wouldn’t be trying to crack it), the password won’t show up quickly.

Perhaps I know that a common password pattern (hereafter referred to as a “mask”, which will make sense later) consists of five lowercase letters with a single digit at the end. I may choose to denote this as such:

`llllld`
l = lowercase letter (a-z)
d = digit (0-9)

I could also try and test for an uppercase letter at the beginning and a special character after that single digit:

`ullllds`
u = uppercase letter (A-Z)
s = special character (!,@,#,$,%, etc.)

Once again, even choosing the right pattern is mostly just guesswork, no more mysterious than the plaintext version of the hash I’m trying to retrieve.

If the owner of that password used a special character or combination of lowercase letters, uppercase letters, and digits, the possibilities to account for would increase exponentially. And I mean that without a server warehouse of dedicated cracking hardware, a sufficiently complex password could take billions of years to crack (in theory).

But human beings are predictable, are they not? Surely the possibility of retrieving a password from a hash doesn’t go out the window as soon as you run out of wordlists. Can brute-forcing be made better (or at least less bad) by leveraging predictability?

Predicting Predictability

To increase my chances of successfully retrieving a plaintext password via brute-forcing without purchasing a server farm, I first needed to understand what patterns people were following when creating passwords.

To do this, I used the infamous “rockyou.txt” password list, home to over 32 million unique passwords leaked from the application developer, RockYou. Since all of these passwords were being used in the wild, the list worked as a large enough sample for my statistical work. This password list is included in all default installations of Kali Linux as well as the famous SecLists repository.

The version I used contained 14,344,391 unique passwords, still large enough to gain something meaningful from.

Converting these passwords to masks required only some processing power and a bit of Python. What was born of this effort is a little tool I’ve called Masker, the source code for which can be found here.

The primary snippet that matters is this one:

for n, char in enumerate(list1):
    if char.isupper():
        list1[n] = "?u"
    elif char.islower():
        list1[n] = "?l"
    elif char.isdigit():
        list1[n] = "?d"
    else:
        list1[n] = "?s"

This particular style of replacement is due entirely to the fact that hashcat, an extremely powerful cracking tool, understands character type-specific signifiers separated by question marks as masks.

After a successful run, the password list became a list of masks (the question marks are for hashcat to understand – I will get to this in a later blog post):

Running Masker over every one of the 14 million passwords in rockyou.txt only took two or three minutes, but the result was a list of masks like the one above. The next steps were to identify how many times each unique mask occurred in the list and rank them by commonality.

With a little Bash magic, I was able to get a list of every unique mask produced by Masker, ranked by occurrence. I wanted to know which masks were the most common and see if a minority of them would constitute a majority of passwords (yes, I had a hunch and, spoiler alert: I was right).

cat masks.txt | sort | uniq -c > results.txt

Here are the top 10:

An analysis of the top 1,000 masks revealed some interesting data, the primary lesson being that most passwords fall into one of approximately 100 masks:

The exact percentage of passwords from the rockyou.txt list that can be cracked with one of 100 masks is 78.33% (rounded up to the hundredths). That’s 11,236,434 passwords that can be cracked with the top 100 masks (.068%) out of 146,579 unique masks derived from the original ~14 million unique passwords I used in my sample.

But the craziness doesn’t stop there. Many of these masks can be lumped together using hashcat’s incrementation features:

~# hashcat -h | grep -i 'increment'
 -i, --increment                |      | Enable mask increment mode                           |
     --increment-min            | Num  | Start mask incrementing at X                         | --increment-min=4
     --increment-max            | Num  | Stop mask incrementing at X                          | --increment-max=8

As a practical example, if I wanted to brute-force with lowercase letters up to 10 characters instead of just 10 characters alone, I could do something like this:

~# hashcat -m 1000 -a 3 hashes.txt ?l?l?l?l?l?l?l?l?l?l -i

This would go through every combination of lowercase letters with a length of one, then two, then three, and so on, up through 10.

Even more usefully, hashcat’s incrementation feature allows us to use more than just one character type at once. This will make up much of what I discuss next time.

What’s Next

Be on the lookout for Part 2 of this blog series. In the next post, I’ll be taking the data from this post and applying it practically. This will involve building out hashcat commands with variations in mask usage.

The goal of this research is to boost the ability of security professionals and ethical hackers to crack passwords beyond relying wordlists. By more accurately predicting unknowns using past data, we should be able to build faster, more reliable and more cost-efficient ways of cracking passwords.

In the end, password cracking and password cracking tools are nothing new. There is nothing novel or groundbreaking about anything that will be in this blog series, but I hope the knowledge serves to help professionals better secure their environments and assets.

Contact

Questions about policies or compliance and where to start? Contact us here! We’d love to chat with you and see how risk3sixty can meet your organization’s needs.