Password Hashing

I have an online account that uses multifactor authentication.  If you're not familiar with multifactor authentication systems, then a brief introduction is in order:

A multifactor authentication system is one that that requires more than one method of authentication, each sourced from independent categories of credentials.  These categories are divided into the following three domains:

1. Something you know
2. Something you have
3. Something you are

Something you know is a password or pass-phrase.
Something you have is a token generating key-fob or a key card with a magnetic stripe.
Something you are is a fingerprint, voice or retinal print.

The first two factors can be easily revoked, the last factor - something you are - cannot be revoked. That's why, along with false positive and false negative rates, something you are should never, ever be used as the primary method of proving identity: it must always be mixed with another factor.

Back to my online account.

I was attempting to log into this account one day when it refused to accept my password.  I reset the password 3 or 4 times - using a strong password each time - and finally called the support desk when I had successfully pulled out the remaining bits of my hair.  They gave me a reset password.  I tried using that password while on the phone with them: no go.

Then they said, 

"Did you also input your token from your authentication app?"

"Why, no.  I did not.  How do I do that?" 

"Enter the password, then follow the password with the authenticator passcode."

So I did just that, and presto: I was authenticated into the system.  Pretty neat.  Until you think about how it could be broken.

How Password Management Should Work

Storing passwords has always an Achilles' heel of Information Security. A lot of developers get it wrong. It's why companies like LinkedIn get pwn'd. In order to do it right, you have to implement several things.

Add some Salt

First, you must always employ a salt. IMO, a salt is at least 128 bits (16 bytes) of cryptographically secure random data. In other words, using srand() and rand() are right out. On Linux'ish systems you must use /dev/random or /dev/urandom (see here regarding the Myths of about /dev/urandom).

Windows has it's own way of providing cryptographically secure random numbers (Google is your friend).

Choose Speed or Memory

And by that I mean, never use SHA[what-ever] to hash your passwords.  Always use one of the following

1. bcrypt - time intensive
2. scrypt - memory intensive
3. PBKDF2 - time intensive

If you use anything other than those functions, you're doing it wrong.

If you don't add unique salts to your password, you're doing it wrong.

If your salt is compiled into your program, you're doing it wrong.

Save the Result

It's really that simple: save the hash and the salt right next to each other if you want to, but you must save the both.  Never save a password, even if you encrypt it with AES.  You must, however, employ proper security controls around the password store.  While encryption is always a preferred control when storing information, there are customary ways to make sure files are available only to the entity that needs them.  Specifically, file ownership and read/write/modify permissions.  On a Linux-ish system, that generally means a unique, hidden folder accessible only by the entity, and a file accessible only by the entity.  E.g.,

$ mkdir  .my_hidden_dir
$ touch  .my_hidden_dir/my_file
$ chown  -R user:group .my_hidden_dir
$ chmod  u=rwx,go-rwx .my_hidden_dir
$ chmod  u=rw,go-rwx .my_hidden_dir/my_file

When the user enters their password, grab the salt, add it to the password, execute your hashing algorithm and compare.  If you get the stored hash, you have the correct password.

How It Could be Done Wrong

Lets recall the facts: my online provider requires me to enter my password and my token at the same time, one appended to the other, like this:

• [password][token]

The problem is this: how does my provider know the length of my password?  In order to calculate the hash of my password, they need the salt and the password.  Since the information is input as one string, then there are only few ways that my password can be extracted from the string:

1. They're saving the length of my password with my password hash
• This is bad.  If the password database is exposed, then my hash, salt and password length will be exposed.  This reduces the time necessary to crack the password since an attacker needs only to create a dictionary of hashes based upon the length of my password - assuming that the attacker also knows the iteration count of the hash algorithm (e.g., the provider is not using SHA[what-ever]). 
2. They're saving my password (not hashed)
• Wrong all the way around, even if it's encrypted.  Don't do it.
3. The token is a fixed length
• A likely possibility.  But this breaks when the token generator changes the length of the token.
4. The password + token is not hashed before it reaches the web server
• This sounds dangerous, but actually the converse is more dangerous:
• If the password is hashed in the client (assuming a browser interface), then the attacker has full knowledge of the hashing algorithm used by the password management system.  Once that system is compromised and the password hashes are exposed, it will be a short order before they're all cracked using a dictionary attack.
• Never hash your passwords in the client

Conclusion

A proper implementation should request the one-time-token from the generator and match that pattern in the string provided by the user.  Where the match begins marks the end of the user password+1.  From there, it's simple string splitting, hashing and comparing.  This solves the problem of variable length tokens from the one-time-token generator.

Doing security correctly is not as easy as it looks or sounds.  We must employ the proper tools to insure our designs and architectures are sound.  As far as my online provider, I can only hope they're using strong hashing algorithms.  But given that they're requiring something I have, it's very, very unlikely that an attacker will randomly provide the correct password+token.