Can you help me with some misconceptions about bcrypt and salting?

Question

I researched password hashing and cracking and I have some misconceptions:

First rule of thumb to create a strong password is to use 10+ combination of digits/upper/lower/symbols to prevent brute force attacks. Then the problem will be only if the password is a member of a pre-made table (whether it was long or short password).

Let's say the password is QWERTY and assume that:

Hash(QWERTY) = $$$$

User1: Hash(QWERTY+134565654) = ####

User2: Hash(QWERTY+876964786) = &&&

And let's think about how salt will help:

For brute force:

The unsalted one $$$$ is easy to brute force

The salted ones #### and &&& are harder to brute force because they are longer and even if they were brute-forced the hackers won't know the password unless they have the salt

For rainbow tables:

The unsalted one is easy to look in rainbow table with $$$$

The second one when you look for a rainbow table for #### you won't find anything

For rainbow tables, if the hacker has the salt when he broke the database: The hacker has #### and has 134565654 The hacker will need to implement a new rainbow table for all the known passwords with appending 134565654 to them until he finds that #### matches QWERTY+134565654 and knows the password

Since every user has their own salt, cracking User1 password from creating a 134565654 specific rainbow table, won't help the hacker to know that User 2 has the same password, so the hacker will need to do another 876964786 specific rainbow table for this user

It takes longer time to crack 1 password but isn't it still feasible with modern GPUs allowing to create fast Rainbow tables?

For Bcrypt:

Unlike the previous example (where the salt would be stored in a separate column for example) bcrypt computes the salt through rounds (say 10), so it runs the slow bcrypt hashing algorithm 10 times on the password before storing in the database and before verifying user login.

Since the bcrypt algorithm is known, why wouldn't hackers create a bcrypt rainbow table for each round? So this way they will create just 31 bcrypt rainbow tables for the common and short lengths passwords?

If what I'm saying is true, does this mean that salting helps only against brute force without salt value exposed, but doesn't really help against strong GPUs with the salt value?

Answer 1

The salted ones #### and &&& are harder to brute force because they are longer and even if they were brute-forced the hackers won't know the password unless they have the salt

Brute forcing is commonly an offline attack. For online attacks the time it takes for password verification are generally too long. Moreover, countermeasures should be in place to disallow a high number of guesses (maximum retries, deliberate delays).

The offline attack is generally over the hash and the salt, because they are stored together in the database.

The extra size of the salt (which is commonly mixed in differently than simple concatenation) should not be seen as much of a hurdle.

The unsalted one is easy to look in rainbow table with $$$$

Well, if the password is indeed really strong, then it may be that the rainbow table doesn't contain it, so it might fail.

The second one when you look for a rainbow table for #### you won't find anything

Indeed, not if you don't have a rainbow table for a particular hash.

It takes longer time to crack 1 password but isn't it still feasible with modern GPUs allowing to create fast Rainbow tables?

You're missing the point here. Rainbow tables are useful for matching multiple passwords against the rainbow table. Rainbow tables are useless to check only one password against. If the salt is unique (e.g. if you use a 128 bit random salt) then rainbow tables have no use.

Rainbow tables make it possible to efficiently store a hash -> password table. The adversary still has to create it by hashing each password guess separately.

Since the bcrypt algorithm is known, why wouldn't hackers create a bcrypt rainbow table for each round? So this way they will create just 31 bcrypt rainbow tables for the common and short lengths passwords?

The input for finding a password in a rainbow table is the hash output. The intermediate hash outputs of the rounds before the last one aren't stored. So how would you lookup a password using them?

If what I'm saying is true, does this mean that salting helps only against brute force without salt value exposed, but doesn't really help against strong GPUs with the salt value?

No, salting does not help against brute force but it helps against rainbow tables.

---

If you use a secret as part of the salt it is called a pepper. The pepper can act as a symmetric key; as long as the pepper contains enough entropy then there is no way to check if a password would create a specific hash. A 128 bit / 16 byte pepper generated by a secure random number generator should contain enough entropy.

Answer 2

The misconception is in how rainbow tables work. A rainbow table is not an optimization that allows cracking one password faster. It's an optimization that allows cracking many passwords quickly, but with a huge upfront cost. More precisely, a rainbow table is a storage technique that makes this optimization possible.

How to attack one password knowing its hash:

1. Calculate hashes of candidate passwords until one matches the given hash or until the search has taken too long. The crack is successful if the password is found before giving up.

How to attack many passwords using a rainbow table:

1. Calculate hashes of a predefined set of candidate passwords, storing them in the rainbow table.
2. For each hash to be cracked, look it up in the rainbow table. This is successful if the password is one whose hash was calculated and stored in the table.

The cost of step 1 is the worst-case cost of a direct attack on one password: you have to do all the calculations, you can't stop early on a match because you don't know what to match against yet. So this method only helps if you're attacking many passwords, and the high one-time cost of step 1 is compensated by the low cost per password of step 2.

Calculating a hash means running the hash function with all its inputs, including the password and the salt if there is one. For a direct attack, there's only one salt value since it's given with the hash. For a rainbow-table-based attack, step 1 has to consider all candidate passwords combined with all candidate salts. Even a relatively small salt, like 64 bits, is enough to make step 1 unfeasible.

GPUs are not a game changer for password cracking. Password hashes need to be slow and salted, regardless of what hardware the attacker is going to use. Where GPUs matter is in how to design the slowness for the most effectiveness.

For a good high-level explanation of how rainbow tables work, read What are rainbow tables and how are they used?. For more technical information, read How can rainbow tables be used for a dictionary attack?.

For a good high-level explanation of password hashing, read How to securely hash passwords?. For more information on the impact of GPU, see Do any security experts recommend bcrypt for password storage? .