PHP Password storage with HMAC+nonce - Is nonce randomness important?

Question

A few years I asked here on stackoverflow about how to make PHP password storage safe. The main answer suggests using the following hashing algorithm:

function hash_password($password, $nonce) {
  global $site_key;
  return hash_hmac('sha512', $password . $nonce, $site_key);
}

The answer suggests using a random nonce. Is there any advantage in having a random nonce over simple unique nonces?

For instance, each user can have its own ID which does not change. However, let's assume user IDs are sequential(built with MySQL's auto increment feature) and therefore not random. Would the user ID be a good nonce or is randomness important?

Now, each user can pick an username. Each user has its own username which does not change, and two different users can't have the same username. Usernames are still not random, but they aren't sequential either. Would usernames be good enough as a nonce? Would it be better than using the user ID?

Answer 1

THIS IS ALL ON THE ASSUMPTION THAT A NONCE IS A SALT...

If by nonce you mean a salt then yes that requires more rainbow tables to be made. Usually once salt over 20 characters suffices, but for extreme security conditions you would want a new random salt for each password.

Also good choice in a slow hash http://www.php.net/manual/en/function.hash.php#89574, no sarcasm. But I like ripemd.

Didnt see the bottom half of your response. To elaborate: Nonces are used to prevent the use of rainbow tables. Whether the ID's would work depends merely on the length of the IDs. Randomness is not technically important, but just makes more rainbow tables required. An example would be, lets say you used a character "a" as a nonce and the password were 2 characters long, a rainbow table of a-aa, a-ab a-ac and so on would have to be created. If you use a random one each time maybe all the permutations of 'a' would have to be done + all the permuatations of the other random characters.

But in general making rainbow tables take quite a long time. So if you come up with a salt thats long its likely the rainbow table for it doesnt exists.

Answer 2

I found that there was a fairly nice tutorial written online about this topic. I don't quite remember where on google I found it but let me see if I can break the function down well enough myself as it is right in front of me...

First the function, it can create a key length of any size. I took the liberty of commenting it fairly heavily...

function pbkdf2($password,$salt,$iter_count = 1500,$key_length = 32,$algorithm = 'sha512') 
{
    /*
      @param string password -- password to be encrypted
      @param string salt -- salt to encrypt with
      @param int iter_count -- number of times to iterate blocks
      @param key_length -- length of key to return
      @param $algorithm -- algorithm to use in hashing

      @return string key
    */

    //determine the length of the hahs
    $hash_length = strlen(hash($algorithm,NULL,TRUE));
    //determine the number of key blocks to compute
    $key_blocks = ceil($key_length/$hash_length);
    //initialize key
    $key = '';

    //create the key itself
    //create blocks
    for($block_count = 1;$block_count <= $key_blocks;$block_count++)
    {
        //initalize hash for this block
        $iterated_block = $block = hash_hmac($algorithm,$salt.pack('N',$block_count),$password,TRUE);
        //iterate blocks
        for($iterate = 1;$iterate <= $iter_count;$iterate++)
        {
            //xor each iterate
            $iterated_block ^= ($block = hash_hmac($algorithm,$block,$password,TRUE));
        }
        //append iterated block
        $key .= $iterated_block;
    }
    //return the key
    return substr($key,0,$key_length);
}

1. First thing it does is figure out the length of the hash.
2. Next it determines how many key blocks are required for the key length specified
3. Then it initializes the hash (key) to return
4. sets up the for loop that will create each block
5. takes the initial hash of the block with the block counter in binary appended to the salt
6. begins the loop to iterate the block $iter_count times (create a hash of itself)
7. XOR each iterate and append it to $iterated_block (xor previous hash to current)
8. XOR loop finishes
9. append $iterated_block to $key for each block
10. block loop finishes
11. return the key

I feel this is probably the best way to do this. Maybe I am too paranoid?

Answer 3

For storing password enough to use:

sha512(salt + password)

salt should be random and unique for each user. Random salt will make precalculated hash tables attack impossible: each user will require his own calculated hash tables. If you'll use not random salt, then chance that precalculated table exists will be higher.

Position salt before password will help to hide hash patterns in case some users have same password.

Nonce is not needed, because it is for prevention a reply attack. This protection is not possible in your architecture.

Using HMAC to prevent collisions is useless, because a) we use hash not for MAC, b) to make probability of collision 50% for SHA-512 you need to calculate about 2^256 values. And 2^256 is truly astronomical number.