3

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?

  • Not exactly, the only way they could figure out the salt is if they see your source code, or if they figured it out through trial and error. The salt just makes it harder to figure out the password, but your security is only as strong as the weakest link (I.E. user's weak password). For the tables, they would most likely just keep a table of passwords (hashed or not). They can only use the salt if they can figure out how you are hashing your password, which in most cases will be because they have your source code (which contains your salt). Someone else can probably explain it better. – dakre18 Apr 5 '16 at 14:28
7

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.

  • This is assuming you're not using some chaining in the rainbow table. – d0nut Apr 5 '16 at 17:42
  • Fair enough. Worst case then. How much reduction can be expected with chaining? – Andrew Philips Apr 5 '16 at 17:43
  • @AndrewPhilips it depends on a lot of factors, actually. Depends on what function is used for building the chains, how deep they are, rate of collision, etc. Just figured I would add a comment noting that rainbow tables aren't just a complete dump of the search space :p – d0nut Apr 5 '16 at 17:45
  • Still, I can't imagine enough of a reduction to matter from a practical perspective. Nevertheless, agreed it would impact the numbers. – Andrew Philips Apr 5 '16 at 17:46
  • I don't know why you think salt should match size of hash output; no scheme I know recommends that except when the hash is too small already. Directly storing SHA1 for 2^50 passwords (which a rainbow table doesn't) is not 2^(50+160) bits but (2^50)x160 or about 20PB which is only(!) about USD10M -- but is unusable unless associative, which is much more. Storing lookup hints instead would be about 1/3 of cost, quite feasible. With 160 bits salt, it would be 2^(50+160)*50 bits and require a good chunk of one universe but not others -- our universe is about 2^267 atoms. – dave_thompson_085 Apr 12 '16 at 9:38
4

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.

  • The storage issue can be overcome by using rainbow tables. – Jacco Apr 5 '16 at 14:58
0

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).

0

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: 6x10100 (~6x1088 TB). The total storage capacity of all computers on the planet is roughly 10 zettabytes, or 8x1010 TB, so good luck storing this table.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.