Help needed in grokking password hashes and salts

Question

I've read a number of SO questions on this topic, but grokking the applied practice of storing a salted hash of a password eludes me.

Let's start with some ground rules:

• a password, "foobar12" (we are not discussing the strength of the password).
• a language, Java 1.6 for this discussion
• a database, postgreSQL, MySQL, SQL Server, Oracle

Several options are available to storing the password, but I want to think about one (1):

Store the password hashed with random salt in the DB, one column

The automatic fail of plaintext storage is not open for discussion. :) Found on SO and elsewhere are solutions with MD5/SHA1 and use of dual-columns, both with pros and cons.

MD5/SHA1 is simple. MessageDigest in Java provides MD5, SHA1 (through SHA512 in modern implementations, certainly 1.6). Additionally, most RDBMSs listed provide methods for MD5 encryption functions on inserts, updates, etc. The problems become evident once one groks "rainbow tables" and MD5 collisions (and I've grokked these concepts).

Dual-column solutions rest on the idea that the salt does not need to be secret (grok it). However, a second column introduces a complexity that might not be a luxury if you have a legacy system with one (1) column for the password and the cost of updating the table and the code could be too high.

But it is storing the password hashed with a random salt in single DB column that I need to understand better, with practical application.

I like this solution for a couple of reasons: a salt is expected and considers legacy boundaries. Here's where I get lost: if the salt is random, and the password plus salt are hashed to produced a one-way value for storing, how can the system ever match a plaintext password and a new random salt?

I have theory on this, and as I type I might be grokking the concept: Given a random salt of 128 bytes and a password of 8 bytes ('foobar12'), it could be programmatically possible to remove the part of the hash that was the salt, by hashing a random 128 byte salt and getting the substring of the original hash that is the hashed password. Then re hashing to match using the hash algorithm...???

So... any takers on helping. :) Am I close?

Answer 1

See http://www.aspheute.com/english/20040105.asp

The user is authenticated with a salted hash, not the unsalted password or the random salt by itself. The salted hash and the salt (but not the actual password) are both stored in the database (you can store them in a single column if you like, but you will have to separate them again before use).

In order to recover the salted hash from the user (so that you can compare it to the stored salted hash), you need the salt from the database, and the password provided by the user.

The salted hash is created like this:

  // Initialize the Password class with the password and salt
  Password pwd = new Password(myPassword, mySalt);

  // Compute the salted hash
  // NOTE: you store the salt and the salted hash in the database
  string saltedHash = pwd.ComputeSaltedHash();

Authentication is done like this:

// retrieve salted hash and salt from user database, based on username
...

Password pwd = new Password(txtPassword.Text, nSaltFromDatabase);

if (pwd.ComputeSaltedHash() == storedSaltedHash)
{
   // user is authenticated successfully
}
else
{
...

A new salt is generated for each user. Should two users accidentally choose the same password, the salted hash will still be different for both user accounts.

Answer 2

You always have to know the salt, by storing it in the DB (as you saw with multi column solutions) or be able to generate it in some other way (which defeats some, but not all, of the point of random salt).

If you only have a single column in which to store the password, then you can either:

• generate the salt on the fly (ie not really random, but use some sort of function of the username or email address)
• concatenate the salt with the hashed password in some way before storing it.

In the first case, you can come up with some trivial function:

public String getSalt(String username)
{
  // assuming Hash returns a String
  return Hash(username + " 1234 my site is totally awesome").substring(0,16);
}

In the second:

// Passwords stored in the db as 16 characters of salt, and the rest is password hash
public boolean authenticate(String username, String authPassword)
{
  // 'SELECT saltyhash FROM users WHERE username=x'
  String saltyhash = getSaltyHashForUserFromDB(username);
  String salt = saltyhash.substring(0,16);

  String dbPassword = salt + Hash(salt + authPassword);

  // perform the actual 'SELECT FROM users WHERE saltypassword=x' stuff
  return hitTheDatabaseToPerformLogin(username, dbPassword);
}

public void createUser(String username, String password)
{
  String salt = createSomeAwesomeSalt();
  String saltyhash = salt + Hash(salt + password);
  createTheUserInTheDatabase(username, saltyhash);
}

Answer 3

You could also store salt and hash in the same column (using a separator).

Answer 4

Here's where I get lost: if the salt is random and hashed with the password, how can the system ever match the password?

It matches it by computing the hash of the password the user entered with the same salt, which it reads from the database (at the same time as the hash).

Answer 5

There's no great mystery. The single-column solution is just like the multi-column solution, except that it combines the salt and the hash together into a single column. The checking code still has to know how to break that single value down into the salt and hash. (This has been how salted passwords have typically worked - for example, the UNIX /etc/shadow format stores an algorithm identifier, salt and hash together in a single field).

You don't have to worry about this too much though, because the password hashing algorithm should include the smarts to do this. For example, if you use jBCrypt, then you simply:

• Store the string returned by BCrypt.hashpw() in the database password column when storing a password; and
• Supply the value from the database password column as the second parameter to BCrypt.checkpw() when checking a password.