Is knowing the salt a problem?

Question

I understand that adding a salt would thwart the use of rainbow tables.

I don't understand the time it would take to create a rainbow table for a certain salt and of course this is dependent on the password size limit you use, the salt size, the hash method and also the computational power. Therefore this question could just be irrelevant.

However, theoretically if someone had access to all salted rainbow tables for all passwords up to x characters and the salt up to x characters and the attacker knew the salts then this would make it possible retrieve the passwords wouldn't it?

Answer 1

The value of salt is not in its secrecy, it's in its differentiation and the added complexity. You've touched on this a bit.

First, two passwords hashed with different salts have different resulting hashes. Therefore, an attacker cannot look at a password table and discover users who share the same password.

Second, as you write, a rainbow table could be pre computed for a large set of password inputs, allowing fast, O(1) time, password recovery. However, this is often for unsalted passwords.

Third, the salt for a password hash is unique to that hash and should be the same size (bit length) as the hash algorithm. A single rainbow table is the size of all password inputs. Assuming 8 character passwords, case sensitive alphanumeric plus symbols (let's say 10 extra) so that's 72 characters. 8*log2(72) is about 50 bits. So, the rainbow table storage for sha-1 hashed passwords is 50+160 or 2^210 bits.

At 2^202 bytes of storage, that's already larger than all the current storage on the planet. I think we can conclude two things: 1) not all passwords are placed in a rainbow table and 2) unsalted rainbow tables are already fairly large.

Now, creating rainbows for every possible salt means requiring 210*160 or 2^33600 bits of storage. Where to put all that data (other universes) pales in comparison to the time required to create them (beyond the end of our universe).

Rainbow tables per salt ain't going to happen.

The proper attack is to capture the password database and run a dictionary attack against individual entries using the non-secret and password specific salts.

Answer 2

As has been said, it is theoretically possible but due to computational and storage limitations practically far beyond possible:

Calculating a rainbow table for the entire hash space of an hashing algorithm is impossible as pointed out here. Not to speak of larger hashes like SHA-512 or SHA3.

There exist rainbow tables for MD5 covering simple passwords (alphanumeric, up to 9 characters). But even then, storage space puts a stroke in your wheel:
these are about 600GB in size (as can be seen in the link). If a per-password random salt of merely 4 alphanumeric characters is used the size of a rainbow table of passwords and salts grows to 600GB * (26 * 2 + 10) ^ 4 = 5.3 Zettabyte (that is 5 Million Terabyte). It is not possible to store, yet to search that amount of data.

Answer 3

Yes it would, but this is computationally impossible as of today.

The salt technically expands your password by so and so random but known characters. You could therefore build a "salted rainbow table" with all passwords combinations up to n characters with, for each password, all salts of m characters (m is known). But this is not computationally feasible (calculations and storage).

Answer 4

Theoretically, yes, but you're going to run into storage limits.

As an example, back-of-the-envelope math:

• Passwords of length: <12
• Salt length: 32 bytes

salt&password combinations: 6x10¹⁰⁰ (~6x10⁸⁸ TB). The total storage capacity of all computers on the planet is roughly 10 zettabytes, or 8x10¹⁰ TB, so good luck storing this table.

I've also heard a rumour that having a 256-bit counter actually ++ from 0 to 2²⁵⁶ would consume more power than the sun, so uhh, you'd need some nice nuclear reactors to build that rainbow table.