I have a top level familiarity with Rainbow tables (1 ,2 )

I also understand that salting adds a randomly generated alphanumeric string to each password before it gets hashed and put in a database.

My understanding of Rainbow tables (RTs) is that instead of a Hash table that stores hash/password combinations, an RT stores the first and last entry in a plaintext/hash chain that is created by using a hashing function and a reduction function.

So the user can access the same plaintext/hash combinations as they could in a hash table, but they are instead computed and found somewhere along the chain.

I'm obviously missing a key factor here but my understanding is that if the searchspace within the combined chains is large enough to cover any 24 digit alphanumeric string, then could it not still include all 16 digit passwords + all 8 digit salts (contrived example to help understand theory)?

It makes sense that salts make everyones passwords different, but I don't understand what it is about them that renders a Rainbow table useless.

  • 1
    salt1+password is different from salt2+password. Or else your RT is the largest database in history.
    – schroeder
    Apr 29, 2022 at 14:24
  • @schroeder's comment is spot on (+1). To say it another way, when you concatenate the random salt with the password, then run the slat+password through the hashing function, you end up with a result that is not in the pre-computed rainbow table. So, the rainbow table is useless.
    – mti2935
    Apr 29, 2022 at 14:33
  • 1
    @mti2935 Thank you for explaining this, the gap is need to bridge mentally is the notion that if saltX+password could be any 8 + 16 digit alphanumeric string (contrived), then can the RT simply contain every 24 digit alphanumeric combination to account for all possible salts?
    – user277528
    May 4, 2022 at 8:46
  • Sure, but you would need a lot of storage. There are 62 possible alphanumeric characters (26 uppercase, 26 lowercase, and 10 digits), and you have 24 of these. That 62 ^ 24 possible combinations for each input, which mean you will have 1.04 * 10^43 records in your RT. Each record will contain 32 bytes for the hash, so the size of your RT will be 32^10^43 bytes. If you used 1TB drives to store the RT, you would need 32 * 10 ^ 31 drives. In other words, you would need 32 thousand billion billion billion 1 TB drives to store the RT.
    – mti2935
    May 4, 2022 at 10:14


Browse other questions tagged .