Programming errors make 15.26 million accounts orders of magnitude faster to crack.
When the Ashley Madison hackers leaked close to 100 gigabytes worth of sensitive documents belonging to the online dating service for people cheating on their romantic partners, there seemed to be one saving grace. User passwords were cryptographically protected using bcrypt, an algorithm so slow and computationally demanding it would literally take centuries to crack all 36 million of them
Now, a crew of hobbyist crackers has uncovered programming errors that make more than 15 million of the Ashley Madison account passcodes orders of magnitude faster to crack. The blunders are so monumental that the researchers have already deciphered more than 11 million of the passwords in the past 10 days. In the next week, they hope to tackle most of the remaining 4 million improperly secured account passcodes, although they cautioned they may fall short of that goal. The breakthrough underscores how a single misstep can undermine an otherwise flawless execution. Data that was designed to require decades or at least years to crack was instead recovered in a matter of a week or two.
The cracking team, which goes by the name “CynoSure Prime,” identified the weakness after reviewing thousands of lines of code leaked along with the hashed passwords, executive e-mails, and other Ashley Madison data. The source code led to an astounding discovery: included in the same database of formidable bcrypt hashes was a subset of 15.26 million passwords obscured usingMD5, a hashing algorithm that was designed for speed and efficiency rather than slowing down crackers.
The bcrypt configuration used by Ashley Madison was set to a “cost” of 12, meaning it put each password through 212, or 4,096, rounds of an extremely taxing hash function. If the setting was a nearly impenetrable vault preventing the wholesale leak of passwords, the programming errors—which both involve a MD5-generated variable the programmers called $loginkey—were the equivalent of stashing the key in padlock-secured box in plain sight of that vault. At the time this post was being prepared, the blunders allowed CynoSure Prime members to positively crack more than 11.2 million of the susceptible passwords.
Enormous speed boosts
“Through the two insecure methods of $logkinkey generation observed in two different functions, we were able to gain enormous speed boosts in cracking the bcrypt hashed passwords,” the researchers wrote in a blog post published early Thursday morning. “Instead of cracking the slow bcrypt$12$ hashes which is the hot topic at the moment, we took a more efficient approach and simply attacked the MD5 … tokens instead.”
It’s not entirely clear what the tokens were used for. CynoSure Prime members suspect they served as some sort of means for users to log in without having to enter passwords each time. In any event, the 15.26 million insecure token contain one of two errors, both involving passing the plaintext account password through MD5. The first insecure method was the result of converting the user name and password to lower case, combining them in a string that has two colons in between each field, and finally, MD5 hashing the result.
Cracking each token requires only that the cracking software supply the corresponding user name found in the password database, adding the two colons, and then making a password guess. Because the MD5 is so fast, the crackers could try billions of these guesses per second. Their task was also aided by the fact that the Ashley Madison programmers had converted the letters of each plaintext password to lower case before hashing them, a function that reduced the “keyspace” and with it the number of guesses needed to find each password. When the input generates the same MD5 hash found in the token, the crackers know they have recovered the guts of the password protecting that account. All that’s potentially required then is to case correct the recovered password. Sadly, this step generally wasn’t required because an estimated nine out of 10 passwords contained no uppercase letters to begin with.
In the 10 percent of cases where the recovered password doesn’t match the bcrypt hash, CynoSure Prime members run case-modified changes to the recovered password. For instance, assuming the recovered password was “tworocks1” and it doesn’t match the corresponding bcrypt hash, the crackers will try “Tworocks1”, “tWorocks1”, “TWorocks1”, and so on until the case-modified guess generates the same bcrypt hash found in the leaked Ashley Madison database. Even with the extreme demands of bcrypt, the case-correction is relatively fast. With just eight letters (and one number, which obviously can’t be modified) in the example above, that comes to 82, or 256, iterations.
The following table shows the process for generating a token for a fictitious account that has the user name “CynoSure” and the password “Prime”. The same table shows how CynoSure Prime members would then go about cracking it and how Ashley Madison programmers could have avoided the weakness.
Insecure method No. 2 for generating the tokens is a variation on this same theme. It concatenates the lower-case user name, e-mail address, plaintext password and the supposedly secret string “73@^bhhs&#@&^@8@*$”. Once again it places two colons between each item and then MD5 hashes the combined string. Using the same fictitious Ashley Madison account, the process looks like this:
About a million times faster
Even with the added case-correction step, cracking the MD5 hashes is several orders of magnitude faster than cracking the bcrypt hashes used to obscure the same plaintext password. It’s hard to quantify precisely the speed boost, but one team member estimated it’s about one million times faster. The time savings adds up quickly. Since August 31, CynoSure Prime members have positively cracked 11,279,199 passwords, meaning they have verified they match their corresponding bcrypt hashes. They have 3,997,325 tokens left to crack. (For reasons that aren’t yet clear, 238,476 of the recovered passwords don’t match their bcrypt hash.)
The CynoSure Prime members are tackling the hashes using an impressive array of hardware that runs a variety of password-cracking software, including MDXfind, a password recovery tool that’s one of the fastest to run on a regular computer processor, as opposed to supercharged graphics cards often favored by crackers. MDXfind was particularly well suited to the task early on because it’s able to simultaneously work with many different combinations of hash functions and algorithms. That allowed it to crack both types of erroneously hashed Ashley Madison passwords.
The crackers also made liberal use of traditional GPU cracking, although that method was unable to efficiently crack hashes generated using the second programming error unless the software is tweaked to support that variant MD5 algorithm. GPU crackers turned out to be more suitable for cracking hashes generated by the first mistake because the crackers can manipulate the hashes in a way that the username becomes the cryptographic salt. As a result, the cracking experts can load them more efficiently.
To protect end users, the team members aren’t releasing the plaintext passwords. The team members are, however, disclosing all the details others need to replicate the passcode recovery.
A comedy tragedy of errors
The tragedy of the errors is that it was never necessary for the token hashes to be based on the plaintext password chosen by each account user. Since the bcrypt hash had already been generated, there was no reason it couldn’t be used instead of the plaintext password. That way, even if the MD5 hash in the tokens was cracked, the attackers would still be left with the unenviable job of cracking the resulting bcrypt hash. Indeed, many of the tokens appear to have later followed this formula, a finding that suggests the programmers were aware of their epic mistake.
“We can only guess at the reason the $loginkey value was not regenerated for all accounts,” a team member wrote in an e-mail to Ars. “The company did not want to take the chance of slowing down their site while the $loginkey value was updated for all 36+ million accounts.”
Source:https://arstechnica.com/
He is a well-known expert in mobile security and malware analysis. He studied Computer Science at NYU and started working as a cyber security analyst in 2003. He is actively working as an anti-malware expert. He also worked for security companies like Kaspersky Lab. His everyday job includes researching about new malware and cyber security incidents. Also he has deep level of knowledge in mobile security and mobile vulnerabilities.
