How to Break 30 Per Cent of Passwords in Seconds

February 6th, 2017 by Oleg Afonin
Category: «Cryptography», «GPU acceleration», «Passwords & Human Factor», «Software»

This article opens a new series dedicated to breaking passwords. It’s no secret that simply getting a good password recovery tool is not enough to successfully break a given password. Brute-force attacks are inefficient for modern formats (e.g. encrypted Office 2013 documents), while using general dictionaries can still be too much for speedy attacks and too little to actually work. In this article, we’ll discuss the first of the two relatively unknown vectors of attack that can potentially break 30 to 70 per cent of real-world passwords in a matter of minutes. The second method will be described in the follow-up article.

The Speed of Brute Force

With today’s GPU acceleration algorithms, cloud computing and distributed attacks, one can gather substantial resources to crack a password. So why are we saying that brute-force attacks are inefficient? It’s simply a matter of speed. Even the latest hardware can offer just barely acceptable speeds when attacking modern protection formats such as Microsoft BitLocker or Office 2013 passwords.

As you can see, attacking an Office 2013 document is relatively slow at only 7100 passwords per second. We came to that number on a single high-end PC equipped with a single NVIDIA GTX 1080 board. Granted, you can bump up the number of GTX boards or use several computers, and while it does help, it may still not be fast enough.

Using an online password calculator, we can count how many possible combinations there are for the different types of passwords. For example, a very simple password containing 6 lower-case letters and no numbers already has 309 million possible combinations. With a computer equipped with a GTX 1080 board that is capable of trying 7100 passwords per second (Microsoft Office 2013) you’re looking 12 hours of brute-forcing, which is quite reasonable. A more typical 8-character alphanumeric password has 2.8 trillion possible combinations will take 12.5 years to break.

In other words, you’re looking at the following real-world recovery speeds:

Per second Per hour Per day
MS Office 2013 7100 25,560,000 613,440,000
What can be broken 2-3 characters 4 alphanumeric characters 5 alphanumeric characters (just barely)

Of course, you can speed it up by adding more GPU accelerators and building a network for performing a distributed attack, but there are smarter attacks that are much cheaper and a lot faster than brute-force.

There are two ways to speed up the attack: increasing attack speed or reducing the number of passwords to try.

Use Real Passwords

Reducing the number of possible combinations to try during the attack is the most efficient and cost-effective way of breaking passwords. Traditionally, security researchers make an assumption that most passwords are based on dictionary words. While this is true for many passwords, it’s extremely insecure to use just one or two words from the dictionary as a password. In many cases, users will base their passwords on the dictionary, using a mix of lower-case and upper-case characters and numbers to make their passwords more complex. We’ll cover the possible mutations in one of the later articles. Today we’ll be looking at something else: the real passwords chosen by real users.

When attacking a document that belongs to a user you know nothing about, building a relevant custom dictionary may be a problem. However, there is a workaround.

Many users think alike. They tend to choose the same passwords. How do we know? Because, from time to time, these passwords leak. LinkedIn, eBay, Twitter, Dropbox and many other big name online services have been compromised and user passwords leaked. Mark Burnett (https://xa.to/) takes his time to monitor these leaks and maintain lists of the most common passwords. His Top 10,000 Passwords article is available at the following link: https://xa.to/top10k

According to Mark Burnett, there are still a huge number of people who pick from a very small list of common passwords. Here are some interesting facts gleaned from his most recent data:

  • 0.5% of users have the password password;
  • 0.4% have the passwords password or 123456;
  • 0.9% have the passwords password, 123456 or 12345678;
  • 1.6% have a password from the top 10 passwords
  • 4.4% have a password from the top 100 passwords
  • 9.7% have a password from the top 500 passwords
  • 13.2% have a password from the top 1,000 passwords
  • 30% have a password from the top 10,000 passwords

(Source: https://xa.to/top10k)

Statistically, about 30 per cent of consumers use passwords from the Top 10,000 list. This brings us to the idea of actually using the top 10,000 passwords as a custom dictionary for performing an attack in Elcomsoft Distributed Password Recovery.

In our tests, the use of the Top 10,000 Passwords list could really break about 30 per cent of passwords in a matter of seconds. In order to further increase the chance of successful recovery, we recommend configuring Elcomsoft Distributed Password Recovery with two consecutive attacks. The first attack would use the Top 10,000 Passwords list as-is, while the second attack would append numbers (0 through 99) to the end of each password. This bumps the length of the password list to 1 million possible combinations, which takes roughly two minutes to process with a GTX 1080 board.

Using the Top 10,000 List in Elcomsoft Distributed Password Recovery:

  1. Configure a classic dictionary without mutations using the downloaded 10,000 passwords list
  2. Configure an additional attack to append numbers 0 through 99 to the end of each password from the 10,000 list

You can download the various password lists from the following links (external sources):

–          Github: https://github.com/danielmiessler/SecLists/tree/master/Passwords

–          Direct download link for Top 10,000 Passwords list: GitHub

The Passwords directory will hold a number of password lists that can be used by multiple tools when attempting to guess credentials for a given targetted service. This will include a number of very popular lists in cooperation with their maintainers, including the RockYou lists maintained by Rob Bowes. Password lists containing the count are located in the “withcount” folder. Lists over 100Mb have been compressed. merged.txt.tar.gz contains a merged list of all password lists in the “Password” directory; it has been sorted and uniq’d.

One Million Passwords List

In addition to the Top 10,000 list, Mark Burnett has released a list of 10 million passwords (https://xa.to/10m). The list contains 10 million most popular passwords encountered in recent password leaks. While you are welcome to download and use the list, it offers diminishing returns in terms of performance. If the 10,000 passwords list can break about 30% of passwords in a matter of seconds (or minutes, if you use the recommended mutations), the 10 million passwords list with no mutations can help you break about 33% of passwords in about 25-30 minutes (using the same configuration and the same Office 2013 document).

Download link:

–          https://xa.to/10m

Conclusion

Using a dictionary containing the most popular leaked passwords can help breaking passwords to documents with strong protection faster and easier. Using the Top 10,000 Passwords list alone can potentially solve up to 30% of cases in a matter of minutes, while using 10 million passwords can help in 33% of cases. However, there is yet another method requiring access to the user’s PC that can potentially break up to 70% of the user’s passwords. We’ll discuss that method in our next article.