# How can rainbow tables be used for a dictionary attack?

I'm putting together a password policy for my company. I very much want to avoid requiring complex passwords, and would much rather require length.

The maximum length I can enforce is 14 characters. I can calculate that 14 random lower case characters is stronger than 8 characters using anything on the keyboard. However I'm suggesting that people use phrases, song titles, things like that.

I don't think I need to protect against someone guessing passwords since our system will lock you out after 5 failures. I imagine I'm protecting against someone stealing the hashes of our passwords. Thus I imagine the mode of attack, if there was one, would be via rainbow tables.

I think 14 random lower case characters is reasonably safe against rainbow tables (we have Windows Server 2008 which I understand eliminates the LM compatibility weakness). However if phrases are used, there are many less possibilities than random characters would have.

Does anyone know if rainbow tables can be designed in conjunction with dictionary words, say by tokenizing them?

Along with this, I believe that NTLM passwords are hashed but not salted - does anyone know if that is true? If it turns out that they're salted, then I think I have little to worry about.

-

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:

1. 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$.
2. 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$:
1. Generate chain for $h$ starting at $R_{i}$
2. 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.
3. If $i \neq 0$ do $i=i-1$ and go back to 1.
4. 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:

1. Produce a rainbow table specific to a given salt, making it invalid for a different salt.
2. 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).

-
About salts: the effect of a salt can be seen as: we do not have one hash function, we have one per salt value. There is not a single hash function but a family of hash function, and the salt value tells you which family member is actually used. When you build a table, you do it for a given hash function; it cannot be used for any other. –  Thomas Pornin Oct 26 '11 at 12:54
You could include the complexity: a rainbow table covers a set of N potential passwords. Let's call t the average chain length. Then, the building cost of the table is about 1.7*N (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 log 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). –  Thomas Pornin Oct 26 '11 at 13:00
400 GB is cheap, I can have 5 times that much storage space for 100$. You may want to crank up the numbers a bit by considering 8-character passwords; they would look more impressive. – Thomas Pornin Oct 26 '11 at 13:08 @ThomasPornin Ok, I'll make it more impressive...! That's not a bad way of looking at it, but I like to remember that it is possible to build a rainbow table incorporating all possible salts too (it's just more$\mathbb{P}$) it just becomes so costly we're not yet in a position to make it happen. I sort of alluded to the building cost of hashtables when mentioning slow hashing, but I didn't have any specific. Mind if I incorporate yours? – Ninefingers Oct 26 '11 at 13:24 That's the point of my comments: to give information that anybody (including you) may use at their leisure (even for incorporating it into, for instance, an edit to this answer). – Thomas Pornin Oct 26 '11 at 13:37 Rainbow tables are just a hyped-up name for tables of precomputed hash values with some trickery to allow for handling huuuuge tables in less huge storage space (e.g. mere terabytes). Precomputed tables, including rainbow tables, are utterly defeated by salting. Assuming you used a proper password hashing process, one which includes a salt and can be configured to be as slow as appropriate (hint: it is called bcrypt), the one remaining weakness is about an attacker "trying" passwords to attack a single hashed password (assuming he got a copy of it). The salt prevents the villain from attacking several passwords in parallel; he has to pay the full price of trying out the potential password for each hashed password he wants to attack. Moreover, the configurable slowness can make each try arbitrarily expensive for the attacker (this has a cost: it also makes it expensive for you; hence the "configurable" part: you make it as expensive as is still tolerable in your context). Now, if you are stuck with existing software, some of the advice above may fail to be applicable. Remember that password hashing is a second line of defence: the attacker should not be able to access the hashed passwords; password hashing is there to prevent an attacker who did obtain unauthorized read access from upgrading his attack into user impersonation and associated write access. The main issue with "password policies" is that they are like herding cats (the cats are a metaphor for the users). Users are human beings, so they are just bad at choosing passwords because they cannot do good random in their head. That's consubstantial to being human. By enforcing policies, you are trying to weed out some cases of extremely bad randomness that humans can invent with alarming creativity. In my view, a better "policy" would be to provide a tool which does create uniformly random passwords, so that users may run it and get "strong passwords". One scheme looks like this: passwords consisting in two lowercase letters, then two digits, then two lowercase letters, then two digits. Just 8 characters, reasonably easy to memorize, yet a bit more than 32 bits of entropy. 32 bits of entropy are enough to deter attackers if you also have an appropriate hashing process, as alluded to above (bcrypt !). - Of course, users have more trouble remembering generated passwords than remembering ones they came up with. Passphrases might be better if you weren't so length limited. There are tools to check for really really bad passwords too. – erjiang Oct 26 '11 at 16:06 Rainbow tables can be used with words out of a dictionary rather than letters out of a charset. The ophcrack vista liveCD is an example. In contains two dictionaries and tries combinations of words as well as modifications. For example the main dictionary contains "house" and "boat" and the second dictionary has "2010" "2011" "january". It will then create passwords like boat2010 or BOAT2010 or h0us3january. You just need to create a reduction function that picks words from dictionaries and modifications from a set of modifications. Say you have a dictionary of 2^15 words (including an empty word) and you want to crate combinations of up to three words. To reduce a hash to a password you would - take the first 15 bits of the hash to select a first word from the dictionary - take the second 15 bits of the hash to select a second word from the dictionary - take the thrid 15 bits for the last word Then you could use some further bits of the hash to select some modifications (e.g. capitalization, writing the word backward, leet speak) up to your imagination. - The question is well answered by ninefingers, but the question exposes fundamental confusion on the part of Mitchell. The NT Hash is not salted, and it IS PASSWORD EQUIVALENT. There is no need to use the hash to get the password, just use the hash to access the resource! Second, the password must be greater than 14 characters to avoid the LM hash, see MS KB299656. You can kill the LM hash via local security policy or GPO. Finally, the use case where an attacker gets the hash means you are already owned. Due to MS's poor choices with CredSSP, the password itself can be pulled from RAM with the same level of access used to take the hash from RAM. Mimikatz. This level of access if total ownage. The hash is never offered up in a weak way, except via the request the hash attack which can be defeated via Reg keys; see this article. - Welcome to CSE! I see no fundamental confusion in the question, where it is asked if NTLM passwords are hashed; which you answer by the negative.$\;$Note: I took the liberty to embed the links, including the one you struggled with. This is conveniently done with the Hyperlink button of the edit window, or Ctrl-L; also, <a>http://foo.bar</a> or [text](http://foo.bar) works (the later is usable in comments too). While editing an answer, the preview let you see what it will look like, including hyperlinks. – fgrieu yesterday As far as I know, NTLM v2 uses a MD5 HMAC with the user password as the key and the MD4 hash of the concenation of user name and domain. MD5 itself isn't very secure as a hash (collisions are trivially to find), but it retains some value for applications like this one, since the best know preimage attack has about$2^{123}$complexity (so almost the full$2^{128}$). However, Microsoft itself advises against its use in applications (source: Security Considerations for Implementers). That being said, even without a salt, there are$26^{14}$different lower-case 14-character passwords. MD5 hashes have a 16-byte output, so a complete rainbow table would hold $$26^{14} \cdot 16\ bytes \approx 2^{69.8}\ bytes = 2^{29.8}\ Tebibytes \approx 900\ million\ Tebibytes.$$ However, if you require your users to use phrases, keep in mind that there are only that much words in the English language. Let's say$10,000$of them are likely to be used (it's probably less). About two words fit in 14 characters. That's only$100,000,000\$ likely passwords.

If HMAC and user name (or hash and salt) are known, a simple brute-force attack will reveal the password.

-