talideon.com

• Home
• Weblog
• Linklog
• Wiki
• About
• Projects
• Concultures
• Notes
• Exeunt
• Contact

July 31, 2007 at 11:10AM Storing passwords as salted hashes is easy

I’ve done this umpteen times before, but I thought I’d might as well document the way I do this.

Most applications need to store passwords of some form or another. However, actually keeping a hold of those passwords in plain-text form isn’t a good idea because if your system is compromised and a cracker manages to get their hands on your accounts table, given that people tend to use a small number of passwords and will tend to use the same password for multiple different services, your users’ accounts on all those other services have been compromised.

You could try obscuring the passwords by using a hash function such as MD5 or SHA1, but you’re still left with a problem: password distributions tend to obey a power law distribution (which generally looks like an L-shaped curve), meaning there’s a small number of passwords or families of passwords that the vast majority of your users will choose. Given this, it’s relatively trivial to mount a dictionary attack to figure out what your users’ passwords are: once one person’s password has been worked out from the hash, any other users that have the same hashes have the same password.

To guard against this, you can include a cryptographic salt in your hash. A salt is simply a random string that gets appended to a password before you hash the password and is then stored as clear-text so that the salted hash can be checked later. Generally, the salt is appended to the hash. By salting the password hash, you manage to obscure identical passwords, which greatly mitigates against dictionary attacks.

To demonstrate its use, say you’re using the following schema for your accounts table:

CREATE TABLE accounts (
    uname  CHAR(24) NOT NULL,
    pwd    CHAR(40) NOT NULL

    PRIMARY KEY (uname)
);

The pwd field consists of a MD5 hash of the actual password and the salt, which makes up the first 32 characters, and the clear-text salt, which is the last eight. I’m not going to cover how you should generate the salt, but I will say that you should make every and all effort to ensure that each salt is unique and cryptographically random.

Here’s a MySQL stored function that will generate the salted password field given a password and a salt to use:

CREATE FUNCTION salted_password (pwd CHAR, salt CHAR)
RETURNS CHAR(40) DETERMINISTIC
RETURN CONCAT(MD5(CONCAT(pwd, salt)), salt);

Here’s a MySQL stored function that, given a salted password, will check if it matches the given actual password:

CREATE FUNCTION is_valid_password (salted CHAR, pwd CHAR)
RETURNS TINYINT DETERMINISTIC
RETURN SUBSTR(salted, 1, 32) = MD5(CONCAT(pwd, SUBSTR(salted, 33)));

As you can see, it partitions the salted hash in two parts, the first 32 characters being the actual salted hash, and everything from the 33rd character onwards being the salt. It then attempts to reconstruct what the salted hash would be given the salt we got from the salted hash and the password the user provided. If the two match, we’re good.

You’d use this to check against your accounts table as follows:

SELECT COUNT(*)
FROM   accounts
WHERE  uname = 'joebloggs'
  AND  is_valid_password(pwd, 'password');

If you can’t or don’t want to use stored functions, here’s what you’d do:

SELECT COUNT(*)
FROM   accounts
WHERE  uname = 'joebloggs'
  AND  SUBSTR(pwd, 1, 32) = MD5(CONCAT('password', SUBSTR(pwd, 33)));

Groovy.

Addendum

Ok, so I’d might as well throw a short note on how I generally generate salts. I usually construct my salts in PHP using this function:

function generate_salt() {
    return md5(uniqid(mt_rand(), true) . ':' . time());
}

And my password fields are usually 64 characters long. I haven’t done any work checking the quality of the salts from this function, but my gut tells me they’re relatively strong. YMMV, though seeing as the Mersenne Twister PRNG doesn’t generate cryptographically secure pseudo-random numbers, but the combination of other factors included should mask this. There are most likely much better methods than the one I outlined above and I’m no cryptographer, so go look at them first. I generally keep my authentication details, i.e., the username and password, separate from the account details to make sure each row is of a constant size, which keeps things fast.

Comments

module Main (main) where

import System.Random
import Char

main :: IO ()
main = do
    rands <- randoms 256 30
    putStrLn $ map chr rands where
        randoms :: Int -> Int -> IO [Int]
        randoms ceil count =
            let s = sequence $ take count $ repeat (randomIO :: IO Int) in
                s >>= \x -> return $ map ((flip mod) ceil) x

Validation: XHTML 1.0, CSS, Accessibility.

Information: About, Contacting, Syndication, Administration.

Generated in 234ms.

Copyright © Keith Gaughan, 2001-2008. All Rights Reserved.

Graciously hosted by Digital Crew.