My friend Kristen asked me over the weekend when I was going to stop blogging about crypto math and say something funny again. Everyone’s a critic!

Patience, my dear. Today, the final entry in my series on salt. Tomorrow, who knows?

---

So far we’ve got a system whereby the server does not actually know what your password is, it just has a salted hash of your password. But we’re still sending the password over the wire in clear text, which seems risky.

System #4

What if the hash goes over the wire? The client sends the user name to the server. The server sends the password salt to the client. The client appends the password to the password salt, hashes the result, and sends the hash to the server. The server compares the hash from the client to the hash in the user list. Now the password never goes over the wire at all. Awesome!

Unfortunately, this system is worse. In previous systems the eavesdropper got the password; in this system the eavesdropper gets the salted hash. The eavesdropper can then write their own client which sends that username and salted hash to the server.

And the “steal the password list” attack just came back; now an attacker who gets the password list gets all the salted hashes, and can use them to impersonate the user. Sure, the attacker will still find it hard to deduce the original password from the salted hash, but he doesn’t need to deduce the password anymore. (Unless of course the attacker is attempting to deduce your password on one system so that he can use it to attack another system that you use. This is why it’s a bad idea to use the same password for two different systems.)

Essentially we’ve turned the salted hash into a “password equivalent”. Can we fix this up?

System #5

How about this?

The client sends the username to the server. The server creates a second random salt which is NOT stored in the user list. This random salt is usedonly once — we either make it so big that odds of generating it again are low, or keep a list of previously used random salts and pick a new one if we have a collision. We’ll call the random salt “the challenge” for reasons which will become apparent in a minute.

The server sends the user’s password salt and the challenge to the client. The client appends the password salt to the password and hashes the salted password. It converts the salted hash to a string, appends the string to the challenge, and hashes the resulting string to form the “response” hash. The response is sent across the wire.

The server then does the same thing – converts the stored salted password hash to a string, appends it to the challenge, and hashes the resulting string. If the response from the client is equal to the value the server just computed, then the client must have computed the same salted hash, and therefore knows the password.

Now what does the eavesdropper know? The eavesdropper knows the username, the password salt, the challenge and the response. The eavesdropper has enough information to launch an offline dictionary attack against that user. But since the random challenge is never going to be used again, the fact that the attacker knows a valid challenge/response pair is essentially irrelevant.

This system has the downside that an attacker who gets the password file has obtained password equivalents, so no dictionary attack is necessary. (Unless of course the attacker is trying to determine a user’s password in order to try it against the user’s account on a different system!)

Fortunately, these weaknesses can be mitigated somewhat by changing your password frequently, not using the same passwords for different accounts, never using common dictionary words as passwords, and making passwords long — passphrases are better than passwords.

---

This general challenge-response pattern is quite common in authentication systems that rely upon shared secrets, becauseat no point is the original secret password ever actually stored or transmitted! With such a system, a machine that does not know your secret can verify that you do know it — almost seems magical, doesn’t it? Of course, now that you know how it works, it’s not quite so magical — the salted hash is essentially the shared secret, and it is stored and transmitted.

Clearly we could go on, adding more and more layers of encryption to this system to further mitigate these vulnerabilities, but I’m going to stop here. Readers interested in ways to solve problems such as mutual authentication (where the server authenticates the client AND the client verifies that it is talking to the right server) or other heavy-duty authentication tasks should read this charming dialogue on the design of the Kerberos authentication system: https://web.mit.edu/kerberos/www/dialogue.html

The foregoing is of course just a sketch with lots of details glossed over and greatly simplified for didactic purposes. Real professional-grade authentication systems do not work exactly like any of my sketches, though several are quite similar.

Unix boxes used to typically use a 12 bit salt and hash it with a 56 bit password using a DES-based hash, for instance. That’s pretty weak! A 12 bit salt only makes construction of a dictionary take 4096 times longer — one dictionary for each possible salt. In modern systems the more secure MD5 hash is often used now, which supports arbitrarily large salts. Unix boxes also used to keep the user list in the clear, so that anyone could read the salted hashes of the passwords; nowadays the encrypted passwords are kept in a file that can only be read by the operating system itself — defense in depth!

NT by contrast uses an unsalted 128 bit MD5 hash to store the password equivalent, so it is susceptible to dictionary attacks should the password file be stolen. NTLMv2 is an authentication system based on some of the challenge-response ideas from System #5. It hashes the password, user name, domain, and current time in a fairly complex way; I’ll spare you the details. And of course, many NT and unix boxes use Kerberos-based authentication these days.

Last time we were considering what happens if an attacker gets access to your server’s password file. If the passwords themselves are stored in the file, then the attacker’s work is done. If they’re hashed and then stored, and the hash algorithm is strong, then there’s not much to do other than to hash every string and look through the password file for that hash. If there’s a match, then you’ve discovered the user’s password.

You don’t have to look through the vast space of strings in alphabetical order of course. An attacker will start with a dictionary of likely password strings. We want to find some way to make that attacker work harder. Setting a policy which disallows common dictionary words as passwords would be a good idea. Another technique is to spice up the hashes a bit with some salt.

System #3

For every user name we generate a random unique string of some fixed length. That string is called the “salt”. We now store the username, the salt and the hash of the string formed by concatenating the user’s password to the salt. If user Alpha’s password is “bigsecret” and the salt is “Q3vd” then we’ll hash “Q3vdbigsecret”.

Since every user has their own unique random salt, two users who happen to have the same password get different salted hashes. And the dictionary attack is foiled; the attacker cannot compute the hashes of every word in a dictionary once and then check every hash in the table for matches anymore. Rather, the attacker is going to have to re-hash the entire dictionary anew for every salt. A determined attacker who has compromised the server will have to mount an entire new dictionary attack against every user’s salted hash, rather than being able to quickly scan the list for known hashes.

Salting essentially makes it less feasible to attack every user at once when the password file is compromised; the attacker must start a whole new attack for each user. Still, given enough time and weak passwords, an attacker can recover passwords.

In this system the client sends the username and password to the server, the server appends the password to the salt, hashes the result, and compares the result to the salted hash in the table.

This answers the original question posed by the JOS poster; the salt can be public because it is just a random string. Ideally, both the salt and the salted hash would be kept private so that an attacker would not be able to mount a dictionary attack against that salt. But there is no way to deduce any information whatsoever just from the salt.

And of course, it’s better to not get into this situation in the first place — don’t allow your password list to be stolen! But it’s a good idea for a security system to not rely on other security systems for its own security. We call this idea “defense in depth”. You want to make the attacker have to do many impossible things to compromise your security, so that if just one of those impossible things turns out to be possible after all, you’re not sunk.

But what about the fact that the password goes over the wire in the clear, where anyone can eavesdrop? That’s now the weak point of this system. Can we do something about that? Tune in next time and we’ll see what we can come up with.

---

MSFT archive of original post is here.