How does using salt reduce rainbow table attack?

Question

I could create a rainbow table for a particular salt value and still create a successful attack similar to one without salt value.

Answer 1

The point of a rainbow table for password cracking is to allow attacking multiple password hashes with only a little less work than for cracking a single password hash.

Building a rainbow table takes about as much time as worst time for cracking a single password hash (just calculating the crypto operations, not the table overhead). This is about double the time of the average cracking time, assuming an equal distribution.

This means for attacking a single password, a rainbow table only has the advantage that it can be build before we actually know the hash that is searched. A rainbow table only really pays when attacking multiple passwords, since the lookup is quite faster than building the table (the actual lookup time depends on the space used for the table).

When we build a new table for each single salt, we lose both advantages – we can't build the table before knowing the salt, and we can't use it for more than one password (assuming the salt is unique). So you still can attack a salted password with a rainbow table, but this is more costly than attacking it directly – in other words, a rainbow table is useless.

Answer 2

Let's say you have enough computing power to calculate the MD5 hashes of all 7 character passwords using the 95 characters commonly found on a US keyboard¹.

There are $95^7\approx2^{46}\approx7\cdot10^{13}$ such passwords. Since every MD5 hash is 16 bytes long, you'll need approximately $7\cdot10^{13}\cdot16\approx1.1\cdot10^{15}$ bytes (i.e., $1120$ TB) of storage to store them all (slightly less if you store them cleverly).

You only have to do the work ($2^{46}$ MD5 computations) once, and at the expense of $1120$ TB of storage, you can crack every 7 character password ever generfated that's simply hashed using MD5.

A slightly better would be using a salt concatenated to the passwords before storing them. A pre-computed rainbow table will be useless if the salt is long enough. For a 64-bit salt, a rainbow table useful for cracking those 7 character passwords work require $2^{46}\cdot2^{64}=2^{100}$ MD5 computations to be created and approximately $1120\cdot2^{64}\approx20000000000000000000000$ TB of storage.

Of course, cracking all 7 passwords in a database will still take only $2^{46}$ MD5 computations (and negligible storage) if the same salt is used for all passwords. That's why a different salt should be used for every password. This way, every password needs roughly $2^{45}$ MD5 computations² to be cracked.

---

¹ Used as base for computations to show how incredibly weak 7 character passwords become if they're stored this way. But even if stored as a salted hash, 46-bit passwords are still pretty weak.

² Statistically, you'll need to try only half of them until you find the right one.