Don’t Rub Salt in Your Wounds

By now everyone’s downloaded a copy of John the Ripper and taken a crack (ahem) at the LinkedIn password file. The wordlists, whatever their provenance or size, likely ran out in a matter of minutes. That left unsophisticated users with the unending silence of incremental mode compounded with the challenge of figuring out how to tease incremental mode into making guesses longer than eight characters.

On the other hand, a cunning cracker might think for a moment about users’ psychology. We all have passwords. We’ve all heard that passwords should be long, preferably longer than eight characters (to the disappointment of crackers who can’t figure out CHARSET_LENGTH and the –make-charset option), and these super passwords shouldn’t just be letters. I already went through one counterpoint to relying on users to follow this advice. Here’s another.

LinkedIn has already been lambasted for not salting passwords. Salting would not have increased the work factor for attackers (the time difference between cracking salted vs. unsalted passwords isn’t significant). Instead, salting would have protected users who had chosen short passwords because it would have defeated precomputation attacks — the pleasantly named “rainbow table” attack. A hacker who started building a rainbow table in 2000 would have a nice collection of precomputed password hashes for most complex passwords up to eight characters. All that’s needed is to look up a pre-calculated hash and reference the password that generated it. The sha1 of “MyP4$$w0rd” is always 8300de9d93a7bd03edce1e73ede3bbfe7fc7c714. The hacker only needed to crack that hash once. The hacker builds a dictionary of hashes for passwords based on movies, songs, etc. Including simple passwords like “12345”.

Salts come to the (meager) rescue for the poor sap who chose “12345”. Adding a long salt changes the original hash from 8cb2237d0679ca88db6464eac60da96345513964 to 99483607e3ee3891208749a372cbff883b5bc652. Whereas the hacker’s rainbow table surely had an entry for the first …3964 hash it’s equally unlikely that the rainbow table has an entry for the second …c652 version even though the user’s password remains “12345”. The presence of a salt erases all of that preparatory work, thereby forcing the hacker to fire up the CPUs for some old-fashioned brute force.

While the salt defeats the rainbow table it isn’t a defense against brute force. If the password list is compromised, then it’s safe to assume the salt is going to be exposed as well. So, if the salt in our example is exposed as “alongsalt” then the time to brute force a password of “alongsalt12345” does not change in comparison to attacking the same password without a salt. The password would be lucky to last a few minutes in either case.

Humans like patterns. Ever since we descended from the trees (well, real humans did; the explanations based on some magic-sky-dude are kinda fuzzy, but I digress as usual) humans became creatures of habit.

Passwords are no different. Exhibit A) Users chronically select poor passwords; exhibit B) Users are constantly encouraged to create long passwords; exhibit C) LinkedIn was hacked. Do you concur?

Which brings us to the bad habit of salting yourself. Or more accurately, using poor entropy to extend a password’s length. It’s easy to turn a short password like “12345” into a longer password by including the web domain, e.g. “linkedin12345” — woohoo! 13 characters! And an entirely predictable password scheme for an account on a site called “LinkedIn”. The mixed-case version, “LinkedIn12345”, fares no better.

On Wednesday I took the time to manually guess some passwords based on pop-culture topics. I have a nice, long .bash_history file to prove it. Today it was time to polish off my JtR memory to play with password schemes. As always, efficiency (a.k.a. laziness) rules the day. The first step was to look for users who chose to improve their password by adding the word, “linkedin”. John the Ripper’s rule mechanism makes this easy. Take a word list and add a word to the beginning or end of each entry.

[List.Rules:LinkedIn]
-: A0"linkedin"
-: Az"linkedin"

Bunch of hits right off the bat. But remember that laziness rule? We could enumerate the different case combinations and number-vowel substitution with more A0 and Az rules. Or we could use the ^, $, and grouping operators. In six lines of JtR rules we’ve extended the word list to hit some fun combinations.

[List.Rules:LinkedIn]
# linkedin
-: ^[nN]^[iI1]^[dD]^[eE3]^[kK]^[nN]^[iI1]^[lL]
-: $[nN]$[iI1]$[dD]$[eE3]$[kK]$[nN]$[iI1]$[lL]
# nideknil (linkedin reversed)
-: ^[lL]^[iI1]^[nN]^[kK]^[eE3]^[dD]^[iI1]^[nN]
-: $[lL]$[iI1]$[nN]$[kK]$[eE3]$[dD]$[iI1]$[nN]
# number|@ -> linkedin or linkedin -> number|@
-: ^[nN]^[iI1]^[dD]^[eE3]^[kK]^[nN]^[iI1]^[lL]^[0-9@]
-: ^[0-9@]^[nN]^[iI1]^[dD]^[eE3]^[kK]^[nN]^[iI1]^[lL]

Suddenly, it becomes clear that users are terrible creatures of habit. My favorite so far? 6af6ebbbea6a2c20f25fd84c9933a8d6ef908c20.

There’s one positive aspect here in that it’s extremely likely that each linkedin-variant password is only used for LinkedIn accounts. But that’s bad news if hackers go after those accounts with domain-style password schemes on other sites.

The message here is that passwords should be a surprise. Yes, normally “L1nk3d1n” would be a good start to a long password, except for the correlation with the site’s domain name. The predictable component only adds about nine bits of entropy to the password rather than the expected 48 bits from an eight-character alphanumeric mix.

I’ll expand on the surprise principle in an upcoming post. Good password advice requires more explanation than four bullet points — the majority of passwords found by the custom JtR rules would have satisfied what turns out to be empty advice if you don’t understand the underlying reasons.

Finally, LinkedIn shouldn’t just be salting the password, they should be applying an algorithm like PBKDF2 to increase hackers’ work factor required to crack a password. Briefly, PBKDF2 applies iterative hashing such that the time to brute force “12345” changes from a few seconds to several minutes. In other words, the longer it takes to generate a single password guess compounds the hackers’ effort against a million combinations. For example, your WPA2 wi-fi connection applies 4,096 iterations for a password hash. To make the math simple, if it took 1 second for a single iteration of SHA1, then it would take over an hour for 4,096 iterations of SHA-1. (Obviously, it doesn’t take an hour because we enjoy efficient wireless connections — the point is that there will still be a significant time increase.)

Change your password. Avoid a domain-style password scheme. Employ PBKDF2 if you’re responsible for protecting passwords. Because hackers have the same advantage as Mick Jagger, “Time is on my side. Yes it is.