You Want Salt With That? Part Three: Salt The Hash
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.
Comments
- Anonymous
February 03, 2005
Defense in Depth?
That would be, for example, not allowing a web browser to access operating system functionality? - Anonymous
February 03, 2005
Blobby, you could unplug your computer from the network if you want the ultimate security, but most people care about functionality more than security. So we as programmers need to provide the functionality with the best security feasible. - Anonymous
February 03, 2005
I believe Mr. Blobby is referring to running under least privilege. - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
Carlos - actually that user name would work as a "salt" value for your algorithm. But, you have the potential problem that if you change the user name through other means, you won't be able to successfully evaluate your hashed password anymore. - Anonymous
February 03, 2005
> What is the advantage os using "salt" over our algorithm?
You are using a salt, you're just using the user name rather than a random salt.
The problem with using user names is that they are highly predictable. And if they're highly predictable, that means that attackers can precompute large dictionaries of username-followed-by-password hashes which can then be used to attack the system.
Also, if you use a random salt then you can choose how much entropy is added to the password by choosing the salt length. - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
You obviously have a good understanding of the basics of security design, Eric. Why doesn't Microsoft actually implement such designs?
Why does so much of Microsoft's own software require administrator access to run when it could easily be adapted to only affect userspace, thus encouraging people to run as Administrator? Why does XP default to 'Administrator' status when setting up a new account?
Why does IE need to access operating system functionality?
Why is there no easy, simple way for a user to securely encrypt a file or directory for themselves?
XP SP2 had security-focus and did quite well, but the underlying principles need changing. Yeah, I'm sure it will all be rosy in Longhorn, if it ever comes out... - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
Mike's comment raises an extremely important point about encryption. Encryption is EASY, but KEY MANAGEMENT is a pain in the rear!
There's no easy encryption because encryption is not a simple panacea. To use encryption correctly you need to understand what is being encrypted, why, for how long, what attacks are likely, how you're going to manage the keys, blah blah blah blah blah. It is just fundamentally a really hard technology to use correctly.
Part of secure design is understanding your users. Users are not professional cryptographers. They don't understand what they want, they don't understand the attacks, they don't understand any of that stuff. All they understand is "encrypted = safe", which is not even true.
You can't just build a general-purpose arbitrary-algorithm encryption system into a consumer-grade operating system and hope that people use it correctly, because they won't. You have to very carefully look at the scenarios in which they will use it, and design a system which meets those requirements, and steers people down that path. The encrypting file system meets the needs of a very large segment of our customers and has a reasonably misuse-proof key management system so that's where we focused our efforts. - Anonymous
February 03, 2005
Fabulous Adventures in Coding assays this week a, well, fabulous adventure, in simple cryptography. I know enough to get myself in deep trouble with this subject, but Eric has put together three short and knowledgeable posts that begin easy and... - Anonymous
February 03, 2005
Thanks for pointing out the encryption thing, I didn't realise! </blush>
Regading IE, I don't mean the process itself, I mean the way ActiveX controls can have control beyond the application.
Regarding (for example) Visual Studio: Why do you need an Administrator account at all? Why not have a set of granular privileges, and something like su? SELinux is a start in the *nix world but still unfortunately not widely deployed. It's excellent to hear it's a priority.
Linux certainly does have the capability to set group level privileges, but I get your point - yes, it has a lot to learn about security too. I reject the notion that (for example) RHES isn't enterprise ready, but that is irrelevant here. Why should that stop me pointing out (what I perceive to be) weaknesses in Microsoft security? - Anonymous
February 03, 2005
<slightly off topic>
Mike: That was a great summary on how encryption is implemented in Win 5.x. I've always wondered how it was that transparently implemented.
Eric: you're right, the easier the feature is to use, the harder it probably is to implement.
</slightly> - Anonymous
February 04, 2005
This is slightly off topic, but still related to cryptography.
One of the most impressive cryptography things to me is the widespread use of SSL, and the encryption technology it's built upon. What do you think it would take for secure email to become a reality? Somthing like all email clients managing keys seemlessly, and all email was encrypted.
Are the biggest hurdles encryption, key management, adoption, or something political like it makes the NSA's job harder? - Anonymous
February 05, 2005
To clear up some misunderstandings about EFS:
On Win2k by default an administrator will have a recovery key for encrypted files.
There is no EFS on XP Home Edition.
On XP SP1+ and Server 2003 the default symmetric algo is AES 256 (much better than DES).
An unfortunate side-effect of the way EFS converts from plaintext to ciphertext is that a plaintext copy is left on the raw volume. You ucan use "cipher /w" to wipe clusters that aren't in use. And we recommend marking a folder for encryption and creating your files inside it - we don't do the conversion in this case so there's no risk of plaintext lying around in freed clusters.
There seems to be some stale or even misleading advice about EFS on the web. Not only on 3rd party sites, but also here on the mothership. This looks fairly accurate:
http://support.microsoft.com/kb/223316/EN-US/
And this is informative:
http://www.microsoft.com/resources/documentation/Windows/XP/all/reskit/en-us/prnb_efs_qutx.asp
But even those seem a little outdated. The former has dead links and the latter is before we added AES (3 years ago?). Frankly it's a little embarassing. - Anonymous
February 07, 2005
An interesting alternative way to do this is embedded in the RADIUS protocol - there is a shared secret between the RADIUS server and each RADIUS client, and when users request authentication, their password is hashed together with the shared secret, producing a similar effect, but essentially eliminating the random challenge step in favor of a single secret exchange that is done offline.
This has its pros and cons, of course. More can be read in RFC 2865 (http://www.faqs.org/rfcs/rfc2865.html). - Anonymous
May 24, 2007
The comment has been removed - Anonymous
September 06, 2007
A recent question I got about the .NET CLR's hashing algorithm for strings is apropos of our discussion