The Exponential Nature of Password Cracking Costs

Flavio De Cristofaro used to run our Security Consulting Services (SCS) group and long time password cracking enthusiast was recently asked to present at AppSecLatam2012 on Lessons learned from Recent Password Leaks. The following is his analysis on the exponential nature of password cracking costs.

The exponential nature of password cracking costs

Let’s assume for a moment that you suffered a security breach for a web application accessed by your customers. Somehow, an intruder was able to evade all the security measures you had in place to breach your website database and was able to obtain all the usernames and password hashes related to your clients. Under this scenario and putting aside the breach itself, the two immediate questions to answer to the management will be:  “How were we protecting user’s passwords?” and “Would the intruder be able to impersonate our clients (obtain their corresponding plain text passwords)?” These questions are somewhat subjective and to properly answer these questions you need to understand the costs of password cracking, and what elements of your password policy affect those costs. In other words: how, from a design perspective, can we make the cracking process more time intensive thus reducing the ability of an attacker trying to crack a specific set of password hashes in a reasonable amount of time.

Quick point – a reasonable amount of time changes based on the profile of your attacker. A script kiddie might dedicate a few hours to a few days to trying to get access to those passwords. A nation state attacker may have more resources available and be willing to devote more time to processing the password hashes. In summary, there are four key components that define the cost of cracking a password:

  • The hashing algorithm used to protect the password.
  • The use of salted passwords.
  • Minimum password length allowed.
  • The minimum charset required to the users when selecting their passwords. (Which equates to the minimum password complexity required.)

 

To show how the four components above relate to the initial questions asked by management, I won’t give a definition of these four components. Instead, I’ll present you with a few meaningful examples that illustrate how changes to these components affect the strength of the protection of your users' passwords.

Example 1 – Cost of cracking a password

Let’s say that the compromised database had only one single password hash corresponding to the site’s administrator. The password was hashed using a hashing algorithm not suitable for password protection (like MD5) and the attacker has access to a very standard computer with an i5 processor and an ATI Radeon 7970 graphics card (which, on amazon would cost approx $213 and $443 respectively).

Image
Cost of cracking a password

 

This figure shows the exponential nature of time needed to crack passwords. As can be seen, in the scenario where the attacker is trying to crack the password using uppercase letters only, using the hardware setup I previously described the attacker won’t be able to cover (at least in two months) all the possible combinations for passwords that are more than 12 characters long.

Example 2 – Enforcing a password complexity policy

For this example let’s use the same preconditions as in example 1. By modifying the charset in use we’ll obtain the following graphic.

Image
Enforcing a password complexity policy

 

Figure 2 highlights the impact of changing the charset in use. In summary, under the conditions previously defined an attacker applying brute force will be able to test (in one day):

  • All the combinations for a ten character password if only uppercase characters are allowed.
  • All the combinations for a nine character password if uppercase characters & digits are allowed.
  • All the combinations for an eight character password if uppercase & lowercase characters are allowed.
  • All the combinations for a seven character password if uppercase, lowercase, digits and symbols are required.

As you can see the length of the password that can be tested goes down as the complexity increases. So, by simply enforcing a reasonable password complexity policy a developer can drastically reduce the ability of the attacker to decrypt any password of certain length in a timely manner (a meaningful length of time).

Example 3 - Enforcing a minimum password length

For the purpose of this example we’ll take the original preconditions defined in the first example but we’ll add an additional precondition – the password complexity policy requires users to create passwords having at least one uppercase character, one lowercase character, one digit and one symbol. Under this scenario, the password length vs. days to crack curve will look like the one presented in figure 3:

Image
Enforcing a minimum password length

 

As can be seen, if you enforce a password length of at least 9 characters including at least one character in each of the aforementioned charset families, the attacker won’t be able to cover the whole space by using his available hardware. The addition of a new character increases the time exponentially.  

Example 4 - Selecting the proper hashing algorithm

To work through this example let’s step back and return to the initial scenario. One of our assumptions was having a developer used a weak algorithm (like MD5) to hash the users' passwords. In this example we’ll analyze the effect of selecting a strong hashing algorithm to protect stored passwords. For the purpose of this example we’ll use the following assumptions:

  • The compromised database had only one single password hash the one corresponding to site’s administrator.
  • The attacker has access to a very standard computer with an i5 processor and an ATI Radeon 7970 graphics card.
  • The password was stored using bcrypt
Image
Selecting the proper hashing algorithm

 

The difference is dramatic, by using a stronger algorithm to hash the password and forcing the attackers hardware to spend more time to process each possible password we can make it unrealistic for the attacker to reverse a reasonably long password in a given time frame.

Example 5 – The effect of salting passwords

In this final example let’s assume that the attacker was able to obtain a list of 10 password hashes hashed using MD5. Now the attacker has a couple of options to get the plain text password for example using Rainbow Tables or applying brute force. If you decided to salt your passwords you’ll be limiting the options of the attacker (he won’t be able to use Rainbow Tables against the salted passwords) and you’ll be also increasing the time/computational power required to crack the universe of 10 leaked passwords considered in this example (The attacker must run the same brute force attack 10 times, one per password+salt pair included in the list). Throughout these examples we presented important components to take into consideration while designing your password-based authentication scheme. In any case you should consider using a combination of these factors as a single measure won’t be really helpful. For example if you salt your passwords but your password policy allows using passwords like 1234 your efforts to protect your passwords will prove fruitless. If users are allowed short passwords with no special requirements then their password could still be cracked, but by taking the time to understand what would be possible for an attacker to reverse we can implement password policies that help elevate the threat and can be easily explained/defended to our users and businesses. 

Explore Core Password & Secure Reset

CTA Text

Core Security provides a complete, integrated solution for automated password management. Core Password and Secure Reset work together to provide a convenient and secure password reset solution for your organization. 

LEARN MORE