Password Security Catch-All Thread [2015-06-16: Update your LastPass master password]

With the advent of password managers, there's no reason to ever reuse a password. Or memorize them, beyond what you use to protect your password vault.

Password managers always feel like putting all of my eggs in one basket. A basket that I might not always be able to access when I need an egg.

*Legion* wrote:

With the advent of password managers, there's no reason to ever reuse a password. Or memorize them, beyond what you use to protect your password vault.

Are you still using Keepass? I've managed to get it running on my work computer via wine, but would prefer a nice cross platform version.

*Legion* wrote:

It won't take 550 years to crack the second one with a dictionary attack.

Password crackers like John the Ripper have the option to combine dictionary words together with spaces to attack passphrase-style passwords like this.

You're right, it would actually take much, much longer! Let's take for example a dictionary containing nothing but proper spellings of current English words. According to Oxford, that's roughly 170,000 words. Now let's filter that down to relatively common words. I don't have any real numbers for that, but let's say half of the dictionary are words that are common. That gives us a dictionary of 85,000 words.

The number of possible combinations of words is then 85,000^4 or 52,200,625,000,000,000,000. The XKCD comic is using the example of a remote web server which limits us to 1000 guesses per second, so let's use that figure. That means that for a four word dictionary attack using a 85,000 word dictionary, it would take 1,655,270,960 years to crack the password.

So maybe an 85,000 word dictionary is too big, right? Let's really shrink that down and go with a 5,000 word dictionary then. Assuming all four words were in that dictionary, it would only take 19,818 years to guess the password.

Even with a 1,000 word dictionary, it would take 31 years to crack the password at 1,000 guesses per second.

This is all assuming that the hacker somehow knows that the password is 4 words long, uses proper English words, is all lowercase and doesn't use any punctuation, which is a long shot.

taer wrote:
*Legion* wrote:

With the advent of password managers, there's no reason to ever reuse a password. Or memorize them, beyond what you use to protect your password vault.

Are you still using Keepass? I've managed to get it running on my work computer via wine, but would prefer a nice cross platform version.

Can I recommend KeepassX
http://www.keepassx.org/

DanB wrote:
taer wrote:
*Legion* wrote:

With the advent of password managers, there's no reason to ever reuse a password. Or memorize them, beyond what you use to protect your password vault.

Are you still using Keepass? I've managed to get it running on my work computer via wine, but would prefer a nice cross platform version.

Can I recommend KeepassX
http://www.keepassx.org/

I use keepassx on windows. It's better!

Keep nerd fighting about this! Seriously I teach a basic "internet security" course for our library and I have been telling folks to use the first method in the comic. I read the comic and I wondered have I been telling people something wrong? Should I modify my syllabus to say use three or four common words?

Serengeti wrote:
*Legion* wrote:

It won't take 550 years to crack the second one with a dictionary attack.

Password crackers like John the Ripper have the option to combine dictionary words together with spaces to attack passphrase-style passwords like this.

You're right, it would actually take much, much longer! Let's take for example a dictionary containing nothing but proper spellings of current English words. According to Oxford, that's roughly 170,000 words. Now let's filter that down to relatively common words. I don't have any real numbers for that, but let's say half of the dictionary are words that are common. That gives us a dictionary of 85,000 words.

The number of possible combinations of words is then 85,000^4 or 52,200,625,000,000,000,000. The XKCD comic is using the example of a remote web server which limits us to 1000 guesses per second, so let's use that figure. That means that for a four word dictionary attack using a 85,000 word dictionary, it would take 1,655,270,960 years to crack the password.

So maybe an 85,000 word dictionary is too big, right? Let's really shrink that down and go with a 5,000 word dictionary then. Assuming all four words were in that dictionary, it would only take 19,818 years to guess the password.

Even with a 1,000 word dictionary, it would take 31 years to crack the password at 1,000 guesses per second.

This is all assuming that the hacker somehow knows that the password is 4 words long, uses proper English words, is all lowercase and doesn't use any punctuation, which is a long shot.

farley3k wrote:

Keep nerd fighting about this! Seriously I teach a basic "internet security" course for our library and I have been telling folks to use the first method in the comic. I read the comic and I wondered have I been telling people something wrong? Should I modify my syllabus to say use three or four common words?

Ditto. I know a little about password security (enough to be dangerous?) and thought that something like the "Tr0ub4dor3&" would be pretty unfeasible with a dictionary attack. Either I don't actually understand dictionary attacks, or the comic is referring to some other method. Since I have know idea why that example is "Easy to guess", I was hoping there would be a blog post to explain it, but if there was, I didn't see it.

farley3k wrote:

Keep nerd fighting about this! Seriously I teach a basic "internet security" course for our library and I have been telling folks to use the first method in the comic. I read the comic and I wondered have I been telling people something wrong? Should I modify my syllabus to say use three or four common words?

If they can use pass phrases, they should. Most internet sites don't like spaces in their passwords though, in which case you can usually substitute an underscore, though that tends to be a pain to retype.

If you want to be uber-secure, use a pass phrase that naturally contains punctuation and capitalization, for example: "I've been a naughty lad!". Super easy to remember, and there's not a dictionary or brute force attack in the world that'll crack that in any reasonable timeframe.

"But Serengeti", you might say, "Many people automatically capitalize the first word and finish with punctuation, so wouldn't the crackers take that into account?"

Well yeah, but they'd also have to take into account the fact that many people are too lazy to do so, which means that for the first word their dictionary would contain all lowercase words and all capitalized words, which suddenly doubles the amount of first words to try. The last word dictionary would have to be quadrupled in size just to take into account a period, exclamation mark, question mark or no punctuation at all. Just adding those rules to the crack attempt would push the crack time for a four word phrase using my theoretical 1,000 word dictionary from 31 to 253 years.

Garden Ninja wrote:
farley3k wrote:

Keep nerd fighting about this! Seriously I teach a basic "internet security" course for our library and I have been telling folks to use the first method in the comic. I read the comic and I wondered have I been telling people something wrong? Should I modify my syllabus to say use three or four common words?

Ditto. I know a little about password security (enough to be dangerous?) and thought that something like the "Tr0ub4dor3&" would be pretty unfeasible with a dictionary attack. Either I don't actually understand dictionary attacks, or the comic is referring to some other method. Since I have know idea why that example is "Easy to guess", I was hoping there would be a blog post to explain it, but if there was, I didn't see it.

Thirded. Depending on the importance of the site, I either use a mix of letters and numbers, like a title of a work (e.g. the900days), or for more important sites, I'll use a longer proper noun with mix of l33t spelling (e.g. l4nc3r3v0fq400). I figured those would be a) secure while still being b) memorable. My only password manager is Keychain on my Mac, which is locked by my account password, which at one time was the most secure but memorable password I could conceive: an original parody of a fictional proper noun with a mix of l33t and punctuation (e.g. m0nk1(h1p17h3(u5).

(Obviously I don't use any of those.)

So now today's xkcd has thrown me for a loop and I don't know if those are good, good enough, or naively simple.

Legion (I think) brought up one of the arguments against using the common words separated by spaces earlier in this thread (yes it has come up before). Many websites have crap security (I don't remember what it was called), and they truncate passwords to a limited amount of characters without actually informing you of this. This would cause your four common word spaced password to be a 2 word separated by a space password.

On another note, any website that doesn't allow for special characters in a password pisses me off to no end. I think Blizzard wouldn't allow it for some reason, and I just threw up my hands with a big "What the hell? Seriously?"

tuffalobuffalo wrote:

Legion (I think) brought up one of the arguments against using the common words separated by spaces earlier in this thread (yes it has come up before). Many websites have crap security (I don't remember what it was called), and they truncate passwords to a limited amount of characters without actually informing you of this. This would cause your four common word spaced password to be a 2 word separated by a space password.

On another note, any website that doesn't allow for special characters in a password pisses me off to no end. I think Blizzard wouldn't allow it for some reason, and I just threw up my hands with a big "What the hell? Seriously?"

I heard about that recently. It was something about early versions of Unix only allowing 8 characters (I assume this is related to /etc/passwd). But that just raises more questions. Like, does that limitation exist in newer *nixes? And even if it does, why are they authenticating against the machine directly, rather than using a database? And if they are using a database, you should be hashing the passwords anyway, and therefore know the storage requirements; so are they using plaintext and truncating? Truncating the plaintext then hashing also? What?

Garden Ninja wrote:
tuffalobuffalo wrote:

Legion (I think) brought up one of the arguments against using the common words separated by spaces earlier in this thread (yes it has come up before). Many websites have crap security (I don't remember what it was called), and they truncate passwords to a limited amount of characters without actually informing you of this. This would cause your four common word spaced password to be a 2 word separated by a space password.

On another note, any website that doesn't allow for special characters in a password pisses me off to no end. I think Blizzard wouldn't allow it for some reason, and I just threw up my hands with a big "What the hell? Seriously?"

I heard about that recently. It was something about early versions of Unix only allowing 8 characters (I assume this is related to /etc/passwd). But that just raises more questions. Like, does that limitation exist in newer *nixes? And even if it does, why are they authenticating against the machine directly, rather than using a database? And if they are using a database, you should be hashing the passwords anyway, and therefore know the storage requirements; so are they using plaintext and truncating? Truncating the plaintext then hashing also? What?

The issues Legion brought up were here.

*Legion* wrote:

It won't take 550 years to crack the second one with a dictionary attack.

Password crackers like John the Ripper have the option to combine dictionary words together with spaces to attack passphrase-style passwords like this.

He's taking that into account. Four randomly chosen common dictionary words is still much much much harder to guess. It doesn't matter that a tool can produce the password and try it. It still has to get the *right answer*, and it will take that long to get the answer at 1000 guesses per second.

1000 guesses per second is pretty slow, which may be what's throwing you off here. I presume he included it simply to give a sense of scale. The base insight is that [em]given a tool like John the Ripper[/em] that is doing nothing but guesses strings of dictionary words, it will take an expected 17,592,186,044,416 guesses to find the password. That's assuming you're picking from a corpus of only 2048 different English words.

Dammit. Super-tannhausered. This is what I get opening tabs to all the threads I want to read at once.

But yeah, the real issue here is systems with stupid password rules.

If I can use a *real passphrase*, I don't need to do weird leetspeak crap and so on to have a secure password. But if I have to do stupid punctuation and numbers and have a password change policy that bitches if the new password is "too similar", there's no point in using a long secure passphrase because I have to remember the line noise *anyway* just to satisfy the "security rules".

I think what the xkcd thing is really about is: No, really, it would be better to have different rules for password choice. By all means, reject passwords for being "too simple". But do it algorithmically so that a long no-line-noise phrase counts as being as secure as a short-with-line-noise password (or better). Blanket "you must use line noise" rules are just bad.

(Hell, use a password cracker to try to guess the password for a while as a test. Heck, run it for a minute after password change and force a new change right away if it breaks that fast, and then if it can find it in the next two days of work, require the password to be changed *again*.)

Grumble grumble.

Serengeti wrote:

The number of possible combinations of words is then 85,000^4 or 52,200,625,000,000,000,000. The XKCD comic is using the example of a remote web server which limits us to 1000 guesses per second, so let's use that figure. That means that for a four word dictionary attack using a 85,000 word dictionary, it would take 1,655,270,960 years to crack the password.

So maybe an 85,000 word dictionary is too big, right? Let's really shrink that down and go with a 5,000 word dictionary then. Assuming all four words were in that dictionary, it would only take 19,818 years to guess the password.

Even with a 1,000 word dictionary, it would take 31 years to crack the password at 1,000 guesses per second.

85,000 word dictionary x 4 words = 85000^4 = 5.22 × 10^19
5,000 word dictionary x 4 words = 5000^4 = 6.25 × 10^14
94 type-able characters on keyboard (26 lowercase + 26 uppercase + 32 special characters + 10 digits) x 11 characters in password string = 94^11 = 5.06 × 10^21

Now, my comment in reference to the 550 years line, I do have to back off of. I didn't pay close enough attention to the 1000/sec parameter set out. But the passwords are, in fact, clearly weaker than even a modestly sized random string, once you take dictionary attacks into consideration.

I do take extreme issue with this line from the comic: "Yes, cracking a stolen hash is faster, but that's not what the average user should worry about."

Complete horsecrap. That is absolutely what the user should worry about. After all, that's how so many actual compromises of web service passwords do happen (Gawker, for instance).

And attacks on stolen hashes go into the millions and even billions per second on commodity hardware, not 1000. The problem with framing this in terms of 1000 attempts per second is that it makes passwords that are easily compromised in an offline attack sound like they're actually uncrackable.

I actually don't take much issue with recommending people use passphrases. If they have to remember a password, it's a decent way to get a memorable one that's reasonably strong. Certainly more so compared to a short one that's equally memorable.

However, I do take issues with people looking at the strength of passphrases purely from a length of character-by-character brute force attack perspective. Dictionary attacks unquestionably are a viable attack against such passwords and they shrink the amount of time to crack one considerably.

And I very strongly take the stance that memorizing passwords is doings things ass-backwards. You shouldn't memorize (most) passwords. Your password manager's job is to do that for you. You do need to memorize a few, like the one you lock your password vault with.

Memorizing passwords goes hand-in-hand with reusing passwords, and that is the drop-dead dumbest security move you can do, short of the obvious things. Somewhere, you're going to stick that password into a web service that doesn't protect it at all. Cleartext field in a database. Bye bye nice memorable password.

(EDIT: As stated before, I'm not a security expert - nor a math one, for that matter - so don't hold it too strongly against me if I f&%k something up )

Maybe this is somewhere earlier in the thread, but I guess I don't really understand how you would actually use a password manager. Say you have 3 computers, how do you access a website like Amazon from all three computers. What if you need to access it from somewhere other than one of your computers?

Also, are there password managers that work for droid phones, because I also want to access these things on my phone.

kaostheory wrote:

Maybe this is somewhere earlier in the thread, but I guess I don't really understand how you would actually use a password manager. Say you have 3 computers, how do you access a website like Amazon from all three computers. What if you need to access it from somewhere other than one of your computers?

Lots of ways.

Hosted ones like LastPass store your encrypted blob and transfer it to whatever system you sign in from.

For non-hosted ones like 1Password or KeePass, you can store your vault on a service like Dropbox yourself, or on a USB drive or something.

Most of them have web browser extensions so you can have your passwords auto-fill.

Also, are there password managers that work for droid phones, because I also want to access these things on my phone.

Most of the ones I know of have clients for iOS, Android, etc.

*Legion* wrote:

85,000 word dictionary x 4 words = 85000^4 = 5.22 × 10^19
5,000 word dictionary x 4 words = 5000^4 = 6.25 × 10^14
94 type-able characters on keyboard (26 lowercase + 26 uppercase + 32 special characters + 10 digits) x 11 characters in password string = 94^11 = 5.06 × 10^21

94 characters. Let's square that, and we get 8836. Given an 8836 word dictionary, I need five and a half words to match the 11 character password.

I'll take that trade.

Notice that with an 8836 word dictionary, an eight-character password is as good as a four word passphrase.

*Legion* wrote:

However, I do take issues with people looking at the strength of passphrases purely from a length of character-by-character brute force attack perspective. Dictionary attacks unquestionably are a viable attack against such passwords and they shrink the amount of time to crack one considerably.

He was in fact looking at it from the point of view of dictionary-based attacks. If you actually look at the comic, his "special characters" password assumed a dictionary-word basis with mutations and additions. He was also assuming that you would choose a less common word for that password (65536 word lexicon) than for the four words of the passphrase.

Using a passphrase-initialism mutation password (memorizable, not easily subject to dictionary attacks, but harder to memorize than the word mutation password) is of course significantly stronger than that, but gets troublesome. I have a password which is required to be 15 or more characters, including two symbols and two digits. Unfortunately, that size makes passphrase-initialism break pretty hard. I am also required not to write this password down or store it in any medium. That password pisses me off, a lot.

*Legion* wrote:

And I very strongly take the stance that memorizing passwords is doings things ass-backwards. You shouldn't memorize (most) passwords. Your password manager's job is to do that for you. You do need to memorize a few, like the one you lock your password vault with.

This is a good idea for most users. An even better idea, of course, would be to allow for token-based credentials in the fashion of Kerberos so that you don't have to give passwords to umpteen different services. Essentially equivalent, but more thoroughly automated. (OpenID is more or less as good as this, although it is not usable outside a web-based context.)

But as far as "what should I tell my mother to do to choose secure passwords"? Yeah, I recommend using a passphrase, and using unique ones for the most important uses (i.e. money is involved) and a shared one for things she doesn't care about so much (i.e. random web bullsh*t). If she was doing anything truly important, I'd probably recommend a password safe thing.

By the way, putting notes in the Mac keychain is a decently solid choice for a simple secure storage mechanism for passwords.

*Legion* wrote:

85,000 word dictionary x 4 words = 85000^4 = 5.22 × 10^19
5,000 word dictionary x 4 words = 5000^4 = 6.25 × 10^14
94 type-able characters on keyboard (26 lowercase + 26 uppercase + 32 special characters + 10 digits) x 11 characters in password string = 94^11 = 5.06 × 10^21

Now, my comment in reference to the 550 years line, I do have to back off of. I didn't pay close enough attention to the 1000/sec parameter set out. But the passwords are, in fact, clearly weaker than even a modestly sized random string, once you take dictionary attacks into consideration.

The whole point of the Xkcd example was that the "line noise" password isn't 11 characters chosen at random from the keyboard - it's a dictionary word with a certain amount of obfuscation that makes it look random to the human brain (which is notoriously terrible at evaluating randomness) but doesn't actually add much security. If you actually did use 11 random characters, that would be very secure ... except that I can be 100% certain that you won't be able to remember it without writing it down. As Xkcd correctly points out, even the modest amount of randomness in his example makes it hard to remember, whereas the 4-word passphrase is both easier to remember and harder to crack.

Granted, it's arguable that writing a password down isn't necessarily insecure if you're careful what you do with the piece of paper, and as others have pointed out, password manager software offers a secure way of "writing it down". But the basic point of the cartoon is bang on the money.

Hypatian wrote:
*Legion* wrote:

It won't take 550 years to crack the second one with a dictionary attack.

Password crackers like John the Ripper have the option to combine dictionary words together with spaces to attack passphrase-style passwords like this.

He's taking that into account. Four randomly chosen common dictionary words is still much much much harder to guess. It doesn't matter that a tool can produce the password and try it. It still has to get the *right answer*, and it will take that long to get the answer at 1000 guesses per second.

It is possible that it will take that long. It's also possible that it will take 1/1000th of a second.

I have recently started using sentences in two forms:
1) First letter of each word, maybe with a number or punctuation or both.
Example: "I hate having to change my password!" becomes something like "Ihhtcmp!"

This works well enough.

2)Just make a damn sentence, possible number addition, possible punctuation.
Example: "This is dumb." becomes "Th1s1sdumb."

These are easy to remember and easy to make fit corporate requirements.

One thing I like about the first method, however, is you can put a prompt on your monitor sticky note or whiteboard without completely giving it away.
Who's going to read your whiteboard and think your "rage against the machine" of "I hate having to change my password!" is actually the key to your machine?
And when you have to change it in 60 days, erase the prompt on your whiteboard, write a new one down.
"Our password policy is silly and doesn't help security."
becomes
"Opp1sadhs."

And you don't have to remember it. It's "written down" but not in an easily stealable way.

...

It's pretty obvious that what I said was short-hand for "the [em]expected time[/em] to discover the password". Sorry for not speaking more pedantically.

As for your cases: Case 1 is what I described above as "passphrase-initialism mutation". It's a good system. Until some jackass tells you your password has to be 15 characters long and you've got to change it every month. Case 2 is barely more secure than a real passphrase of the same length, less secure than a real passphrase of optimal length, and you still have to remember where the weird punctuation and crap is. Still, they're both good ways to do things. Just not better than choosing a reasonable passphrase.

It's worth noting that a reasonably easy method of getting around the numbers-and-symbols password restriction style is to use an easily rememberable number-symbol combo as a prefix, then use a passphrase for the rest. Depending on what sort of "password is too similar" rules are in place for changing your password, you may or may not have to change the number-symbol combo with each password change. (Assuming, of course, that passwords of >20 characters in length are allowed.)

Garden Ninja wrote:
tuffalobuffalo wrote:

Legion (I think) brought up one of the arguments against using the common words separated by spaces earlier in this thread (yes it has come up before). Many websites have crap security (I don't remember what it was called), and they truncate passwords to a limited amount of characters without actually informing you of this. This would cause your four common word spaced password to be a 2 word separated by a space password.

On another note, any website that doesn't allow for special characters in a password pisses me off to no end. I think Blizzard wouldn't allow it for some reason, and I just threw up my hands with a big "What the hell? Seriously?"

I heard about that recently. It was something about early versions of Unix only allowing 8 characters (I assume this is related to /etc/passwd). But that just raises more questions. Like, does that limitation exist in newer *nixes? And even if it does, why are they authenticating against the machine directly, rather than using a database? And if they are using a database, you should be hashing the passwords anyway, and therefore know the storage requirements; so are they using plaintext and truncating? Truncating the plaintext then hashing also? What?

Yes plenty of website truncate your password to 8 or 12 characters without telling you. And having just changed all my online passwords to random strings I can also tell you that plenty websites don't appear to allow special (punctuation) characters (you can changed the password but it then won't allow you to log in with it). It is almost certainly nothing to do with what version of *nix might be running at the server, new website users aren't being added as users on the host machine after all. Most likely it'll be something to do with the default size of a password field in the underlying database not being changed or made bigger. Although I've not looked I'll bet a couple of popular CMSes out there have 8 or 12 character default password sizes. And in the case of the special characters they are probably sanitizing the password field on their log in page when they shouldn't be (but not on their "change password" page).

DanB wrote:

Most likely it'll be something to do with the default size of a password field in the underlying database not being changed or made bigger. Although I've not looked I'll bet a couple of popular CMSes out there have 8 or 12 character default password sizes. And in the case of the special characters they are probably sanitizing the password field on their log in page when they shouldn't be (but not on their "change password" page).

I'd lay money 9 times out of 10 it's down to the charset on the underlying database.

Maq wrote:
DanB wrote:

Most likely it'll be something to do with the default size of a password field in the underlying database not being changed or made bigger. Although I've not looked I'll bet a couple of popular CMSes out there have 8 or 12 character default password sizes. And in the case of the special characters they are probably sanitizing the password field on their log in page when they shouldn't be (but not on their "change password" page).

I'd lay money 9 times out of 10 it's down to the charset on the underlying database.

GPWM

heard about that recently. It was something about early versions of Unix only allowing 8 characters (I assume this is related to /etc/passwd). But that just raises more questions. Like, does that limitation exist in newer *nixes?
DanB wrote:

It is almost certainly nothing to do with what version of *nix might be running at the server, new website users aren't being added as users on the host machine after all.

Well, yes and no. It does have to do with *nix when you're using the crypt(3) library function as your hashing algorithm.

The DES-based crypt() function that truncates to 8 characters has been in UNIX for a long time. It has perpetuated over 30-some years in order to maintain compatibility.

Modern UNIXes provide a crypt() implementation that supports hashing algorithms beyond just DES, but the default for the function is still DES (again, for historical compatibility reasons) and you only use a more modern hashing algorithm if you specifically tell crypt() to do so (which, of course, is what modern UNIXes do for hashing their own passwords).

The issue with Gawker was that they were indeed using a DES-based crypt(). Whether it was from using an old UNIX with no other crypt() option or just not making a new one use a modern hashing algorithm, it still comes down to Gawker using the decades-old DES hash that was the traditional UNIX hashing method for a long time.

Worse, I don't think they were even using a local salt.

For those who don't know what that means: hashing algorithms are, by their nature, entirely predictable. You feed a value into a hash function, and you will always get the same value out of it. A good hash function is not predictable; given the input, you should have absolutely no idea what the output will look like until you actually run the algorithm. Each hash should be as unique as possible; collisions (where two different passwords hash to the same value) need to be very rare, or it's not a good hashing system. And, of course, it's a one-way trip; you can't use the hash to get the original data back. (if you could, it would be encryption, not hashing.)

The idea is that you give the website a password, and it hashes the password, and only stores the hash. Then, when you log in again, you retype the password, it re-hashes it, and compares it to the stored value. It's almost like storing the actual password, except that even the website doesn't know what it is, unless they store it separately. There is no mathematical way to reverse the process; they are throwing bits away repeatedly as they run the algorithm, and once those bits are lost, they're gone forever. Once you've made hamburger, there's no restoring the cow.

The problem there is the predictability. If you're just using standard DES, for instance, attackers can precompute hashes for zillions of passwords, and store them in a special format called a 'rainbow table'. Rainbow tables are very clever compression algorithms... it would take a couple of paragraphs to explain *why* they're so clever, but basically they can store a LOT of password hashes in a surprisingly small space, given the size of the potential data sets they're dealing with. It's pretty common for a rainbow table holding the hash of every single 8 character password to take under 2TB to store. If the attackers get some hashes, they can just do a reverse search; if the original password was 8 or less characters, they've got you in a tenth of a second. Computing the rainbow table took months or years of computer time, but then lookups are instant.

So the way to defeat rainbow tables is to add a unique value for the site to the user's password before hashing. If your password is "password", they might hash "passwordlocalsalt9983". This means that rainbow tables are completely useless; they didn't precompute with the extra salt data, so they have to start from scratch and try to brute-force their way in.

Salt doesn't add any true difficulty to the cracking process, but it forces attackers to start flatfooted, with no preparation, once they get a copy of the password database. This gives the site a much better chance of noticing the theft before very many passwords are cracked, and hopefully gives users time to change them before the brute-forcing stumbles into theirs.

Salt, in other words, buys response time, rather than actual hard security, but response time is often all that's really needed. And salt is so utterly trivial to implement that nearly EVERYONE does it. It's a huge win for zero cost, but Gawker didn't bother. They just used the bog-standard hash functions, so they were totally vulnerable to rainbow tables. Boom, instant hack, no time to warn users at all.

For a tech site, that's a gaffe the size of the Grand Canyon.

The lesson is. Change your password(s) regularly and often.

Malor wrote:

Worse, I don't think they were even using a local salt.

For those who don't know what that means: hashing algorithms are, by their nature, entirely predictable. You feed a value into a hash function, and you will always get the same value out of it. A good hash function is not predictable; given the input, you should have absolutely no idea what the output will look like until you actually run the algorithm. Each hash should be as unique as possible; collisions (where two different passwords hash to the same value) need to be very rare, or it's not a good hashing system. And, of course, it's a one-way trip; you can't use the hash to get the original data back. (if you could, it would be encryption, not hashing.)

The idea is that you give the website a password, and it hashes the password, and only stores the hash. Then, when you log in again, you retype the password, it re-hashes it, and compares it to the stored value. It's almost like storing the actual password, except that even the website doesn't know what it is, unless they store it separately. There is no mathematical way to reverse the process; they are throwing bits away repeatedly as they run the algorithm, and once those bits are lost, they're gone forever. Once you've made hamburger, there's no restoring the cow.

The problem there is the predictability. If you're just using standard DES, for instance, attackers can precompute hashes for zillions of passwords, and store them in a special format called a 'rainbow table'. Rainbow tables are very clever compression algorithms... it would take a couple of paragraphs to explain *why* they're so clever, but basically they can store a LOT of password hashes in a surprisingly small space, given the size of the potential data sets they're dealing with. It's pretty common for a rainbow table holding the hash of every single 8 character password to take under 2TB to store. If the attackers get some hashes, they can just do a reverse search; if the original password was 8 or less characters, they've got you in a tenth of a second. Computing the rainbow table took months or years of computer time, but then lookups are instant.

So the way to defeat rainbow tables is to add a unique value for the site to the user's password before hashing. If your password is "password", they might hash "passwordlocalsalt9983". This means that rainbow tables are completely useless; they didn't precompute with the extra salt data, so they have to start from scratch and try to brute-force their way in.

Salt doesn't add any true difficulty to the cracking process, but it forces attackers to start flatfooted, with no preparation, once they get a copy of the password database. This gives the site a much better chance of noticing the theft before very many passwords are cracked, and hopefully gives users time to change them before the brute-forcing stumbles into theirs.

Salt, in other words, buys response time, rather than actual hard security, but response time is often all that's really needed. And salt is so utterly trivial to implement that nearly EVERYONE does it. It's a huge win for zero cost, but Gawker didn't bother. They just used the bog-standard hash functions, so they were totally vulnerable to rainbow tables. Boom, instant hack, no time to warn users at all.

For a tech site, that's a gaffe the size of the Grand Canyon.

The salt also should be random and unique to each user (this is called a "nonce", I believe). Otherwise, once they determine the salt used, they could just recompute the rainbow table. A unique salt for each user means you need to store the salt for the hash comparison to work. This isn't actually much of a problem, since even if the attackers have the salts, they would still need to recompute the rainbow table for every single user.

Even leaving rainbow tables aside, unique salts are important simply so that people that happen to have the same password won't have the same hash. Otherwise, the first time I crack someone's "123456" password, I've cracked everyone else's hashes with the same password, because the hashes match. It just makes the cracking process go that much faster.

BadMojo wrote:

The lesson is. Change your password(s) regularly and often.

And don't reuse them across sites, period, amen.

The scary part of the Gawker crack isn't that crackers could log in and comment as you on Gizmodo. It's that many of those people use those same passwords for lots of other things, and the crackers have that person's email account sitting right next to the now-cracked password hash. It becomes trivial to find that user's accounts on other sites and start using that password to try and get in.

You simply cannot trust the average web service to (a) store your password correctly, and (b) disclose when a breach happens in a timely manner. You must ensure that your exposure doesn't go beyond that specific site.

Maybe a better way to sum that up:

Just using the raw hash function, someone has to generate and store all the hashes for all the possible passwords of X characters or less; this allows every password of X complexity or less on every site in the world that uses that hash to be instantly hacked.

With a per-site salt, doing that much work will get every password of X complexity in that system. You'd only create and share a rainbow table if you thought more than one site used that salt. If you were sure the salt was unique, you'd generate a hash, compare it to what was on the system, and throw it away if it didn't match anything. No point in storing it.

With a per-user nonce, doing that much work gets you one user. You have to start all over again, from scratch, on User B.