For a rainbow table to work I need generate a large set of data, hash that data, then compare hashes with the compromised data. If the hashes match I return the value of the generated data.
Now at this point ignore the computational time and storage. If I do a brute force and compute hashes for the rainbow and notice the following:
JLKyuoTkWpu1nKzx24By0G45ACAQg9XvJIAbYXT0mo8= returns 12345678901234567890password
and
vwXZcCYEybvlfdm1xwOXnrXo0sWX+f634njY3SMVyaI= returns 12345678901234567890password2
If I could find just two or three numbers with the same salt then i would not have to calculate the entire space N character space. I can deduce that the salt is 12345678901234567890 since each number begins with it. Now that I know the salt i can begin doing dictionary attacks with the salt + 'dictionary word' or compute every possible combination of salt + alphanumeric characters.
One other thing I would like to point out is that if i could pre-calculate the entire space(salt + password) then I can identify collisions this way as well. If I notice a lot of numbers that begin with 12345678901234567890 and just a few that do not then the few that do not I can ignore as erroneous or try to find a match to a value later in the rainbow table.
Now I will point out possible hashing scenarios and what it would take to brute force them.
Scenario 1: Known salt, known passwords requirements.
Lets say I have compromised a database of sha1 password hashes with a password length that must be exactly 8 char alphanumeric. I know the salt so now I only need to calculate
64^8. I need to calculate 281474976710656 hashes. On my machine it takes 2.57952379422524 seconds to calculate 1,000,000 sha1 hashes. So I can calculate the entire space in .. 17.5713 years! Sounds like a lot but if I can recruit a bot net or distributed computing then I can take 100 machines to calculate the space in about 63 days.
Scenario 2: Different salt for every hash, known salt, and known password requirements. A much better way!
Now to figure out one password hash I need to compute the entire space with the unique salt to get one password. I assume here that the salt is public like the username or database creation date. Some value that is readily available from the compromised database So using the same logic as before but I will need 63 days for EACH password using a distributed computing system. This is much more time consuming to compute and therefore more secure.
Scenario 3: Unique salt that is long and algorithmically calculated for every hash.
Below is an example code of what I believe is a very secure hashing implementation based on Scenario 2 but with the salt algorithmically generated. It is written in c#. I use the username to generate a value that acts as a seed to a random number generator. I concatenate multiple generated random numbers to create my salt. Then prepend to the salt to the password before hashing. For a rainbow table to be computed and the algorithm to compute the salt is unknown the user would have to calculate roughly 64^45 possible combinations or more. Of course if the algorithm is known then the scenario is identical to Scenario 2. This code allows you to create very long yet unique salts for every password hash.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.Diagnostics;
namespace crypto
{
class Program
{
static void Main(string[] args)
{
string username = "ascetik";
string clearText = "password";
byte[] userBytes;
string salt;
byte[] saltandclear;
byte[] cipherText;
string hashedString = "";
//Generate the salt. This could be any algorithm you choose. I took
// the username, converted to a byte array, then XORed the bytes together.
// I took the xored result as the seed to my random number generator.
// Then i used the result of the PRG as my salt.
userBytes = ASCIIEncoding.ASCII.GetBytes(username);
long XORED = 0x00;
foreach (int x in userBytes)
XORED = XORED ^ x;
Random rand = new Random(Convert.ToInt32(XORED));
salt = rand.Next().ToString();
salt += rand.Next().ToString();
salt += rand.Next().ToString();
salt += rand.Next().ToString();
//prepend the salt to the clear text and convert to byte array
saltandclear = ASCIIEncoding.ASCII.GetBytes(salt + clearText);
Console.Out.WriteLine(“salt + password length:” + saltandclear.Length);
//compute sha256 hash
SHA256 sha256 = new SHA256Managed();
cipherText = sha256.ComputeHash(saltandclear);
Console.Out.WriteLine(Convert.ToBase64String(cipherText));
Console.In.ReadLine();
}
}
}
Conclusion
Using a unique salt, that is algorithmically created, for each hash could drastically improve the confidentiality of a system. I better way would be to run a mixing algorithm like a hash over the data and using the result as the password to hash or hashing twice. With this option even if all the hashes where matched to entries in the rainbow table the data would still be useless. But the con to this is that it could increase the chance for data collisions and is not recommended. I’ll leave this up to the crypto experts to figure out. It seems that for now that Scenario 2 and 3 are efficient mitigation against rainbow table and dictionary attacks attacks.
Explanation of numbers:
Alpha chars = 26
Upper and lower case chars = 2*26= 52
Numbers = 10
All Possible Alphanumeric with 8 chars = (52 +10)^8
All Possible characters that are exactly 8 characters in length = 62^8
 Slashdot It! |
Posts
