Passwords – Why passwords have never been weaker—and crackers have never been stronger
Password Cracking – what hackers know about your habits
The ancient art of password cracking has advanced further in the past five years than it did in the previous several decades combined. At the same time, the dangerous practice of password reuse has surged. The result: security provided by the average password in 2012 has never been weaker.
6.5 passwords per user
The average Web user maintains 25 separate accounts but uses just 6.5 passwords to protect them, according to a landmark study (PDF) from 2007. As the Gawker breach demonstrated, such password reuse, combined with the frequent use of e-mail addresses as user names, means that once hackers have plucked login credentials from one site, they often have the means to compromise dozens of other accounts, too.
8.2 billion passwords per second
Newer hardware and modern techniques have also helped to contribute to the rise in password cracking. Now used increasingly for computing, graphics processors allow password-cracking programs to work thousands of times faster than they did just a decade ago on similarly priced PCs that used traditional CPUs alone. A PC running a single AMD Radeon HD7970 GPU, for instance, can try on average an astounding 8.2 billion password combinations each second, depending on the algorithm used to scramble them. Only a decade ago, such speeds were possible only when using pricey supercomputers.
The advances don’t stop there. PCs equipped with two or more $500 GPUs can achieve speeds two, three, or more times faster, and free password cracking programs such as oclHashcat-plus will run on many of them with little or no tinkering. Hackers running such gear also work in tandem in online forums, which allow them to pool resources and know-how to crack lists of 100,000 or more passwords in just hours.
Most importantly, a series of leaks over the past few years containing more than 100 million real-world passwords have provided crackers with important new insights about how people in different walks of life choose passwords on different sites or in different settings. The ever-growing list of leaked passwords allows programmers to write rules that make cracking algorithms faster and more accurate; password attacks have become cut-and-paste exercises that even script kiddies can perform with ease.
At any given time, Redman is likely to be running thousands of cryptographically hashed passwords though a PC containing four of Nvidia’s GeForce GTX 480 graphics cards. It’s an “older machine,” he conceded, but it still gives him the ability to cycle through as many as 6.2 billion combinations every second. He typically uses a dictionary file containing about 26 million words, combined with programming rules that greatly extend its effectiveness by adding numbers, punctuation, and other characters to each list entry. Depending on the job, he sometimes uses a 60 million-strong word list and something known as “rainbow tables,” which are described later in this article.
As a penetration tester who gets paid to pierce the defenses of Fortune 500 companies, Redman tries to spot weaknesses before criminal hackers exploit them on his customers’ networks. One of the key ways he stays ahead is by downloading hash lists that are dumped almost every day on pastebin.com and other sites to see if any belong to the organizations he is contracted to protect.
Recently, he recovered a 13-character password that he had spent several months trying to crack. To protect the account holder, he declined to reveal the precise combination of characters and instead made up the imaginary passphrase “Sup3rThinkers” (minus the quotation marks) to illustrate his breakthrough. “Sup3rThinkers” follows a number of patterns that have become common: it opens with a common, five-letter word that begins with a capitalized letter and substitutes a 3 for an E, followed by a common, seven-letter word that also begins with a capital letter. While the speed of his system didn’t hurt, cracking the password was largely the result of the collective codebreaking expertise developed online over the past few years.
The most important single contribution to cracking knowledge came in late 2009, when an SQL injection attack against online games service RockYou.com exposed 32 million plaintext passwords used by its members to log in to their accounts. The passcodes, which came to 14.3 million once duplicates were removed, were posted online; almost overnight, the unprecedented corpus of real-world credentials changed the way whitehat and blackhat hackers alike cracked passwords.
The RockYou dump was a watershed moment, but it turned out to be only the start of what’s become a much larger cracking phenomenon. By putting 14 million of the most common passwords into the public domain, it allowed people attacking cryptographically protected password leaks to almost instantaneously crack the weakest passwords. That made it possible to devote more resources to cracking the stronger ones.
Within days of the Gawker breach, for instance, a large percentage of the password hashes had been converted to plaintext, a feat that gave crackers an even larger corpus of real-world passwords to inform future attacks. That collective body of passwords has only snowballed since then, and it grows ever larger with each passing breach. Just six days after the leak of 6.5 million LinkedIn password hashes in June, more than 90 percent of them were cracked. In the past year alone, Redman said, more than 100 million passwords have been published online, either in plaintext or in ciphertext that can be readily cracked.
Almost as important as the precise words used to access millions of online accounts, the RockYou breach revealed the strategic thinking people often employed when they chose a passcode. For most people, the goal was to make the password both easy to remember and hard for others to guess. Not surprisingly, the RockYou list confirmed that nearly all capital letters come at the beginning of a password; almost all numbers and punctuation show up at the end. It also revealed a strong tendency to use first names followed by years, such as Julia1984 or Christopher1965.
“Sup3rThinkers” wasn’t included in the list of RockYou passwords, making it part of the 40 percent of hashes that require Redman to apply cracking techniques that go beyond a simple word-list attack. Fortunately for him, the RockYou corpus included both “sup3r” and “thinkers” as separate passwords. That allowed him to recover the password in question by appending each word in his list to every other word in the list. The technique is simple enough to do, although it increases the number of required guesses dramatically—from about 26 million, assuming the dictionary Redman uses most often, to about 676 trillion.
Other complex passwords require similar manipulations to be cracked. The RockYou list, and the hundred-millions-plus passwords that have collectively been exposed in its aftermath, brought to light a plethora of other techniques people employ to protect simple passcodes from traditional dictionary attacks. One is adding numbers or non-alphanumeric characters such as “!!!” to them, usually at the end, but sometimes at the beginning. Another, known as “mangling,” transforms words such as “super” or “princess” into “sup34” and “prince$$.” Still others append a mirror image of the chosen word, so “book” becomes “bookkoob” and “password” becomes “passworddrowssap.”
One promising technique is to use programs such as the open-source Passpal to reduce cracking time by identifying patterns exhibited in a statistically significant percentage of intercepted passwords. For example, as noted above, many website users have a propensity to append years to proper names, words, or other strings of text that contain a single capital letter at the beginning. Using brute-force techniques to crack the password Julia1984 would require 629possible combinations, a “keyspace” that’s calculated by the number of possible letters (52) plus the number of numbers (10) and raising the sum to the power of nine (which in this example is the maximum number of password characters a cracker is targeting). Using an AMD Radeon HD7970, it would still take about 19 days to cycle through all the possibilities.
Using features built into password-cracking apps such as Hashcat and Extreme GPU Bruteforcer, the same password can be recovered in about 90 seconds by performing what’s known as a mask attack. It works by intelligently reducing the keyspace to only those guesses likely to match a given pattern. Rather than trying aaaaa0000, ZZZZZ9999, and every possible combination in between, it tries a lower- or upper-case letter only for the first character, and tries only lower-case characters for the next four characters. It then appends all possible four-digit numbers to the end. The result is a drastically reduced keyspace of about 237.6 billion, or 52 * 26 * 26 * 26 * 26 * 10 * 10 * 10 * 10.
An even more powerful technique is a hybrid attack. It combines a word list, like the one used by Redman, with rules to greatly expand the number of passwords those lists can crack. Rather than brute-forcing the five letters in Julia1984, hackers simply compile a list of first names for every single Facebook user and add them to a medium-sized dictionary of, say, 100 million words. While the attack requires more combinations than the mask attack above—specifically about 1 trillion (100 million * 104) possible strings—it’s still a manageable number that takes only about two minutes using the same AMD 7970 card. The payoff, however, is more than worth the additional effort, since it will quickly crack Christopher2000, thomas1964, and scores of others.
“The hybrid is my favorite attack,” said Atom, the pseudonymous developer of Hashcat, whose team won this year’s Crack Me if You Can contest at Defcon. “It’s the most efficient. If I get a new hash list, let’s say 500,000 hashes, I can crack 50 percent just with hybrid.”
With half the passwords in a given breach recovered, cracking experts like Atom can use Passpal and other programs to isolate patterns that are unique to the website from which they came. They then write new rules to crack the remaining unknown passwords. More often than not, however, no amount of sophistication and high-end hardware is enough to quickly crack some hashes exposed in a server breach. To ensure they keep up with changing password choices, crackers will regularly brute-force crack some percentage of the unknown passwords, even when they contain as many as nine or more characters.
“It’s very expensive, but you do it to improve your model and keep up with passwords people are choosing,” said Moxie Marlinspike, another cracking expert. “Then, given that knowledge, you can go back and build rules and word lists to effectively crack lists without having to brute force all of them. When you feed your successes back into your process, you just keep learning more and more and more and it does snowball.”