Password hashing and the Ashley Madison hack

The mainstream media is in a frenzy about the Ashley Madison hack, and with good reason. Aside from the shady social and moral motives that most people are criticising Avid Life Media (the site’s owners) about, the breach is a notable one in terms of what the attackers made off with.

Among the stolen data are emails, users’ pictures and troves of other highly sensitive and embarrassing content that the attackers dumped on the dark web. However, what’s certainly of interest, but which not many are talking about, is the fact that the adultery site was very good at protecting their users’ passwords from being easily cracked.

Given the heaps of sensitive data that the attackers were able to get hold of, users’ passwords may at first sound like a small piece of the overall puzzle. However, while it’s true that users’ passwords make up a relatively small percentage of the gigabytes of data, when paired with the usernames or email addresses, they open up scores of possibilities for attackers. Although in this day and age they probably should know better, users still share passwords between different services. So an attacker could try to use the same email address or username and password combination to log in to a user’s web mail account. If that works, it’s pretty much game over for the victim because an attacker can then take over the email account and start to reset passwords left right and centre.

So how should a web application protect a user’s password? The absolutely wrong way to do it is to store passwords in plain text; that way an attacker can simply access those passwords with no effort whatsoever if the database gets compromised. The right way to do it is to run a user’s password through a one-way cryptographic hashing function that produces a hash (also referred to as a digest).

A one-way cryptographic hash function accepts a plaintext of arbitrary length and produces a fixed-length digest that cannot be reversed, whilst retaining integrity and consistency in the hashing process, meaning that hashing the same data must consistently provide the same output.

This makes hashes ideal for storing passwords since the moment a user supplies a password, it is hashed into a unique and consistent value that cannot be reversed. A hash can be stored in a database without the application needing to know the actual password the user created.

password hashing

The only way an attacker can crack a password (assuming that there are no weaknesses with the hashing function that was chosen) is to hash the plaintext and compare the result to the hashed password in the database.

The above however may still present a problem for users who have the same password – that is, if two distinct users pick the same password, the hash is going to be the same for those two users, therefore an attacker has one less password to crack. To make matters worse, an attacker can rely on what are known as rainbow tables to achieve a time-memory trade-off attack by pre-computing a table for reversing cryptographic hash functions used for cracking password hashes.

In order to prevent time-memory trade-off attacks, a salt needs to be used. A salt is a random string that is unique to each user. The salt is concatenated to the plaintext of a password before it has been hashed. The salt is therefore hashed together with the password provided by the user. A salt has two advantages – it does not allow an attacker to use pre-computed attacks such as rainbow tables or lookup tables and it also adds more entropy to a password – that is it increases the randomness of a password a user supplies.

While a salt does not prevent a determined attacker for cracking a password, it makes it much harder. Another thing to note is that it is not important that the salt is kept secret (in fact, most of the time it’s stored alongside the password), however, for a salt to be effective it must be unique and random.

So salted password hashes make an attacker’s task much more difficult, but attackers have other unlikely tools at their disposal for cracking large amounts of salted password hashes – Graphical Processing Units (GPUs).

It may seem strange, but GPUs are better suited for password cracking than CPUs since they make use of several hundreds, or thousands of cores

While significantly slower than a core of a modern CPU, a GPU core is able to perform mathematical computations independently from other cores, therefore having an architecture that is better suited towards parallel processing than a CPU.

So given that attackers will be making use of GPUs (or even faster hardware such as FPGAs and ASICS to crack salted passwords, a hash that is designed to be fast is counter productive for storing passwords because an attacker would be able to generate a larger number of hashes in a shorter time window.

Since one-way cryptographic hash functions are used in fields other than password storage, for example, file integrity and digital signatures, it is essential to make use of the appropriate cryptographic hash function based on its target use.

In applications such as file integrity and digital signatures, a fast cryptographic hash function is preferred. This speed becomes especially important in a scenario involving network protocols and other such delay sensitive applications. However, when choosing a hashing function for use with passwords, you’d want to choose a computationally expensive hash, simply because it will drive-up the cost of trying to crack that given password hash.

Examples of widely used fast cryptographic hash functions include MD5 and SHA-1. On the other hand, examples of slow cryptographic hash functions designed for password storage include PBKDF2, bcrypt and scrypt.

In 2012, LinkedIn suffered a security breach resulting in nearly 6.5 million user accounts and their un-salted SHA1 passwords stolen. The attackers who stole the passwords managed to crack the majority of these passwords in under a day.

Passwords stored in the Ashley Madison databases that got leaked, on the other hand are hashed using bcrypt (bcrypt enforces the use of a salt).

Hashing functions such as bcrypt and scrypt, are designed to be computationally expensive and memory intensive, rendering GPU cracking inefficient since each GPU core has relatively little memory available to it. bcrypt achieves this by running the plaintext through multiple iterations of the the Blowfish cipher. The bcrypt setup that Ashley Madison was using, set password hashes to have a cost of 12 — therefore putting each password through 212 (4,096) rounds of the Blowfish cipher in addition to a salt.

The lesson to take away here is that the choice of one-way cryptographic hashing functions is crucial in ensuring passwords cannot be cracked without considerable effort and resources. While the Ashley Madison hack was disastrous for the company and its users, it might have turned out to be catastrophic had they used a less-suitable hashing function.

Share this post
  • Erratum:
    “…therefore putting each password through 212 (4,096) rounds of the Blowfish cipher in addition to a salt.”
    “…through 2^12 (4,096)” and not “…through 212 (4,096) ”
    The “cost” of the Bcrypt Blowfish 32/64 X2 used by AM is 2^12 >> $12
    $2a$12$9c [edited] ZpbdzOMS

    Very well written article, clear and concise.
    Thank you

  • “it might have turned out to be catastrophic had they used a less-suitable hashing function.”
    -Agreed. They did a good job on protecting (some) of their data.
    The issue is the end user. Using “password” as a password is very risky: Even Bcrypt will not protect you for a long time.
    It’s basically going back to the old bear story: You don’t need to run faster than the bear, you just need to run faster than the slowest guys.
    Websites should have policies in place that forbids users using such weak and well know password. It makes them sitting ducks.

    • Yes, of course, that will always remain true. Even against, a bcrypt hash, dictionary-guessable passwords don’t stand much of a chance. This being said, hashes such as bcrypt make key exhaustion attacks (bruteforce attacks) and substitution attacks (for example a Leet version of a word like ‘p455w0rd’) impractical.

  • Leave a Reply

    Your email address will not be published.