2019-08-12 11:43 | Gustav Jensen

Your complex password might be unsafe: Hashcat and statistics used to analyze 500 million leaked passwords

A lot has happened since web servers used to store user credentials in plaintext. Now, servers store hashes of passwords which is much safer, but this is not enough to ensure that a hacker won't be able to retrieve the original password.

Password security mainly has two sides to it:
(a) how does the server store a user's credentials
(b) how does the user select their password

Servers don't store your password safely

Point (a) has improved through the years. In the beginning, passwords would be stored in plaintext along with the username. This meant that if a hacker got access to the database, he could merely dump the datebase and have access to all user logins. This still happens even today, but much more seldom.

In a more modern approach, hash functions are used to obfuscate the password in the database. There are many different ways to do this, some more secure than others. Hash functions such as MD5, SHA1, SHA256 are typically used. Often, they're combined with a salt which is a random string appended to the password before hashing -- this is to prevent identical passwords from yielding the same hash.

This does make life harder for the bad guys. However, thanks to increasing computation power (see Moore's law) and smarter strategies, it is typically possible to crack many passwords in manageable time. By cracking, we mean hashing billions of different possible passwords to see if they yield a hash that is present in the database.

Unfortunately, most of the commonly used hash functions are not well suitable for passwords. To make it more difficult to crack passwords, a hashing function should be computationally expensive such that the number of hashes that can be computed per second is limited. Common hash functions such as md5, SHA1, etc. are comparatively "easy" to compute and enable hackers to use special hardware (GPUs, FPGAs) to speed up the cracking process drastically.

Some hashing functions address this issue, one of the more well known ones being bcrypt. bcrypt uses a parameter to make computation increasingly more expensive and also makes it unsuitable to use GPUs.

Sadly, the use of proper password hashing functions such as bcrypt is rarely seen in the real world.

hashcat is a modern tool designed specifically for cracking password hashes. We'll use this later.

So in regard to point (a), there is much room for improvement. The next issue is how users select their passwords. This makes matters worse, as we shall see.

Your password is most likely quite bad

In password cracking, bruteforcing is feasible up to a certain point. By bruteforcing, we mean trying every possible character combination up to a certain string length. Depending on the hash function, cracking system and time frame, it can be feasible to try all combinations up to 7 or 8 characters. Beyond this, the time frame may be too impractical since the keyspace (number of possible passwords) is too large. Since passwords often are required to be at least 8 characters, this doesn't look too good for the hackers when passwords are longer than 8 characters.

However, we can exploit the fact that humans typically select their passwords in predictable ways. As an example, modern password policies often require a combination of upper and lower case letters as well as symbols or digits. Thus, a commonly seen pattern is to let the first character in the password be an upper case letter and add some numbers or symbols at the end of the password.

This information can be directly applied when cracking with the hashcat utility.

Mask attacks in hashcat

Suppose we know that a good portion of passwords are 10 characters and follow the pattern "Goodpass12", i.e. an upper case letter followed by lower case letters and ending in two digits.

If we try all combinations of alphanumeric characters (a-z, A-Z, 0-9), traditional bruteforcing requires trying 62^10 (839.299.365.868.340.224) combinations to guess any password of length 10, and that is passwords without symbols. Trying this many combinations would be infeasible, taking several years even with a fast setup. However, we could guess the above password by trying much fewer passwords, by following the pattern mentioned.

We can create a hashcat mask for it: ?u?l?l?l?l?l?l?l?d?d

This means that the first character must be an upper case letter, the following 7 letters must be lower case, and the last 2 characters must be digits. By using this mask, the keyspace is reduced to:


26*26*26*26*26*26*26*26*10*10 = 20.882.706.457.600

In comparison, the inital keyspace is 40191 times larger. Thus, by applying a specific mask, we can guess many passwords in a lot fewer tries, assuming we used a well fitting mask.

Still, the above large number is almost 21 trillion. Is it feasible to calculate that many hashes in reasonable time?

Let's assume we can generate 500 million hashes per second, which is not unreasonable if it's a fast hashing algorithm such as MD5 (which is commonly used, sadly), on a modern setup. In this case, it would only take 11.6 hours to try all possible passwords of length 10 that fit the given mask. In comparison, trying all alphanumeric passwords (a-z, A-Z, 0-9), it would take more than 53 years to try all combinations.

This shows the power of "optimizing for the common case". Instead of blindly trying all possibilities, we try certain patterns which are used by humans when selecting passwords (for example, having the first character as an upper letter is common when passwords are required to have at least one upper case letter).

Armed with this knowledge, how do we go about creating good masks for hashcat which can guess most passwords possible with least guesses?

Stats on a 500M password set

We have lately been gathering passwords from various dumps on the internet and collecting them into one large database. The purpose was to carry out some statistics, but in more detail than what is typically seen in blogs. After some time, we had gathered roughly 500M passwords into one huge text file.

The next challenge was to sanitize the data (remove noise), import all those passwords into a MySQL database and then execute statistics queries. We gathered statistics on the following:

  • password lengths distribution (calculated on a smaller subset)
  • distribution of character types on each position in the password (discarding passwords shorter than 8 characters)
  • most commonly used characters and symbols

Sanitizing the data

The first challenge was to remove noise from the dataset. In our text file, we had passwords listed line by line following a "email:password" format. But in some of the dumps we used, there were some strange occurrences. For example, a lot of the passwords appeared to be hashed, e.g. $HEX[70656b...65c3b161]. Clearly, that was not an actual password and needed to be decrypted. Thus, we removed all such passwords from the dataset and other strange reoccurring ones.

Password length

The password length statistics were made on a subset of the total dataset to be able to complete the query within reasonable time. The result can be seen in this figure:

It can be seen that most passwords are 8 characters and there seems to be a normal distribution. The standard deviation is 2.76, which means it makes sense to focus on passwords in the range 8-11 (passwords shorter than 8 are often not allowed anymore). Most of the passwords are between 6 and 10 characters, with a majority in the 6-8 range. This is not looking very good. A simple way to make your password more secure is to increase its length beyond 10 characters at least, to make bruteforcing (more) impractical.

Note: The remaining statistics are only carried out on passwords that are at least 8 characters long, to prevent "too easy" passwords from affecting the results.

Distribution of character types on each position in the password

Next, we have the distribution of character types on each character position in the passwords, see figure 2. The categories "Digit", "Lowercase", "Uppercase" should be self-explanatory. The category "Special" is any printable ASCII character that is not a letter nor digit. The category "other" is used for an unprintable ASCII character or otherwise unusual character, for example special Unicode characters.

The figure is read as follows. For character position 1 in a password, 18.22% had a digit, almost 75% had a lowercase letter and 6.51% had a uppercase letter. And so forth for the remaining character positions.

In this figure, there are several interesting points to consider:

In the first 10 characters of the "average" password, a digit is more common on each increasing position, with a climax on position 9 and 10. This is interesting. A common password pattern is to end a password in one or a few digits, to increase the complexity. Since roughly 54 % of passwords are 8-10 characters long, it makes sense that the percentage of digits peaks at these positions. If we consider only passwords that are exactly 8 characters long, the same pattern can be observed.

Another interesting point is that for character positions 1-10, an upper letter is most probable on the first position. This supports the pattern where a user capitalizes the first letter of his password in order to satisfy common password policies.

Most common characters

In order to reduce the keyspace when cracking passwords in hashcat, it makes sense to look at the most (and least) commonly used characters in passwords. We want to remove as many characters from the keyspace as possible, to be able to crack more passwords in less time.

Overall, in the following figure, it can be seen that most passwords consist of mainly lower case letters and digits.

In the following four graphs, you can observe the frequencies for these character classes: upper case letters, lower case letters, digits and symbols.

Digits

Any of the ten digits 0-9 can be observed often in passwords, with 1 being the most popular by far and 6 being the least used. Since all digits occur regularly, it does not make sense to exclude any particular digits from the keyspace.

Lower case letters (only english alphabet)

The letters 'a' and 'e' are by far the most popular ones, and 'z', 'x' and 'q' being the least popular. Still, all letters can be observed, so it might not make sense to remove any of these from the hashcat keyspace.

Upper case letters (only english alphabet)

'A' is by far the most used upper case letter, but all the other upper case letters are also seen quite often, so it does not make sense to remove any upper case letters from the keyspace.

Symbols (only ASCII printable symbols)

Here, it gets more interesting for us. In the ASCII table, there are a total of 38 symbols (!,#,/,(,), etc.). However, many of these symbols are rarely used in passwords. From our stats, full stop (.) is by far the most popular symbol, followed by underscore (_) and then at-sign (@). In order to reduce the keyspace, we can create a mask that only tries the top ten most common symbols instead of all 38. The top ten occurring symbols are these (in order of popularity):

  1. .
  2. _
  3. @
  4. !
  5. -
  6. *
  7. (space)
  8. #
  9. $
  10. ?

These ten symbols make up 88.4 % of all used symbols across all passwords. This seems like a good tradeoff to make -- removing 28 characters from the symbol keyspace and still covering 88.4 % of used symbols.

Creating efficient masks for hashcat

On a modern setup, it's possible to test all combinations of ASCII printable characters of length 8 within a day. For passwords that are 9 characters long, roughly 2.5 months are required on a powerful cracking system with 4 GPUs. Thus, at this point we need to start using masks in a smart way. Therefore, let us consider only passwords longer than 8.

First, let's create some useful hashcat masks that we can combine later:

The ?c stands for "custom", and it contains all lower case and upper case letters, all digits and 10 common ASCII symbols. Thus, this mask has 26+26+10+10=72 distinct characters. This is an improvement from all 95 printable ASCII characters.

Let's make a mask for cracking passwords of length 9. Idea: define a mask which has 1 upper/lower case letter as first character, followed by 3 lowercase letters, followed by 5 custom characters:

`?t?l?l?l?c?c?c?c?c`

This mask seems reasonable because upper case letters in many cases only occur on first position, and lower case letters are common in the beginning. This also allows for common symbols, digits and all ASCII letters at the remaining positions. The total number of unique passwords that follow this mask is:

(26+26)*(26^3)*(72^5)=1.768.421.839.601.664

This keyspace can be exhausted within 6 hours on a good cracking machine with 4 GPUs. This is a great improvement over "2.5 months" which was required for all possible ASCII passwords of length 9. Of course, this mask will not capture all passwords of length 9, but it should be able to capture a good amount.

A similar approach can be used for passwords of length 10, 11 and so forth. Keep in mind that the longer the password is, the more "tricks" you need to use in order to reduce the keyspace to a manageable size.

For example, for passwords of length 10, we can use this mask:

?t?l?l?l?l?l?c?c?c?c (1 upper/lower, 5 lowercase, 4 custom)

Using the same system as the one we used for the other calculations, this keyspace can be exhausted in roughly 2 days which is not too bad (on md5 hashes).

Conclusion

This post demonstrates why your password should be complex. If you follow a simple pattern that many humans follow such as Julie1984, then there's a significant risk of having your password cracked even if it's longer than 8 characters. The solution is to use unusual patterns in your password and make it as long as you can manage.

Moreover, use two-factor protection whenever possible as a second line of defense in case your password gets cracked.


Kontakt os

+45 2054 4448

[email protected]

Vester Farimagsgade 41, 1606 København V

Services | Uddannelse | Blog

© 2020 Danish Cyber Defence A/S · Vester Farimagsgade 41 · 1606 København V · CVR 38871064