Posey's Tips & Tricks
Password Cracking Revisited: Rainbow Tables
Brien takes a look at cracking passwords with reader-suggested rainbow tablets.
Last month I wrote a column in which I discussed my attempts at cracking passwords in a lab environment. I had intended for the blog post to be a thought exercise. I constantly hear people recommending the use of long and complex passwords, and I wanted to find out just how much of a difference length and complexity made. I wasn't just interested in mathematical theory, but also in real-world practicality.
Shortly after that particular blog post went live, it was flooded with comments from people stating that the exercise was not representative of real -world cracking because tools and methods exist that do away with the need for a brute force crack. Many of these comments specifically referenced rainbow tables.
I have always tried to keep the content in my blog posts honest, so I have to confess that I had never heard of rainbow tables. It kind of makes sense if you stop and think about it though. Much of my IT education has come from Microsoft certification classes and Microsoft isn't about to include techniques for cracking Windows passwords in their curriculum.
Being that rainbow tables were unfamiliar to me, I thought that I would take the opportunity to discuss them for the benefit of anyone else who might not be familiar with the concept.
As you saw in my previous article, brute-force password cracking is prohibitively slow. Sure, there are ways to speed up the crack, but generally speaking brute force cracks are not practical.
Most brute-force cracking utilities generate passwords one at a time and use those passwords in sequential cracking attempts. As you probably saw in my previous article, this approach is extremely computationally intensive and time consuming.
Another approach that has been used is to generate all of the possible password combinations ahead of time and then store them in a table. That way the cracking utility can simply reference the table rather than having to go through the effort of a brute force crack. While this approach sounds good in theory, there are a couple of problems with it. First, it can take a long time to create the table entries. Second, it could take an impossibly large amount of space to store the table data.
Rainbow tables are something of a compromise between these two techniques. Rainbow tables are based on the idea that many systems store passwords in a database. Of course storing the passwords in plain text would not be very secure, so the passwords are stored as non-reversible hashes.
Rainbow tables are chains of hashes and reductions. A reduction matches a hash to plain text. These tables start with a plain text value. The value is repeatedly hashed, reduced (which is not the same thing as an inverse hash), and then rehashed. However, the table itself only stores two values -- the starting plain text and the ending hash. As such, a chain consisting of millions of values can be stored as two values -- essentially the start and end points.
Rainbow tables are arranged in columns of chains (which aren't actually stored anywhere). Because of the way that these columns are arranged it is simple to tell whether a password hash exists within any of the columns. Once the correct column is located then deriving the password is simply a matter of working through the hash and reduction functions for that column. This process allows complex passwords to be cracked very quickly.
What Got Overlooked?
Most of the comments that I got in relation to my previous article seemed to assume that I based the article on Windows passwords. I didn't. The article was based on the idea of performing a brute force crack on a ZIP file, not on a Windows password. I wanted to get a general feel for the impact that password length and complexity had on a brute force crack. Even so, I think that it is fair to consider the impact that rainbow tables might have on cracking zip file passwords.
Rainbow tables don't work for ZIP files for one very simple reason. Rainbow tables work because the password hash is stored on the system that is being cracked. This hash is the key to making the whole thing work.
Zip files do not store their passwords as a hash. Password-protected ZIP files are encrypted, and the password is the encryption key. As such, rainbow tables do not work for cracking ZIP files because there is no password hash that can be retrieved.
I sincerely wish to apologize for any confusion caused by my previous article. I am grateful to those who commented about rainbow tables because those comments allowed me to learn about something that I had never seen before.
About the Author
Brien Posey is a 22-time Microsoft MVP with decades of IT experience. As a freelance writer, Posey has written thousands of articles and contributed to several dozen books on a wide variety of IT topics. Prior to going freelance, Posey was a CIO for a national chain of hospitals and health care facilities. He has also served as a network administrator for some of the country's largest insurance companies and for the Department of Defense at Fort Knox. In addition to his continued work in IT, Posey has spent the last several years actively training as a commercial scientist-astronaut candidate in preparation to fly on a mission to study polar mesospheric clouds from space. You can follow his spaceflight training on his Web site.