Finding a decent explanation of rainbow tables was something I struggled with, so firstly I'll cover what they are. I will get to your question in the end. My sources for this are this guide and the wikipedia article.
Why can't I just use a big bucket of hashes?
Firstly the naive way to build a reverse lookup table is this. Let's say we want to generate all the hashes for every 8-digit password in existence, using the set [A-Za-z0-9]. In that case there are 62 unique characters and with that, using the counting function $n^r$ where $n$ is the possible number of outputs and $r$ is the number of choices we can make, then there are $218340105584896$ possible strings in this output space. Navely storing this data we can take a 8 character string as taking 8 bits per character (so each string costs 64 bits) plus a separator character plus the 256-bit output of say sha256, the total cost is then $218340105584896(64+1+256) = 70087173892751616$ bits. Converting that to bytes, i.e. $\frac{70087173892751616}{8*(1024)^3} \approx 8159220$ gigabytes.
Two notes on this:
- It only considers exactly 8-character passwords. If you want to consider passwords containing 4-8 entries, you need $62^4+62^5+62^6+62^7+62^8$.
- It assumes you're actually going to store that data in raw form. There are probably better ways to handle this.
So the first problem is storage. Above, we simply computed the total output space of a hash function.
What is a rainbow table?
The idea behind rainbow tables is to offset the space issue. To this end, let's define a few things: firstly we have a search domain we'll call $\mathbb{P}$ and a hash output domain we'll call $\mathbb{H}$. Then we have a hash we want to invert we'll define as $\mathcal{H}: \mathbb{P} \rightarrow \mathbb{H}$. i.e. the hash function takes an element of the search domain and produces a value in the hash output domain.
We then introduce a concept called chaining. To do this, consider we could define a function that maps the other way fairly trivially; let's call it $\mathcal{R}: \mathbb{H} \rightarrow \mathbb{P}$. In a rainbow table, a chain starts with a starting value and applies $\mathcal{H}$ then a $\mathcal{R}$ alternately, but always in pairs such that when done you end up with the first and last elements $p_0, p_k \in \mathbb{P}$. This is what you store.
A rainbow table is slightly more complicated than using the same $\mathcal{R}$ for each pair; this has problems relating to collisions. If two chains produce the same value they converge, meaning we waste time spend computing said chains - this is a chain collision. I had trouble visualizing this, so drawing a diagram:
a_1 ----> a_2 ----> a_3 / b_2 --> a_4 / b_3 --> a_5 / b_4 ---> a_6 / b_5
| |
b_1 --------------------- -----> b_6.
Instead, a set of functions $\{\mathcal{R}_0, \ldots, \mathcal{R}_{k-1}\}$ are applied, one for each pair of the chain. SO when chains merge using this setup, they always produce the same final value and can then be de-duplicated, saving space - detection of wasted space is also much easier on generation.
Then:
- Generating rainbow tables: pick a length $k$ and define the functions $\mathcal{R}_{0}, \ldots, \mathcal{R}_{k-1}$. Then, for a given input $p \in \mathbb{P}$ we compute $c_0 = p, c_{n+1} = \mathcal{R}_{n-1}(r_{n}), r_{n} = \mathcal{H}(c_{n})\;\;(n=0,1,2,\ldots, k)$. These $c$ form a chain $C$. We compute our chains and for each chain we store just the pair $(c_0, c_k)$.
- Searching a rainbow table. Now, assume we want to inverse a hash value $h$. To do this we run through this process, starting with $i=k-1$:
- Generate chain for $h$ starting at $R_{i}$
- Using the end-value of the above chain, search our list of end values for computed chains. If we find a matching end-value, compute its chain term at a time (we can do this because we know the start value). If we find $h$ as say $r_n$ in that chain then the corresponding $c_n$ value is the inverse of $h$. Stop. If we don't find the end value in the chain list, carry on. If we don't find the hash in a generated chain where we did find the chain value, carry on.
- If $i \neq 0$ do $i=i-1$ and go back to 1.
- If we get here, we haven't found the inverse.
Right so exactly what is the benefit?
It's a space/time trade off. Specifically, the reverse lookup table takes a lot of space. This is a scheme that takes less space, but requires more time per lookup to work. Since the size of a complete reverse table is prohibitive for most people, the increased computational cost is generally preferable. Storage space is reduced massively, but is actually harder to calculate as it depends on $k$, and the $\mathcal{R}$ you use.
Clearly, also, we have different options with rainbow tables in terms of the length of $k$. The longer $k$, the fewer the number of total chains before all elements in $\mathbb{P}$ are covered. However, that also increases the run time of a lookup.
Oh no, now I have no idea how salt comes into this?!
Salt increases the size of $\mathbb{P}$ by increasing the $r$ in $n^r$. This makes both an inverse hash list astronomically big and also increases the size and computation time required for a rainbow table, too.
An attacker then has two options:
- Produce a rainbow table specific to a given salt, making it invalid for a different salt.
- Produce a huge rainbow table.
And what about slow hashing functions?
So far we've mostly talked about space as a consideration, without regards to the time taken to look up a function. Most cryptographic hashes are designed to be fairly quick, so this is ultimately feasible to do for say MD5.
Now what happens if we choose $\mathcal{H}$ which we know takes approximately a second to calculate each hash? Assuming there are no shortcuts that remove this additional time cost, the giant inverse table will take $218340105584896$ seconds, or approximately $6923519$ years. Your rainbow table is going to take a long time to generate too - assuming you never have collisions and cover the whole domain, just as long as a hash reverse lookup, plus added cost to search, depending on the length of $k$.
Combining both is a fairly effective defense against a rainbow table, making it both specific to a given salt and expensive to generate and use.
Why do password policies mention things like character classes, e.g. must have an upper case, must have a piece of punctuation?
We defined $\mathbb{P}$ as the set [A-Za-z0-9]. If you add punctuation into the mix you increase the size of $\mathbb{P}$ again, and so increase the size of the rainbow table (number of chains needed) again. Password length requirements also do this.
So dictionaries?
The whole premise behind a rather famous XKCD comic is the idea of information entropy. To tread roughshod over a fairly interesting area of science (sorry!) basically what you say is that whilst the total permutations of $\mathbb{P}$ are large, actually, quite a lot of those are totally meaningless to humans and we would not, given a choice, use them. Said XKCD comic was saying that actually, if you make certain judgements about the likely format of passwords, using information entropy as a measure of uncertainty within these formats then longer pass-phrases actually score better than shorter complicated passwords.
There is no reason you cannot produce a rainbow table using a set of reduction functions that takes this sort of assumption into account.
A dictionary is just a simplified version of this guessing - namely you're making the assumption that the thing you are inverting is actually a known dictionary word. You could also generate a rainbow table with known dictionary pass-phrases.
In both cases you are reducing $\mathbb{P}$ which by extension decreases the size of the rainbow table and the time to perform a lookup; however, such a technique is susceptible to the fact your approximate representation of a password just might not be right.
What's the complexity of rainbow tables?
Suppose we want to build a rainbow table to cover a set of $N$ potential passwords. (In other words, $N = |\mathbb{P}|$.) Let $t$ denote the average chain length; this is a parameter that you can choose freely, to optimize the cost of the attack.
Then, the cost of building the table is about $1.7N$ hash computations (yes, it is 70% more expensive than a simple exhaustive search on the set). The storage cost is $N/t$ elements of size at least $\lg N$ (but not necessarily much bigger). Attacking a password has cost about $t^2/2$ hash computations, and $t$ lookups (a "lookup" is when you are actually looking for data in the harddisk; it is typically much slower than a hash computation).
