Thursday, January 31, 2013

NYTimes and more Rainbow Table nonsense

Today's NYTimes article on how it got hacked is full of inaccurate information. Take, for example, this paragraph:

While hashes make hackers’ break-ins more difficult, hashed passwords can easily be cracked using so-called rainbow tables — readily available databases of hash values for nearly every alphanumeric character combination, up to a certain length. Some hacker Web sites publish as many as 50 billion hash values.
This is nonsense. 

Rainbow Tables are nearly useless in such cases. When I pentest corporations and dump the hashes from the domain controller, I don't use Rainbow Tables.

The reasons are simply that Rainbow Tables only handle short passwords and they only crack one password at a time.

Most corporations have password policies demanding at least 8 letters and complex passwords containing at least one upper case letter and a number or symbol. This means almost all Rainbow Tables are useless. Consider the list at There is only a single table that fits this requirement, the one labeled "ntlm_mixalpha-numeric#1-8_40000".

Using an old graphics processor (like the Radeon 6970) I can brute-force that level of password complexity in 14 hours. It doesn't matter if I have one hash I'm trying to crack, hundreds, or even thousands of hashes. I can crack them all simultaneously.

Using a Rainbow Table, I can only do one password at a time. It takes about 10 minutes per password. If I have a list of 100 password, using Rainbow Tables will take me 16 hours to try to crack them all. Large corporations like the NYTimes have tens of thousands of accounts: Rainbow Tables would be pointless.

And no Rainbow Table exists for complex passwords 9 characters and longer. In corporations mandating a minimum of 8 characters for passwords, more than half will be longer than this. In corporations mandating a minimum of 9 characters with a mix of upper/lower case and digits/symbols, Rainbow Tables are 100% useless.

The quote above also includes the statement "some hacker web sites publish as many as 50 billion hashes". This, too, is nonsense. My graphics processor cracks passwords at a rate of 4.5 billion attempts per second. That means I can brute-force 50 billion hashes every 11 seconds. I don't care how many billions of random hashes are published on websites.

What matters is non-random hashes, those that reflect passwords chosen by humans rather than chosen by computers. The most important list of human chosen passwords is the "RockYou" password list. This was a gaming company that stored passwords in the clear. A couple years ago, hackers broke in and stole 14-million unique passwords and dumped them on the Internet. It's the gold standard these days for cracking passwords. Simply comparing the RockYou list to a list of hashes from a domain controller gives you from a third to a half of the passwords in seconds, even when there are good password policies. Mutating the RockYou list gives you even more passwords.

In other words, the statements about "rainbow tables" and "billions of hashes" are nonsense. Accurate information would be that hackers can brute-force billions of passwords per second, and have lists of millions of known passwords.

The point I'm trying to make is that such glaring errors calls into question all the unnamed experts cited in the NYTimes story. If their level of expertise is that they still believe in the threat from Rainbow Tables, then they aren't real "experts". It's not a story based on thoughtful analysis by experts, but a story that just repeats the standard tropes/clich├ęs.


Anonymous said...

Winter2012 is 10 character and has an uppercase letter with a number OR special character. So that password must be uncrackable according to your theory.

Robert Graham said...

No, that takes seconds to crack with a mutated dictionary attack.

My point wasn't to describe how to hack passwords. Instead, it was to point out things like "rainbow tables" is nonsense. The threats are from dictionary attacks and GPU brute-forcing (or a combination with mutated dictionaries), but not rainbow tables.

Anti DDoS said...

I'm a neophyte for this, but one thing I could see is that Rainbow Tables doesn't require you to bang the server x billions times?

Brute force would have got them banned in seconds?

David S. said...

To Anon DDoS: In the case of using brute force guessing in lieu of rainbow tables, you're going to need the password hashes available and not just a live server with a login form to "bang on," so you would need to find a way to get the hashes in the first place either way.