Why people say that salt helps to prevent rainbow table attack?

Question

I am using some frameworks that store salts inside databases. For example this article shows how Devise stores salt together with the user information. My question is why do people say that salts prevent rainbow table attacks? I make this question because if I were the attacker and I had a "Devise table" then I might use both  1) the salt and 2) my table of passwords to create another table with that salt. Does it make sense?

Answer 1

Creation of rainbow table requires much resources to compute it and a lot of space to store the table. The main idea is that despite it costs much resources, it needs to be computed only once, then can be used many times. For instance, some web site or some application has 1 000 000 users. Suppose the password database contains "simple" password hashes without salt. Suppose the hacker has got this database with hashes. For using the system a real password needs to be obtained from the hash.

Knowing their algorithm, the attacker creates a rainbow table. Suppose the attacker has chosen such rainbow table parameters, that it took one day, 24h, on a single PC to compute it. But now the attacker can use this table for breaking any of the hashed 1 000 000 passwords in the database.

But if every password hash uses a separate random salt, then the attacker has to create a rainbow table for every password. This will cost essentially more time and resources, and makes no sense for the attacker.

The length of the salt is chosen usually so that the number of possible salt values is relatively big and the attacker cannot create a rainbow table for all possible values of salts.

The article that you refer describes usage of bcrypt. This hashing algorithm has 2 means against brute-forcing: It uses salt and it is computationally relatively expensive: it works much slower than fast algorithms like MD5 or SHA-512. Usage of salt makes creation of rainbow tables useless. Usage of expensive algorithm requires much more time and not only makes creation of rainbow tables even more expensive, but prevents also from the brute-forcing of separate passwords, because to test all possible passwords the attacker will need the computer power of the whole world for millions of years, which makes brute-forcing useless.