Rainbow Tables and Easy Password Recovery

Dec 04 2006

By Kurt Seifried (kurt@seifried.org)

Password security largely relies on secrecy, if someone finds out your password you’re generally up the creek. Of course this isn’t news to anyone but I feel compelled to give some background information in order to setup the dominoes before knocking them down.

So if we need something to be a secret, but we need to pass this secret around, and be able to verify that indeed, the correct secret is being sent around what technology can we rely upon? Why good old encryption of course! More specifically one way hashes, data goes in, gets mangled and 1’s and 0’s come out which cannot be used to determine the original password. Well unless of course you take every possible password, hash it and compare it to the value you have. Once you find a match you know what the original password is. Of course one interesting issue here is hash collisions, since a hash generates a value that is finite in length, and generally shorter then all the possible inputs you can get a password that has the same hash value of another different password. More on this later.

As it turns out this type of attack where you simply brute force passwords and store the results for later lookup is surprisingly easy to do in a quick and efficient manner.

Traditionally this type of attack would require huge amounts of storage space for every possible password and hash value, making it largely impractical to pre-compute all the hash values, store them and then later look them up as needed. Even with storage costs coming down this form of attack is, to put it bluntly, a total pain in the butt.

Enter Rainbow tables. First suggested by Philippe Oechslin, simply put rather then computing and storing every possible password and hash value you take a password, hash it, hash the resulting hash and repeat several thousand times. You now have a hash value and the initial password used to create (about 10,000 iterations ago). Now the trick that comes in is the password check doesn’t really care what the password is, it only cares that the hash value of the password is correct. With this in mind any string of text be it “dog” or “203yrfqhweggbas” which has the same hash value is for all intent and purposes usable as the password. Suddenly you can store 10,000 hash results with only one hash value, a vast improvement.

All that remains is for the majority of the possible values to be calculated, indexed and then stored. Once this step is done you can look up a password in a matter of seconds (basically your only bottleneck is copying the data into memory and searching it until you find a result). Since a Rainbow table for a given set of passwords typically ranges from several hundred megabytes to a few dozen gigabytes this step does not take a lot of time on a modern system. The software to do all this is freely available and easy to use.

Or you can simply skip all this and pay an online service to send the results back to you via email in a matter of minutes. Generally speaking the cost of getting a Windows password decrypted by such a service is about 30 to 40 cents (US) a password. Yup. Not even a dollar.

Bet you got passwords worth more than a dollar flying around your Windows network.

Password Cracking: Rainbow Tables Explained by Philippe Oechslin, Ph.D., CISSP

RainbowTables.net - Bulk Password Decryption Service

http://www.passcracking.ru/ - MD5 Password Decryption Service

http://rainbowtables.shmoo.com/ - Downloadable Rainbow Tables

Share and Enjoy: These icons link to social bookmarking sites where readers can share and discover new web pages.