Wednesday, August 22, 2012

Beating down hash functions

The state of the art in GPU- and statistics-enhanced password cracking. Crackers beating down information entropy just like in the old days at Bletchley Park! (Trivia question: what are "bans" and "cribs"? Answers)
Ars technica: ... 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."


Christopher Chang said...

A major cause of today's problems is the 8 character "standard" password length, inherited from the days when it was typical for computer systems to use hash algorithms that discarded characters after the 8th. Keeping in mind that there are rarely more than ~96 likely possibilities per character (ASCII 32-126, plus early termination), we're really talking about less than 2^53 possibilities. This is within brute-forcing range today, "strong password" punctuation/capitalization requirements be damned.

I don't see any alternative to widespread adoption of much longer passwords, I'd say 16 characters absolute minimum. (Well, maybe 17 characters, to discourage people from combining two passwords already sitting in hackers' dictionaries...)

David Coughlin said...

They have moved to requiring us to have a minimum of 14 characters at work, on 45-day must change cycle. I used to be able to remember my last two or three passwords, but now all I can really remember is the one I have right now. That said, my passwords are creeping into the low 20s for character counts, and they have fortunately cut the number of places that I actually have to enter it. That 10 seconds of lost time is more painful that a lot of 5-minutes of lost time.

Christopher Chang said...

My instinct is that forced frequent password changes are generally not worth the grief they cause, but that depends on how prominent a target your organization is; maybe I don't want to know how many times such policies have thwarted or discouraged keylogger attacks and the like.

RKU1 said...

Given the exponential price/performance in micro cameras, isn't this all just a very temporary issue until thumb prints take over, via some sort of tiny attachment? With a sensor to detect it's a real thumb rather than a photo of one?

Gabriel_Betteredge said...

Steve!!!!!! Are you as outraged as I am that Jones forced the cancellation of UFC 151? No doubt about it now: Jones is no kind of champion. And Greg Jackson is an absolute disgrace; his uber-conservative gameplans (e.g. Condit, Guida) are destroying MMA like a cancer. Machida is also to blame for not taking the fight.

Blog Archive