Passwords hash protection against "Rainbow tables" reverse engineering with password padding

Question

I've come across this article describing the dangers of storing "unsalted" password hashes in the database that could be subject to reverse engineering with the use of so-called "Rainbow tables".

It also comes with this C# code sample that basically requires storing two hash columns in your user passwords database table (instead of a traditional - one.) The issue of such approach for me is that I already have an established database table with unsalted user password hashes, and adding a new column will require restructuring of the database. So before I do that, I was looking for a different alternative and here's what I came up with.

Here's the function that instead of plainly calculating the SHA1 hash on a password pads it with a long sequence of pseudo-random (but consistent) data and then calculates the hash:

byte[] computeSecureHash(string strUserPassword)
{
    //RETURN: = SHA1 byte array on the 'strUserPassword'

    //Make simple junk array based on the password
    ushort v = 117;
    byte[] arrJunk = new byte[24];
    for (int c = 0, i = 0; i < arrJunk.Length; i++)
    {
        v ^= strUserPassword[c++];
        v *= 7;
        arrJunk[i] = (byte)v;

        if (c >= strUserPassword.Length)
            c = 0;
    }

    //Make crypto byte array based on the password
    Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(strUserPassword, arrJunk);
    pbkdf2.IterationCount = 1000;
    byte[] arrCrypto = pbkdf2.GetBytes(128);

    //Pad actual password
    string strUserPassword_Padded = "";

    const string strChars2Use = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ`-=[]\\;',./~!@#$%^&*()_+{}|:\"<>?";
    int nHalfArrCrypto = arrCrypto.Length / 2;

    //Left side
    for (int i = 0; i < nHalfArrCrypto; i++)
    {
        strUserPassword_Padded += strChars2Use[arrCrypto[i] % strChars2Use.Length];
    }

    strUserPassword_Padded += strUserPassword;

    //Right side
    for (int i = nHalfArrCrypto; i < arrCrypto.Length; i++)
    {
        strUserPassword_Padded += strChars2Use[arrCrypto[i] % strChars2Use.Length];
    }

    //For user's password "123"
    //the 'strUserPassword_Padded' becomes:
    //"bwDR]_B>H5t-k:eIq?r_wGBWqWfs#tcAE~DQ5?(Pbj#<+Cw:9(r!B[f_.S<pCjn-123b9l3<Sz^D~>G}v)?NuHT4BZ-pI2$W[kW1e4KO\"`rTg3H`}&jmtrFh1J5c72:})tQ"

    //And now compuse SHA1 on the padded password
    SHA1 sha1 = new SHA1CryptoServiceProvider();
    byte[] bytesInputData = System.Text.Encoding.UTF8.GetBytes(strUserPassword_Padded);
    return sha1.ComputeHash(bytesInputData);
}

So my question is, can someone review this code and tell me what are the dangers of doing it this way vs. what the author suggested in his code? In case of my code sample, I'll have to store only one hash in the database instead of two (password hash + salt hash.)

Answer 1

A salt that's solely derived from the password is close to pointless; you've just created a slightly different (but constant) hash function overall. A single rainbow table (albeit a custom one) could be used to target your entire database.

Furthermore, if a salt is derived from the password then identical passwords show up as identical "password hashes". Easy passwords will likely show up as duplicates - in effect you are generating your own rainbow table.

The whole point of storing a unique, independently-generated salt for each password is so that every single password is hashed with a unique hash function. Therefore there would be no single rainbow table that could be used across your entire database.

Answer 2

This will only partially mitigate the problem. What you have done is essentially created a keyed hash function.

With such a function general rainbow tables will no longer be applicable, but you are still in danger if an attacker gets ahold of your entire database. In this case, he can create a new rainbow table based around this random string. Using this new table he has a high chance of breaking into at least one account in your system.

Adding a separate salt is the equivalent of using a different hash function for each password, thus you would need a separate rainbow table for each possible salt, making the attack extremely expensive. If an attacker creates a rainbow table for one salt he only can break passwords that salt.

Also, I wanted to point out that it doesn't matter how much "static" randomness you add if the randomness remains constant.

Answer 3

The junk is derived from password so it doesn't have a salting effect, a rainbow table can still be generated that could be applied to your entire table.

But if you want to use just one column the answer is simpler:

Just use pbkdf2 to make your hash directly, make a 64 bit (8 byte) random salt, Use a higher iteration count (4000-10000). If you column can only hold 160 bits (20 bytes) then generate 12 bytes (if your column can hold more i'd up it more to 24 bytes) and store in your column salt + hash concatenated.

Thus when you are comparing you just read out the first 8 bytes to get your salt.

Answer 4

You can always take the current databases hashed passwords and hash them again with a different hash algo+salt, just as if they were the original password. It is perfectly safe to layer hashing on top of hashing, in fact it's often more safe this way. Keep in mind though that you also have to be able to reverse the process or you will break things.

Answer 5

restructuring of the database to just add an salt field is better option (or the only one really if your going to do it properly, but you could use your currant hash field to store the salt, as other person posted)

when they next log in with an valid user name and password (as this is only when the password hash should change or you do mass force change password on every one) if there is no Salt data then generate large random salt save it and regenerate the hash from the password+salt (ideally using something better then SHA1, pbkdf2 needs to be set higher then 10,000 but depends on your server resources)