Nate Anderson Dan Goodin follows up on Nate Anderson's excellent piece on the nuts and bolts of password cracking with a further attempt to decrypt an encrypted password file leaked from LivingSocial, this time with the aid of experts. The password file they were working on was encrypted with the relatively weak (and now deprecated) SHA1 hashing algorithm, and they were only attacking it with a single GPU on a commodity PC, and were able to extract over 90% of the passwords in the file.
The discussion of the guesswork and refinement techniques used in extracting passwords is absolutely fascinating and really is a must-read. However, the whole exercise is still a bit inconclusive -- in the end, we know that a badly encrypted password file is vulnerable to an underpowered password-cracking device. But what we need to know is whether a well-encrypted password file will stand up to a good password-cracking system.
The specific type of hybrid attack that cracked that password is known as a combinator attack. It combines each word in a dictionary with every other word in the dictionary. Because these attacks are capable of generating a huge number of guesses—the square of the number of words in the dict—crackers often work with smaller word lists or simply terminate a run in progress once things start slowing down. Other times, they combine words from one big dictionary with words from a smaller one. Steube was able to crack "momof3g8kids" because he had "momof3g" in his 111 million dict and "8kids" in a smaller dict...
What was remarkable about all three cracking sessions were the types of plains that got revealed. They included passcodes such as "k1araj0hns0n," "Sh1a-labe0uf," "Apr!l221973," "Qbesancon321," "DG091101%," "@Yourmom69," "ilovetofunot," "windermere2313," "tmdmmj17," and "BandGeek2014." Also included in the list: "all of the lights" (yes, spaces are allowed on many sites), "i hate hackers," "allineedislove," "ilovemySister31," "iloveyousomuch," "Philippians4:13," "Philippians4:6-7," and "qeadzcwrsfxv1331." "gonefishing1125" was another password Steube saw appear on his computer screen. Seconds after it was cracked, he noted, "You won't ever find it using brute force."
Ars Technica's Nate Anderson decided to try cracking passwords (from a leaked file of MD5 hashes), to see how difficult it was. After a very long false start (he forgot to decompress the word-list file) that's covered in a little too much detail, Anderson settles down to cracking hashes in earnest, and provides some good data on the nuts and bolts of password security:
By this point I had puzzled out how Hashcat worked, so I dumped the GUI and switched back to the command-line version running on my much faster MacBook Air. My goal was to figure out how many hashes I could crack in, say, under 30 minutes, as well as which attacks were most efficient. I began again on my 17,000-hash file, this time having Hashcat remove each hash from the file once it was cracked. This way I knew exactly how many hashes each attack solved.
This set of attacks brought the number of uncracked MD5 hashes down from 17,000 to 8,790, but clearly the best "bang for the buck" came from running the RockYou list with the best64.rule iterations. In just 90 seconds, this attack would uncover 45 percent of the hashed passwords; additional attacks did little more, even those that took 16 minutes to run.
Cracking a significant number of the remaining passwords would take some much more serious effort. Applying the complex d3ad0ne.rule file to the massive RockYou dictionary, for instance, would require more than two hours of fan-spinning number-crunching. And brute force attacks using 6-character passwords only picked up a few additional results.
The point, really, is that if you want to understand the relative security of different password-generation techniques, you need to understand what's involved in state-of-the-art password cracking techniques.
Security Ledger reports on a breakthrough in password-cracking, using 25 graphics cards in parallel to churn through astounding quantities of password possibilities in unheard-of timescales. It's the truly the end of the line for passwords protected by older hashing algorithms and illustrates neatly how yesterday's "password that would take millions of years to break" is this year's "password broken in an afternoon," and has profound implications for the sort of password hash-dumps we've seen in the past two years.
A presentation at the Passwords^12 Conference in Oslo, Norway (slides available here), has moved the goalposts, again. Speaking on Monday, researcher Jeremi Gosney (a.k.a epixoip) demonstrated a rig that leveraged the Open Computing Language (OpenCL) framework and a technology known as Virtual Open Cluster (VCL) to run the HashCat password cracking program across a cluster of five, 4U servers equipped with 25 AMD Radeon GPUs and communicating at 10 Gbps and 20 Gbps over Infiniband switched fabric.
Gosney’s system elevates password cracking to the next level, and effectively renders even the strongest passwords protected with weaker encryption algorithms, like Microsoft’s LM and NTLM, obsolete.
In a test, the researcher’s system was able to churn through 348 billion NTLM password hashes per second. That renders even the most secure password vulnerable to compute-intensive brute force and wordlist (or dictionary) attacks. A 14 character Windows XP password hashed using NTLM (NT Lan Manager), for example, would fall in just six minutes, said Per Thorsheim, organizer of the Passwords^12 Conference.
Paul Moreno, an Ecuadoran blogger, discovered a flaw in the country's national online identity database, which he demonstrated by hijacking the identity of President Rafael Correa. He was briefly arrested, but was released after a vociferous Twitter campaign that prompted action from the president, who personally ordered Moreno's release. Moreno triumphantly announced his victory on Twitter.
Citing a Wired story on password security, Moreno set out on Nov. 26 to demonstrate a security flaw in DatoSeguro with an attention-getting proof of concept scheme: accessing President Correa’s account. He began by doxing the president, and once equipped with Correa’s date of birth and a national identification number — obtained via online searches — he had two of the three pieces of information he needed. The third was a set of two numbers from an identity card, which he simply guessed. With that, he had access to Correa’s account. “Out of curiosity, I noticed one time that the fingertip digits in the IDS are all very similar,” he wrote on his blog. “There’s a V or an E or an A followed by various numbers: V23444 – E5444 and so on…combinations that are very simplistic, apparently. The system asked me for the third and fourth numbers of the fingertip digits. With the first combination, I got the numbers right and my account was created. After verifying the email the system sends, I had access to all Rafael Vicente Correa Delgado’s so-called secure data. It took me about half an hour, maybe less.”
Moxie Marlinspike and David Hulton's Divide and Conquer: Cracking MS-CHAPv2 with a 100% success rate presentation from Defcon is now a reality. If you want to crack a MS-CHAPv2 PPTP authentication handshake (like the one I use when I connect to IPREDator, the secure proxy I favor), they'll exhaust all of the DES keyspace for you for a mere $20, usually in less than a day.
Basically, MS-CHAPv2-based VPNs should now be considered insecure and not fit for purpose. Plus Moxie and David can brute force all of DES for $20. Yowza.
A Week Of Discounted Cracking
For this week (9/23/2012), we will be offering deeply discounted MS-CHAPv2 cracking jobs by reducing the price from $200 to $20. This means that any PPTP VPN connection or intercepted MS-CHAPv2 WPA Enterprise wireless credentials can be cracked and decrypted with a 100% success rate for only $20.
The one major caveat is that an influx of additional jobs might increase the pending queue depth and cause MS-CHAPv2 jobs to take slightly longer than ususal, but we'll see how it goes.
Dan Goodin's Ars piece on the state of password security is a must-read overview of the way that the password cracking landscape has changed in surprising ways. It's not just that computers have gotten faster -- it's the confluence of several factors, including: more sites that require passwords, which encourages password re-use; sites that use weak password hashing, unsalted hashing, or no hashing at all; and titanic dumps of real-world passwords that provide insight into how users choose their passwords. Put them all together and you get a situation like the LinkedIn dump, where 90 percent of the encrypted passwords were extracted in short order -- and where many of those passwords could be used to take over other user accounts, thanks to password re-use.
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.
"Now, it's like once a quarter you get another RockYou," Redman said.
In the RockYou aftermath, everything changed. Gone were word lists compiled from Webster's and other dictionaries that were then modified in hopes of mimicking the words people actually used to access their e-mail and other online services. In their place went a single collection of letters, numbers, and symbols—including everything from pet names to cartoon characters—that would seed future password attacks.
"So it's no longer this theoretical word list of Klingon planets and stuff like that," Redman said of the RockYou list. "It's literally 'dragon' and 'princess' and stuff like that, and [the list] may crack 60 percent of a newly compromised website. Now you have 60 percent of the work done and you haven't done any thinking at all. You've just used your previous knowledge."
I wrote a novella about where all this stuff ends up, called Knights of the Rainbow Table, for Intel's Tomorrow Project. I don't believe sf writers predict the future, but I sure feel like that one predicted the present.
A couple weeks ago, a few hundred Dropbox users noticed they were receiving loads of spam about online casinos and gambling websites, at email addresses those users had set up only for Dropbox-related actions. The online file storage service now admits that hackers snagged usernames and passwords from third party sites, and used this data to break into those Dropbox users' accounts. Dara Kerr, reporting for CNET:
"Our investigation found that usernames and passwords recently stolen from other websites were used to sign in to a small number of Dropbox accounts. We've contacted these users and have helped them protect their accounts," the company wrote in a blog post today. "A stolen password was also used to access an employee Dropbox account containing a project document with user email addresses. We believe this improper access is what led to the spam."
Over at Ars Technica, Jon Brodkin has more. Evidently, the illicit access happened because a Dropbox employee’s account was hacked.
Total entries = 442773
Total unique entries = 342478
Top 10 passwords
123456 = 1666 (0.38%)
password = 780 (0.18%)
welcome = 436 (0.1%)
ninja = 333 (0.08%)
abc123 = 250 (0.06%)
123456789 = 222 (0.05%)
12345678 = 208 (0.05%)
sunshine = 205 (0.05%)
princess = 202 (0.05%)
qwerty = 172 (0.04%)
Top 10 base words
password = 1373 (0.31%)
welcome = 534 (0.12%)
qwerty = 464 (0.1%)
monkey = 430 (0.1%)
jesus = 429 (0.1%)
love = 421 (0.1%)
money = 407 (0.09%)
freedom = 385 (0.09%)
ninja = 380 (0.09%)
writer = 367 (0.08%)
Password length (length ordered)
1 = 117 (0.03%)
2 = 70 (0.02%)
3 = 302 (0.07%)
4 = 2748 (0.62%)
5 = 5323 (1.2%)
6 = 79610 (17.98%)
7 = 65598 (14.82%)
8 = 119125 (26.9%)
9 = 65955 (14.9%)
10 = 54756 (12.37%)
11 = 21219 (4.79%)
12 = 21728 (4.91%)
In "Linguistic properties of multi-word passphrases" (PDF, generates an SSL error) Cambridge's Joseph Bonneau and Ekaterina Shutova demonstrate that multi-word passphrases are more secure (have more entropy) than average user passwords composed of "random" characters, but that neither is very secure. In a blog post, Joseph Bonneau sums up the paper and the research that went into it.
Some clear trends emerged—people strongly prefer phrases which are either a single modified noun (“operation room”) or a single modified verb (“send immediately”). These phrases are perhaps easier to remember than phrases which include a verb and a noun and are therefore closer to a complete sentence. Within these categories, users don’t stray too far from choosing two-word phrases the way they’re actually produced in natural language. That is, phrases like “young man” which come up often in speech are proportionately more likely to be chosen than rare phrases like “young table.”
This led us to ask, if in the worst case users chose multi-word passphrases with a distribution identical to English speech, how secure would this be? Using the large Google n-gram corpus we can answer this question for phrases of up to 5 words. The results are discouraging: by our metrics, even 5-word phrases would be highly insecure against offline attacks, with fewer than 30 bits of work compromising over half of users. The returns appear to rapidly diminish as more words are required. This has potentially serious implications for applications like PGP private keys, which are often encrypted using a passphrase. Users are clearly more random in “passphrase English” than in actual English, but unless it’s dramatically more random the underlying natural language simply isn’t random enough. Exploring this gap is an interesting avenue for future collaboration between computer security researchers and linguists. For now we can only be comfortable that randomly-generated passphrases (using tools like Diceware) will resist offline brute force.
SplashData, a company that makes password management tools, has released a roundup of 2011's "25 worst passwords," gleaned from password-dumps posted by "hackers" (presumably, sources like the Lulzsec Sony password files). I can't locate the actual study and its methodology (are these passwords "worst" because they're the most common, or because they contain the least entropy? Is the sample set representative?) but the list is still informative, and, of course, it can give a warm glow of superiority to those of us with stronger passwords.
1. password 2. 123456 3.12345678 4. qwerty 5. abc123 6. monkey 7. 1234567 8. letmein 9. trustno1 10. dragon 11. baseball 12. 111111 13. iloveyou 14. master 15. sunshine 16. ashley 17. bailey 18. passw0rd 19. shadow 20. 123123 21. 654321 22. superman 23. qazwsx 24. michael 25. football
Passwords have been a recurring theme this year, and it's becoming increasingly clear (to me, at least), that passwords may be reaching their end-of-life on the Internet.
Today's XKCD, "Password Strength," neatly illustrates the research from this paper (PDF) by Philip Inglesant and M. Angela Sasse from University College London, with the ironic conclusion that we've trained our users to use passwords that computers can easily guess and humans can't possibly remember.