Practical Analysis of New Password Cracker

Just before the holidays, I saw a press release regarding some state-of-the-art hash cracking hardware and the headlines made it sound like it was a big deal:
“New 25 GPU Monster Devours Passwords In Seconds”
Well, along with my general interest in hashing and cryptography, we had discussed salted-MD5 password hashing that week with a client. The press release provided an interesting aside to that discussion, so I did some analysis on the benchmarks from which we could draw practical conclusions about its impact. In this article, I’ll provide a high-level overview of why you should be moving from salted hashes to Key Derivation Functions (KDFs), and then plunge into the mathematics and information theory analysis I performed so we can all understand exactly what these benchmarks mean from a practical point of view.

The High-Level

After all is said and done, hash algorithms like MD5, SHA-1, SHA-256, SHA-512, and SHA-3 are designed to be as fast as they possibly can while not producing collisions or reversible outputs. Speed may sound like a good thing but it’s a problem for password hashing. Speed works in the attacker’s favor because his job is to recompute the hashes one-by-one until he lands on the correct value. And while the complete keyspace of even MD5 is well beyond the realm of plausible brute-force attack, the limited keyspace we tend to use makes brute-force attack extremely plausible. Moving from MD5 to SHA-3 will increase your possible keyspace but if you’re still using 8-character passwords, the only security benefit you get is that SHA-3 is marginally slower than MD5.

Well, custom password cracking machines like the one in the article will keep getting faster and we likely still have 6-12 character passwords. There are strong arguments for coming up with something other than passwords for authentication purposes, and people are working on that, but there is a current solution to the brute-force problem. For those of us who still have passwords, the cryptographic solution is to use a key derivation function like S/I S2K (PGP), PBKDF2 (RSA), BCrypt (OpenBSD), or SCrypt (Tarsnap), in place of a salted hash. All of these functions were designed to be deliberately slow in order to thwart brute-force calculation. The idea is that the authentication system only has to compute the hash once given the correct password, but the attacker has to compute the hash, literally, 6 million billion times.

Mathematics & Information Theory

The headline of the article refers to LM (Microsoft’s LAN Manager) hashes but as I mentioned above, I was more interested in the MD5 benchmark. If you’re interested in the other benchmarks, I’ve provided all of the formulas and logic you’ll need to perform the same analysis against those. The benchmark that the author provides for MD5 is 180 billion (180x10^9) guesses per second. If the entire keyspace, meaning all possible one-to-one values, of MD5 were used that would present the attacker with 2^128 possible hashes to calculate for every password. To determine the relationship between 180x10^9 and 2^128, we need to do some math which I’ll go over in the next section.

Practical Speed Analysis

First, we’ll simplify everything greatly by converting the base 2 number (2^128) into a base 10 number because it’s easy for most people to convert other numbers to base 10 notation in their heads for comparison.

Here is the formula:
Let x be the exponent, let a be the starting base, and b the target base, and y be the result:
y = x*ln(a)/ln(b)

To convert 2^128 to base 10, we do: 128*ln(2)/ln(10) = 38.5
Therefore, 2^128 = 10^38.5 = 1x10^38.5 = 1e38.5

So, the password cracker can perform 180x10^9 hashes per second and it has to calculate 1x10^38.5 hashes for every password. The following formula  shows how long that will take:

1x10^38.5 / 180x10^9 ~= 1.75x10^27 seconds

Given 1 year = 3.15569x10^7 seconds
1.75x10^27 / 3.15569x10^7 ~= 5.5x10^19 years

So, with state-of-the-art custom hardware, it would take 5.5x10^19 (10 billion billion) years to crack one salted MD5 hash. That seems pretty secure even given the ½ probability that you will guess the correct value at random. It WOULD be if the entire keyspace could legitimately be used. Unfortunately, the passwords that people can effectively type into a prompt are pretty limited.

Entropy & Other Limitations

A standard ASCII character consumes 1 byte (8 bits) and each byte can theoretically have 2^8 (256) unique values. Because each character consumes 8 bits, 16 possible characters can fit into the keyspace of MD5. To figure out the work needed to guess all of the combinations, we’ll consider the typeable characters: a-z, A-Z, 0-9, and 32 special characters for a total of 94 possible values per byte. 94 possible values is being VERY generous. In practice, I see only 4-6 permitted special characters for a total of 68 possible values per byte but we’ll work with 94 to analyze the best-case scenario. So, in reality, rather than having to try 2^128 possible values, we only have to try 94^16 (~2^105) possible values.

On top of the ASCII entropy limitation, people have a hard time remembering passwords, so most password policies allow between 6 and 12 characters. This further reduces the work from 94^16 to between 94^6 and 94^12.

For comparison, the conversions are:
6 Characters: 94^6 = 6*ln(94)/ln(2) ~= 2^39 ~= 7x10^11
8 Characters: 94^8 = 8*ln(94)/ln(2) ~= 2^52 ~= 6x10^15
10 Characters: 94^10 = 10*ln(94)/ln(2) ~= 2^65.5 ~= 5x10^19
12 Characters: 94^12 = 12*ln(94)/ln(2) ~= 2^79 ~= 5x10^23

Due to practical limitations, the key space of a 128 bit hash has been reduced from 1x10^38.5 to between 7x10^11 and 5x10^23. If we factor in fewer special characters, it is much lower.

Final Analysis

Recall that the hash cracker is capable of generating 180x10^9 MD5 hashes per second. Below is the table of time to crack a salted MD5 password with this technology:

6 Characters: 7x10^11 / 180x10^9 = 3.8 seconds
8 Characters: 6x10^15 / 180x10^9 ~= 9 hours
10 Characters: 5x10^19 / 180x10^9 ~= 8 years
12 Characters: 5x10^23 / 180x10^9 ~= 9 million years


So, there you have it. If you are using 6 or even 8 character passwords, your salted MD5 hashes are well within the practical realm of being cracked if they were to fall into the hands of an attacker.

As I mentioned above, moving to a different fast hashing algorithm isn’t the answer as all of them will eventually be in the same boat. Consider moving to a key derivation function for your password hashing needs.

Non-Negotiable Elements of a Secure Software Development Process: Part 2 - Secure Architecture, Configuration, and Coding Patterns

In September, I gave a presentation focused on helping quality assurance professionals understand how they fit into a secure software development process (SSDP) and how they can take an active role in improving software security.  In that presentation, I discussed essential elements that make up a successful SSDP.  These elements are: security requirements (expectations), secure architecture, configuration, and coding patterns (how to satisfy an expectation), and validation criteria (verification that expectations have been met).  These elements allow an organization to be transparent regarding its security goals and performance.  They also facilitate communication with customers, developers, managers, and other project stakeholders.

This article is part 2 in the series discussing non-negotiable elements of a secure software development process. In part 1 of the series, we discussed how security requirements set clear and reasonable expectations that development teams can plan for and meet to satisfy a specific level of security assurance.  This article focuses on secure architecture, configuration, and coding patterns that equip development teams to meet those requirements.
All three articles are listed below:

Part 1: Security Requirements

Part 2: Secure Architecture, Configuration, and Coding Patterns

Part 3: Validation Criteria

What are Secure Architecture, Configuration, and Coding Patterns?
Secure architecture, configuration, and coding patterns are language specific implementations of code, frameworks, configuration, and application designs that satisfy a security requirement.  They provide development teams with positive examples and instructions to successfully adhere to security practices without requiring them to be a security expert.  

For example, if a team chose to use Hibernate as their data persistence layer, a secure pattern would demonstrate how the team should define domain objects, map those objects to the database, and how to securely retrieve objects from the database programmatically. Specific instructions, code and configuration examples, and discussion should be provided in this pattern to ensure the reader understands the proper implementation.  One element that this pattern would include is how to retrieve objects programmatically using a parameterized hibernate query, shown below.

Query safeHQLQuery = session.createQuery("from Inventory where productID=:productid");
safeHQLQuery.setParameter("productid", userSuppliedParameter);

A similar approach could be used for ASP.NET parameterized queries without the use of an ORM framework:

string sql = "SELECT * FROM Customers WHERE CustomerId = @CustomerId";

SqlCommand command = new SqlCommand(sql);

command.Parameters.Add(new SqlParameter("@CustomerId", System.Data.SqlDbType.Int));
command.Parameters["@CustomerId"].Value = 1;

Examples and instructions should cover all relevant cases of the pattern. In the examples above, this would include INSERT, UPDATE, DELETE, SELECT, and store procedure calls.

Once these patterns have been defined and accepted, the lead developer should communicate them to the rest of the team and train members in how to apply it successfully.

In general, architecture and configuration patterns will be far more efficient and effective than coding patterns.  If the architecture and configuration of the application is secure by default or forces developers to adhere to coding conventions that are secure by default, then fewer mistakes will be made and less time will be spent writing secure code.  As a general recommendation, try to satisfy security requirements by choosing secure designs, frameworks, libraries, services, or configurations.  If those options aren’t available, then define specific coding patterns for the team to implement.  If coding patterns will be written many times, consider writing a reusable module to implement the pattern.

The Cost of Writing Secure Patterns
I want to briefly discuss the cost associate with this approach. The implementation of secure architecture, configuration, and coding patterns is the most expensive SSDP element. This cost is significantly greater than the cost of developing the original security requirements. Security requirements are practices that can be defined once and apply to all projects in the organization; whereas, patterns must be defined for each group of projects that use similar technologies. In order to write security requirements, an individual with a security background is necessary; however, secure patterns may require a developer with a deeper understanding of security in order to select optimal solutions to satisfy requirements. Ideally, this upfront cost greatly reduces the ongoing cost when writing secure code.

In some cases, an organization may not have the expertise necessary to create security requirements or secure patterns.  In these cases, teams can use outside resources such as The Open Web Application Security Project (OWASP) or an application security specific consulting organization to kick start the process.

Benefits of Writing Secure Patterns
The primary benefit of defining secure architecture, configuration, and coding patterns is that every team member is equipped to satisfy security requirements without needing a deep application security background.  There’s no question about how to prevent SQL injection or cross-site scripting; in fact, specific vulnerabilities may not even have to be mentioned.  Instead, developers have a list of “answers” or a guide that describes how the team has chosen to architect and develop their application.  This guide naturally causes the team to write code free from vulnerabilities that the organization has selected against while writing security requirements. Additionally, the development team can reference these patterns throughout the life of the application rather than relearning or researching how to avoid or remediate vulnerabilities. To be clear, education is important, but this approach helps reduce the burden on developers to recall information from classes to implement secure code.

By repeating one unified pattern across the entire application, secure patterns also become easy to test and verify.  If one pattern is used throughout an entire application, than one set of test cases can be applied to validate those practices (these test cases are discussed in the next article).  In some cases, it may be possible to certify that an application is free of a particular vulnerability.

Secure Architecture, Configuration, and Coding Patterns Wrap-up
Language and framework specific secure architecture, configuration, and coding patterns equip development teams to satisfy security requirements for their project.  This unified approach to preventing application security vulnerabilities can be verified through test cases customized for each pattern.  These test cases and verification criteria are the topic of the next article.

New Burp Suite (>= 1.5.01) Extensibility and an Example Editor Tab Plugin

Burp Suite has a new extensibility API! In December, I wrote a plugin that uses the new API to speed up a security assessment of a Silverlight application using WCF web services. The code and explanation below helps demonstrate some of the new features in Burp.

The Silverlight application interface communicated with a SOAP based web service; however, the web service responses weren’t ordinary XML.  Instead, they contained a Base 64 encoded value.  After digging into the application, we discovered that the web services zipped and then Base 64 encoded XML response data.  

Initially, I wrote a python script to decode and unzip the data; however, it was time consuming to copy, paste, and unzip each response over and over again.  My solution was to use the new API to add an Editor Tab to Burp.  This editor tab automatically detects whether the HTTP response needed to be processed and then unzipped the value right in the proxy tool.  The plugin source code and several screenshots are available below.  The code may not be the most elegant solution, but it met my needs for being fast to develop and functional.

As I wrote the plugin, I noticed that Burp provides a useful stack trace if an exception occurs while loading the plugin; however, once the plugin is fully loaded, stack traces only show obfuscated class names for Burp.  You can work around this challenge by mocking up any data needed, writing all code that doesn’t rely on the Burp API separately, and then run it with the Jython interpreter.  When integrating it as a plugin, my approach was to use a lot of println statements. I had a general idea of how to use the framework, but I still needed to work out the details.

HTTP SOAP Request:

Base 64 Encoded SOAP Response:

Base 64 Decoded, Unzipped XML Content:

The plugin code is available as a gist at:

Non-Negotiable Elements of a Secure Software Development Process: Part 1 - Security Requirements

In September, I gave a presentation focused on helping quality assurance professionals understand how they fit into a secure software development process (SSDP) and how they can take an active role in improving software security.  In that presentation, I discussed essential elements that make up a successful SSDP.  These elements are: security requirements (expectations); secure architecture, configuration, and coding patterns (how to satisfy an expectation); and validation criteria (verification that expectations have been met). These elements allow an organization to be transparent regarding its security goals and performance.  They also facilitate communication with customers, developers, managers, and other project stakeholders.

This is part 1 in a series of articles discussing Non-Negotiable elements of a secure software development process. This article focuses on security requirements. All thr
ee articles are listed below:

Part 1: Security Requirements

Part 2: Secure Architecture, Configuration, and Coding Patterns

Part 3: Validation Criteria

What are Security Requirements?
Security requirements are intended to be language and framework agnostic statements that communicate the organization’s expectation around a security practice.  Security requirements are applicable for any project or team regardless of whether they are using ASP.NET MVC, J2EE with Spring MVC, or Ruby on Rails.  They use positive statements to describe the type of behavior desired, and use negative statements to provide additional clarity.  The ideal is to whitelist specific approaches to developing software.

An example security requirement intended to prevent SQL injection that meets this criteria might be:

“Applications that use an SQL database must use parameterized queries or prepared statements for all transactions, including SELECT, INSERT, UPDATE, DELETE, and stored procedure calls. Define the SQL query and use placeholders to denote the location in which parameter values will be added later. Then, add each value to the statement as a parameter. All variables must be added as parameters rather than being concatenated with the SQL query.”

This requirement is clear and understandable, it is easy to validate (more on this later), and it leaves the implementation up to the team.  Developers can choose to write dynamic queries that use prepared statements or they can use a framework, like Hibernate or LINQ to SQL that also follow this practice but abstracts the actual queries.

An example of a well intentioned but unsuccessful security requirement that also seeks to address SQL injection is:

“Write queries that do not allow untrusted user input to be interpreted by the database as SQL commands to prevent SQL injection.”

While this example is probably too simplistic, the reality is that most organization start with requirements that are just as ill-defined. The typical starting point is to focus on writing requirements that state what not to do instead of identifying the positive practice that will eliminate the vulnerability.  Ill-defined requirements like this one do not equip the development team with the means to succeed at meeting security expectations.

Benefits of Defining Security Requirements
Developers, customers, managers, and the organization at large benefit from security requirements in several ways.  First, security requirements can be discussed during the project planning stages with stakeholders.  Teams can decide how expensive it might be to satisfy a specific requirement and build that time into the software development process.  If these security requirements are linked with real business related consequences, customers or stakeholders can decide how much to spend on securing the application based on their budget, the sensitivity of data, or how critical the application is to the business.  

Developers benefit by having well defined requirements, clear expectations, and timelines that account for the implementation of agreed upon security components.  The team should also be able to articulate which types of threats the application is designed to repel as well as those that it is not, making security much more transparent.

Organizations benefit by being able to define collections of security requirements as assurance standards.  These collections of security requirements can be designed to satisfy PCI requirements, contractual obligations, or minimum security baselines.  Next, the assessors or evaluators of these standards can quickly and cheaply identify how an application meets the requirements.  In addition, organizations can leverage the security story of a specific application for marketing purposes or as a competitive advantage.

Security Requirements Wrap-up
Ideally organizations should define realistic, understandable, and measurable security requirements. By explicitly stating these requirements and using positive statements to define achievable development practices, the team is able to plan for, communicate, and meet the organization's security goals.  These software language and framework agnostic requirements naturally give way to specific implementation details for each project in the form of secure architecture, configuration coding patterns.  These patterns will be discussed in part 2.