Passwords: A step-by-step analysis of breaking them

If you read my last post on passwords or you’ve had some previous experience in messing around with cracking passwords, then you can understand how difficult it is to guess them.

But why do all of us underpaid security consultants get all excited and happy when we get a SQL injection or get domain admin and access all of those lovely password hashes in your database/domain/Unix box? Quite simply, because people create passwords and people are predictable beasts.

How passwords are stored

First off, let’s have a little digression into how passwords are stored, this can be performed in many ways, depending on how the programmer has weighed up the computational time over security equation. The most common technique is to create a hash of the password – by passing it through an algorithm such as MD5 or SHA1 that returns a unique (-ish) string. This can be further complicated by adding a salt – a little bit of seasoning to make it harder to create a table of results.

Mathematically this can be represented as:

To check whether the password is correct, a password is requested from the user, then it is hashed with the same salt and algorithm and the /hashes/ are compared. The advantages of doing it like this is that it is harder to guess the passwords.

But how hard is it to guess passwords? I have sat on a USB stick a selection of 13423 password hashes created using the mysql password function, which generates a custom SHA1 hash. This is a selection of hashes that came from a live service on the Internet (a game) and I may go into detail how I obtained them, although this is a story for another day (with names changed to protect the naïve).

How many passwords can I break?

So, I’m stuck on a slow train meandering to the capital; so how many of these can I break before I get to the station?

My tool of choice is hashcat which, although it’s not open source, has become very popular recently as it uses your graphics card to offload a lot of processing. This can get significant speed bonuses. I also have a new laptop with a separate graphics card.

The first step we can do is to test the hashes against a dictionary of known passwords. These have been gathered from various sources, including common words, previously cracked passwords from other sources (including linkedin and rockyou) and my personal dictionary of passwords that I’ve cracked in the past.

To kick this off we do:

This is telling the program to attempt to crack mysql hashes (-m 300) and to remove found hashes from the source file. We will later be recycling the found passwords for further attacks.

This goes and churns away at the rate of about 120 million hashes a second, causing my laptop’s fan to sound like a jet engine and attempt to melt through the shoddy east midlands train table.

This first foray finishes by the time we get to Kettering and succesfully cracks 7.5 thousand passwords.

Bruteforcing…

We can do some other things with the dictionaries, but I’m going to leave them for later and try some simple bruteforce techniques. As there are no passwords restrictions on the original site, there are probably some weak passwords which I could get by brute forcing all lower case, upper case and numbers.

This is applied in hashcat by using the mask mode as a brute force:

The magical parameters here are to set brute force mode (-a 3), a password pattern for 8 lower case characters (?l?l?l?l?l?l?l?l) which is incremental (i.e. start at 1 character and build up to 7). We will be repeating this with a mask of ?d?d?d?d?d?d?d?d (for digits) and ?u?u?u?u?u?u?u (for upper case). I’m only doing 7 characters as 8 will take about 30 minutes which is too long for this train journey!

This finishes by the time we get to Wellingborough adding an extra 627 cracked hashes.

Let’s modify the brute force a bit. If we assume people use “words” as passwords then they could use the common title case format, e.g. Password; so we tune it to look for an upper case followed by lower case letters: ?u?l?l?l?l?l?l

Let’s speed things up…

This is getting too slow, there’s 45 minutes left on the train so we need to kick some more complex testing. Hashcat comes with a selection of rules that mangle the entries in a dictionary in methods that have been shown to be successful in the password.

We can tell hashcat to use rules, as below. Note that as we’re writing our results to the dictionaries directory we are feeding back previously found passwords into the loop.

I discover I’m now running out of battery power on my laptop as the graphics is killing it and this archaic train carriage has no power points, predicting that I’ll run out of battery before I get to the most exciting place that is know as London St Pancras. So I’m going to have to cut this short. I kill off the d3ad0ne rule early to try another tactic (which is a pity as it was working well).

Digininja wrote a neat tool called pipal, which takes a file of passwords and analyses it for patterns, e.g. by checking for common words or common formats. The nice thing is that it provides a list of hashes at the end the analysis that we can pass back through hashcat. Most of these are ones that I’ve already done, but one has potential: ?l?l?l?l?l?l?l?d – 7 lower case letters, followed by a digit.

At this point, as the train speeds past Luton, thankfully without stopping, I’ve been cracking passwords for about an hour, whilst also writing this up and I’ve cracked 10109 passwords, leaving 3315 left. My laptop battery icon tells me I have about 14 minutes left with this amount of power usage, so I have to stop here. There’s still lots of potential in the rules and I guess I could crack most of the remaining passwords without too much difficulty. (update later.)

Just for completion, we can do a pipal analysis of the passwords:

The top 10 base words (i.e. “password” in Password1) can be seen:

From this we can tell that this is a game (pokemon, zelda), and also that several passwords are most likely throw-away or specific only for this account.

The top 10 table of years is also interesting:

Bearing in mind that this service is a game, it offers us an insight into its audience: 8 out of 10 of the top years are from 1986 to 1993, which if we assume are the birth years of the players, we see that it has a prime audience between 28 and 21. This is information which would take scores of marketers to hunt down, whereas we can glean it in a much more geektastic fashion.

The two errant years (2010, 2012) also point that the game may have had two releases.

One final thing is to indulge in my childish joy of certain taboo words: (the regexp has been censored to not offend certain sensitivities:

That’s 45 passwords with rudeness in them, what a sweary lot!

Here’s the table of which methods got out how many passwords: