Wednesday, August 26, 2015

Lessons learned from cracking 4,000 Ashley Madison passwords.

When hackers released password data for more than 36 million Ashley Madison accounts last week, big-league cracking expert Jeremi Gosney didn't bother running them through one of his massive computer clusters built for the sole purpose of password cracking. The reason: the passwords were protected by bcrypt, a cryptographic hashing algorithm so strong Gosney estimated it would take years using a highly specialized computer cluster just to check the dump for the top 10,000 most commonly used passwords.
So fellow security expert Dean Pierce stepped in to fill the vacuum, and his experience confirms Gosney's assessment. The long-and-short of his project is that after five days of nonstop automated guessing using a moderately fast server specifically designed to carry out compute-intensive cryptographic operations, he deciphered just 4,000 of the underlying plaintext passwords. Not surprisingly, the passwords Pierce extracted from just the first 6 million entries in the Ashley Madison table look as weak as those from just about any data breach. Here are the top 20 and number of users who chose each one:
Most of the lessons gleaned from Pierce's exercise involve the secure storage of passwords at rest. We'll get to that in a moment. But first, a few observations about the top 20 passwords uncovered. First, they come from the beginning six million hashes stored in the Ashley Madison database. Depending on how the list was organized, that may mean they belong to the earliest six million accounts created during the site's 14 years in operation. Passwords from the last million entries—which might have been created in the last few years—could be stronger.
Another important point: for a word list, Pierce used passwords taken from the seminal 2009 hack of gaming website RockYou, which leaked 32 million plaintext passcodes, 14.3 million of which were unique. While the list is comprehensive, cracking experts often combine larger and much more specialized lists with programming rules that vastly expand the lists' reach by, say, replacing the letter "a" with the "@" character. Had Pierce used one of these more sophisticated cracking methods, the top-20 list almost certainly would have looked different.

Exercise in adversity

Here's more detail on how Pierce did it, and it further underscores the effort required to crack such a tiny percentage of the dump. After downloading the 10-gigabyte compressed file Ashley Madison hackers released last week, he extracted the hashed passwords from one of the MySQL files and was left with a 2.1GB file with a staggering 36 million lines, each one consisting of a cryptographically protected password. He then moved the file to a server running fourAMD Radeon R9 290 graphics cards and the PiMP software for mining Bitcoins and other types of crypto currency. To tweak the super-fast machine, he also installed the latest version of oclHashcat, which automates many password-cracking tasks on GPUs.
To his surprise and annoyance, his computer returned an "insufficient memory available" message and refused to continue. The error was most likely the result of his cracking rig having only a single gigabyte of computer memory. To work around the error, Pierce ultimately picked the first six million hashes in the list. After five days, he was able to crack only 4,007 of the weakest passwords, which comes to just 0.000668 percent of the six million passwords in his pool.
As a quick reminder, security professionals around the world are in almost unanimous agreement that passwords should never be stored in plaintext. Instead, they should be converted into a long series of letters and numbers, called hashes, using a one-way cryptographic function. These algorithms should generate a unique hash for each unique plaintext input, and once they're generated, it should be impossible to mathematically convert them back. The idea of hashing is similar to the benefit of fire insurance for homes and buildings. It's not a substitute for safe practices, but it can prove invaluable when things go wrong.

As Ars has chronicled over the years, passwords have never been weaker and crackers have never been stronger, even when passwords are hashed following industry standard practices and end users choose long, random-appearing passcodes or passphrases with dozens or even hundreds of characters. In short, crackers guess surprising numbers of passwords by exploiting the predictability in the way most end users choose passwords and by using GPU-based computers that in some cases can make billions of guesses per second until the right one is made.
One of the ways engineers have responded to this password arms race is by embracing a function known as bcrypt, which by design consumes vast amounts of computing power and memory when converting plaintext messages into hashes. The bcrypt used by Ashley Madison puts each password through 4,096 rounds of a hashing algorithm based on Blowfish, a cipher known to be extremely slow and memory-intensive. What's more, bcrypt automatically appends unique data known as cryptographic salt to each plaintext password.
"One of the biggest reasons we recommend bcrypt is that it is resistant to acceleration due to its small-but-frequent pseudorandom memory access patterns," Gosney told Ars. "Typically we're used to seeing algorithms run over 100 times faster on GPU vs CPU, but bcrypt is typically the same speed or slower on GPU vs CPU."
As a result of all this, bcrypt is putting Herculean demands on anyone trying to crack the Ashley Madison dump for at least two reasons. First, 4,096 hashing iterations require huge amounts of computing power. In Pierce's case, bcrypt limited the speed of his four-GPU cracking rig to a paltry 156 guesses per second. Second, because bcrypt hashes are salted, his rig must guess the plaintext of each hash one at a time, rather than all in unison.
"Yes, that's right, 156 hashes per second," Pierce wrote. "To someone who's used to cracking MD5 passwords, this looks pretty disappointing, but it's bcrypt, so I'll take what I can get."

It’s about time

Pierce gave up once he passed the 4,000 mark. To run all six million hashes in Pierce's limited pool against the RockYou passwords would have required a whopping 19,493 years, he estimated. With a total 36 million hashed passwords in the Ashley Madison dump, it would have taken 116,958 years to complete the job. Even with a highly specialized password-cracking cluster sold by Sagitta HPC, the company founded by Gosney, the outcome would improve but not enough to justify the investment in electricity, equipment, and engineering time.
Unlike the extremely slow and computationally demanding bcrypt, MD5, SHA1, and a raft of other hashing algorithms were designed to place a minimum of strain on light-weight hardware. That's good for manufacturers of routers, say, and it's even better for crackers. Had Ashley Madison used MD5, for instance, Pierce's server could have completed 11 million guesses per second, a speed that would have allowed him to test all 36 million password hashes in 3.7 years if they were salted and just three seconds if they were unsalted (many sites still do not salt hashes). Had the dating site for cheaters used SHA1, Pierce's server could have performed seven million guesses per second, a rate that would have taken almost six years to go through the entire list with salt and five seconds without. (The time estimates are based on use of the RockYou list. The time required would be different if different lists or cracking methods were used. And of course, super fast rigs like the ones Gosney builds would complete the jobs in a fraction of these times.)
The key lesson from the exercise is that the one-way cryptographic functions play a crucial role in protecting passwords. And while there's no substitute for a layered security approach that prevents breaches in the first place, a hashing algorithm such as bcrypt or PBKDF2 makes a world of difference when hacks do happen.
But Pierce's experiment also provides a cautionary tale to the large percentage of people who pick "p@$$w0rd", "1234567", and other weak passcodes to protect their valuable online assets. Bcrypt may drastically slow the time in which a large list can be cracked, but its benefit diminishes when crackers target a handful of hashes that, say, are all associated with a single e-mail domain such as or The value further deteriorates when those targeted users choose a weak password.
"With a dump this size, passwords will still pop out like crazy, because people always use weak passwords" Pierce told Ars. "Even with good hashing+salt, a poor (or non existent) password policy can put users at risk."

No comments :

Post a Comment