Rainbow Tables, Looking at how the sausage is made
It's been a while since I posted, so I thought I'd put up something that has been bothering me for a long time, and isn't about bulbs ;)
Every security pro knows what a rainbow table is, at least they think they do. I was certainly in that position until I really started looking at them as part of my GPEN revision. From the material we had and the questions asked it class it still was not clear how exactly we make sure that our tables contain all of the possible permutations of passwords in the key space we are looking to recover from. I put some feelers out to a very knowledgeable bunch of people on a mailing list I am a member of and it was clear by the fact that I only got one reply that most infosec pros are quite happy to use the technology as long as they don't have to understand how it really, really works.
"Hand reared organic pork, only the best cuts and no filler"
Rainbow tables are easy right? We just use our massive computers to pre-calculate all these lame unsalted hashes and record them in a file, and then when we have a hash to crack we just look it up in the file and presto, we have the password. No, that's wrong, stop telling people that. If it were that simple we would have been doing this decades ago. The big issue with this is the space required to store all the pre-computed hashes. In the above model a table of hashes and passwords covering the Alpha-Numeric with Special Character key space would contain 7.5 x 10^12 pairs, totalling 112TB. You can download a table to do the above key space for LANMAN hashes with a 99.9% chance of success that is less than 1GB. How on earth can that work?
"Right Lisa, some wonderful, *magical animal!" *
You'll no doubt have noticed the 99.9% figure quoted above, it was what got my head down in the rabbit hole in the first place. You see, rainbow tables are a product of *deep dark maths* and they get their special powers by the fact that there is an element of randomness used in their creation. This is where people like me without a doctorate in mathematics, start to have to trust the what the people who do have one say about this process. On a very basic level rainbow tables work by reducing by an order of magnitude the amount of computation a system has to do in order to determine the password that is associated with a particular hash.
How to get from 112TB to <1GB
Instead of storing every password:hash pair in a lookup table, rainbow tables only store the start condition and end condition of a chain of reduction functions. These chains of functions can be any length although they are usually in the order of tens of thousands of calculations long. The longer a chain is the more work the cracking computer has to do to determine the password. This means it takes longer to crack a hash but the table size is smaller, and this is the trade off we have to make to have tables of a reasonable size that can still recover passwords in a reasonable amount of time.
What are reduction functions?
A reduction function is similar to a hash function in that it takes an input and generates an output. However it the output it produces must be compatible with the key space we are looking to crack as its output is then used by the hash function we are generating a table for to generate another hash, clear so far? How about an example?
Example chain
Starting password: F1shermans3n3my
Reduction function R(1) just takes the first 8 characters of the input hash
Reduction function R(2) takes the second 8 characters of the input hash
Reduction function R(3) takes the first 8 characters XOR'ed with the second 8
F1shermans3n3my -> MD5 -> 197286d6790a825d9776919ab1308457
197286d6790a825d9776919ab1308457 -> R(1) -> 197286d6
197286d6 -> MD5 -> 414e28158cfc944ef733df37e6a4c4e7
414e28158cfc944ef733df37e6a4c4e7 -> R(2) -> 8cfc944e
8cfc944e -> MD5 -> 853fdffc3878b857c686f43265c27768
853fdffc3878b857c686f43265c27768 -> R(3) -> BD4767AB
etc.
Now these are just functions I pulled out of my... hat, and it is not suggested that they are good reduction functions to use when generating chains. As the chain is being generated the reduction functions cycle through again and again until the chain has been generated of the required length. The *deep dark maths* makes sure that these functions always return a value that is compatible with the desired key space and password length to be recovered, and that after a certain number of iterations will have returned a certain percentage of the total key space. This is the point that was not clearly explained in the material on SEC560 and made me look into this in the first place.
A note about start points
The initial passwords that are used to start the chains need to be selected, and you can either generate them randomly or sequentially, see this post for more on this. Also it has been suggested that you can generate them with dictionary words(Thanks Farhan).
At the end of all this hashing and reducing we save our disk space by throwing almost all of it away. Stay with me though, it'll make sense later. We store only the start password and the end password. We then start another chain with a different initial password and rotate our reduction functions by one so that in the example above we would start with R(2) then R(3) and then back to R(1)
Chain 1 Chain 2
Initial Password Initial Password
Reduction Fn 1 Reduction Fn 2
Reduction Fn 2 Reduction Fn 3
Reduction Fn 3 Reduction Fn 1
See the rainbow? I bet you thought it was a drug reference didn't you?
So how does all this help us recover passwords?
So far we've done a lot of maths and thrown most of it away, and I bet you're wondering how this has in any way made recovering passwords easier. The trick comes with the steps used to lookup data in the tables. First take the hash you want to crack create a chain using the same reduction functions that were used to generate the tables. Then take all of the passwords that the reduction functions generated and see if they match the end password of any of our generated chains. Once you have found a chain that contains one of the passwords our chain has generated then you know that because we are using the same reduction functions that somewhere in that chain is the password:hash pair that we want to recover. You then re-create that chain checking at every step to see if a hash function generates the hash that we are cracking. Once it does you go back to the output of the previous reduction function and you have your password. The total computing load for cracking involves creating only one chain, a series of lookups to a small (millions usually) number of end passwords, and a partial generation of a further chain. This is orders of magnitude faster than running through the entire key space manually. The slowest part of this is looking up the chain end passwords as the tables are usually too large to fit in memory and you are relying on slow disk I/O.
Am I satisified now?
Well I got my question answered and I think I now really do understand how these small tables can cover the huge key space that is required to do this kind of lookup. However just like with cryptography it's never a pleasant feeling to have to resign yourself to just trust the maths. I doubt I'll ever get a PhD in mathematics so I'll have to do just that.
This post is mostly just an exercise for myself as I usually learn things better if I write them down, and there are other resources out there that go into the mathematics behind this if you have the background to understand it. Also I can recommend the SEC560 course to anyone who is interested in penetration testing, so don't be put off by this post as rainbow tables covers only 13 slides in the 6 day course, and I have had no issues understanding the rest of it! I'm 99% sure I've got this down now, but my reduction functions are overloaded with Tonsillitis and pain killers so if anyone can see any glaring mistakes then feel free to tell me where I'm wrong so I can correct it. The last thing I want is for this post to be mis-information on an already confused subject.
