Password Miscelleania ~~~~~~~~~~~~~~~~~~~~~ Salting ~~~~~~~ If you've ever looked in a unix password file, you already know that passwords are not stored in as plaintext on your system. They are stored as a hashed version of your password, specifically a one-way, cryptorgaphically secure hash. In other words, if your password is "pwnz", it might be stored on a system using an md5 password file as "pwnz" -> 1b81df735c9b374439647f3ebed3457a This prohibits an attacker from finding out your password, but enables the system to verify you when you enter your password. When you enter "pwnz" into the login screen, the system hashes what you typed and compares it against the md5 stored in the password file. What could be simpler? This system is weak, however. The three main attacks are: * If 2 users both have the same password, it will become immediatley obvious to anybody browsing the password file. * When an attacker is using a dictionary cracking system, (s)he only needs to calculate the hash of a dictionary word once, and is able to compare it against all the users in the password file. * An organization of attackers could create a masssive database of md5 sums/password pairs, and simply preform a lookup of a password, not requiring any computation on the part of the attacker. The method used to prevent these attacks is known as "salting" the password. A piece of random data, the salt, is chosen along with the password when it is generated, or along with the user when his/her account is created. A hash might then look like this: "pwnz 28937" -> d38dca847a71d7585703278729b9cb08 But how does the system know what to use as a salt when validating a user? Well, quite simply, the salt is stored in plaintext along with the hash. So the entry in the password file might look like d38dca847a71d7585703278729b9cb08,28937 Is this secure? Yes, because if the hash function you choose is really cryptographically secure (which md5 is believed to be (by most people ;))) [1], knowing part of the text to be hashed gets you no closer to knowing the entire text. So what kind of values should be used for a salt? In truth, it doesn't really matter so long as the randomness is large enough so that it's unlikely that two or more users will be using the same salt. In other words, a few times more possible salts than local users should be sufficient. Some people have suggested using the username as the salt. While this seems reasonable, it is not as secure as it could be. It would still enable an attacker to build a large database of hashes for the "root" user or any other commonly used user name. "john", etc... Some people have suggested using the system's hostname as a salt. Under no circumstances should you listen to these people. Doing this completely defeats the first 2 stated purposes of a salt. A username/hostname combination would probably be OK security wise, but is not practical: If you changed your hostname you would invalidate your entire password file. The best bet is simply a randomly chosen number, the current time, etc. Understand that a salt doesn't need to be really random, it just needs to be unique enough among users that it highly reduces the practicallity of performing any of the 3 aforementioned attacks. Using Block Ciphers For Password Files ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Commonly you see block ciphers used for password protection instead of a one-way hash. DES was long the defacto password hashing standard, but now it is common to see, AES, Blowfish, etc used for password files. Thanks to D.J. Bernstein we know that cryptographically secure hash functions can be used as cryptographically secure block ciphers and vice versa. How does this work? Well, remember that with a secure block cipher it is impossible to recover the key without resorting to (expensive) exhaustive keyspace searches. This applies even if the attacker knows the plaintext and the ciphertext. So, in order to use a block cipher as password protection, we would choose the password to be the key and a known string to be the plaintext, and then store the ciphertext in the password file. So, if our block cipher is defined as B(key, plaintext) = ciphertext We might calculate a password entry like so B("pwnz", "this is a publicly known string") = dkjhgksfjhgjf Now, where should we put the password salt when using this scheme? Well, we could append it to the password as we did with the hash function, or, as it turns out, you could use the salt instead of the publicly known string, so: B("pwnz", "my_salt") = wioqwuiebhfob And store the password in the file as wioqwuiebhfob,my_salt I hope this file has been informative. Fractal [1] Actually, MD5 has been show to *NOT* be cryptographically secure in a number of cases, but is probably secure enough for most purposes: certainly password hashing. Even worse is that MD5 was designed to be FAST. A good password hashing function should be SLOW so that brute force attacks take longer.