11 million Ashley Madison passwords cracked in 10 days

Regular readers know we like silver linings here at Naked Security.

We even managed to find one amongst the detritus of the recent Ashley Madison data breach.

→ If you missed that breach: a hacking crew calling itself Impact Team got into the back-end of an online “adultery dating” service called Ashley Madison and then dumped a massive stash of user data. That included enough to identify (as well as to misidentify) tens of millions of married people who were apparently interested in meeting up for casual sex with their non-spouse.

The silver lining amongst nearly 40,000,000 leaked Ashley Madison records was that the company had at least stored its users’ passwords safely.

The company used a salt-hash-and-stretch password storage system called bcrypt.

Bcrypt generates a random string of characters (the salt) and mixes it with your password; scrambles the password cryptographically (the hash); and does so over and over again (the stretch).

So, when someone presents a password, by resalting-rehashing-and-restretching it, you can see whether it’s the same as the one they set up originally, without ever storing the actual password.

Better yet, because the mathematics of cryptographic hashing prevents you working backwards to the passwords, the only way to crack the stored representations of the passwords is by trying a giant list of likely passwords one-by-one.

Even better, because of the random salt used to “flavour” each stored password value, you have to guess at each password individually, even if two users picked exactly the same password.

Best of all, the stretching means that you need to do quite a lot of work, computationally speaking, to try out each guess.

Not so much work that checking one password at login time takes minutes, or even seconds…

…but enough computational work that a crook can’t try billions, or even millions, of passwords a second.

Defence in depth

Note that salting-hashing-and-stretching your users’ passwords doesn’t mean you no longer need to keep the stored password values securely.

You aren’t supposed to lose customer data in the first place, but so-called key derivation functions like bcrypt (other well-known ones are scrypt and PBKDF2) act as a second layer of defence to reduce the impact of a breach if crooks do get in.

After all, if it takes a crook a whole month to crack your bcrypted password, then as long as you change your password within that month, you win the battle.

(Unless you used the same password on another site, so DON’T DO THAT.)

So far, so good

So, we said, “Good for Ashley Madison.”

But it sounds as though Ashley Madison’s silver lining may have been just a layer of electroplate.

A group going by CynoSure Prime noticed that not all of the passwords in the dump had actually been through the bcrypt salt-hash-and-stretch process.

Some of the stored password values were computed using just a single iteration of the MD5 hashing algorithm.

By modern standards, a simple MD5 calculation is way, way too quick for password safety.

Bcrypt uses a much slower cryptographic hash than MD5, and, in Ashley Madison’s implementation, repeated the effort 4096 (2¹²) times.

That made each guess tens or hundreds of thousands of times slower, so what might take a day of MD5 cracking would take decades of work for bcrypt.

A blogger who went after the the bcrypt hashes recovered only 4000 passwords in a week.

In contrast, CynoSure Prime recovered the passwords for over 11 million of the MD5 hashes in about 10 days.

The bottom line

The lesson to learn from this?

A cryptographic job worth doing is worth doing well.

If you decide to adopt an improved cryptographic process because the old one is no longer adequate, you really do need to get rid of the old process.

We know this already.

Consider, for example, the recent FREAK and LOGJAM vulnerabilities in TLS/SSL.

FREAK and LOGJAM were caused by programmers retaining support – 15 years after it was no longer needed – for what’s known as EXPORT_GRADE encryption, which was deliberately designed to be crackable back in the 1990s!

This is another solid reminder that cryptographic attacks only ever get faster.

Keep that in mind!

(You did change your Ashley Madison password already, right?)