Password Cracking with Rainbow Tables
This tutorial is not meant to be a comprehensive lesson on encryption and password cracking in general, but a closer look at a specific password cracking technique that has been developed relatively recently. As such, you are encouraged to check out the following links if this paper isn't making sense:
http://www.fsix.net/files/john.txt
http://www.dsinet.org/textfiles/unix...ix_Newbies.txt
http://www.antionline.com/showthread...hreadid=252078
Conversely, if you're already very familiar with encryption and password cracking, feel free to skip down to the "Enter RainbowCrack" section.
----------------------------------------------------------------------------------------------------------------------------------------------
RainbowCrack is a program which cracks encrypted passwords, hardly a new idea. However, the method which it uses to do so is very new, and has the potential to change the time required to crack certain passwords from years to a matter of minutes. In this tutorial I will describe the basics of how RainbowCrack works and the security implications of this new technique.
A BIT ABOUT PASSWORD ENCRYPTION
Passwords are probably the most common form of computer authentication. In the vast majority of security designs, the password to the root or Administrator account is the sole piece of information an attacker needs to gain complete control of the system or network.
Passwords must be known to the authenticating server and nobody else (save the user, of course). To keep them secret, servers do not store the passwords in plaintext, but as an encrypted password hash. This way, anyone who gains access to the password file on the server doesn't have a list of everyones's passwords.
A BIT ABOUT PASSWORD CRACKING
...Or do they? Password encryption is done using a one-way hashing algorithm, meaning that as far as we know, there is no way to look at the hash and calculate what password was used to make it. Password crackers work like this:
1 - Make a guess at what the password might be.
2 - Encrypt the guess using the same algorithm the password was hashed with.
3 - Compare the guess hash and the password hash
4 - If they're different, go back to step 1.
5 - If they're identical then, guess what? The cracker's guess is the password.
"Conventional" password crackers execute this process in real time, calculating hash after hash until the matching one is found. The catch is that even if the target password is 1-7 characters long (which is relatively short), and even if it's limited only to lowercase letters (a very insecure password), there are still 8,353,082,582 possible combinations. This means that even if your cracker can calculate 150,000 hashes per second, it will take over 15 hours to run through every possibility.
Given that many passwords are 15 characters and contain upper and lowercase letters, plus numbers and special characters, you're looking at 3,491,870,000,000,000 YEARS on an average desktop (according to my math, anyway). Because of the insanely high amount of time required to crack a complex password using a conventional cracker, they are often considered secure.
ENTER RAINBOWCRACK
RainbowCrack ( http://www.antsight.com/zsl/rainbowcrack/ ) is a program developed by chinese cryptographer Zhu Shuanglei. It is basically a practical implementation of a cryptographic theory invented by Philippe Oechslin ( http://lasecwww.epfl.ch/php_code/pub...php?ref=Oech03 )
Okay, so what does it do?
The short answer is that it cracks complex passwords in 5 minutes or so, depending on the cracker's harddisk access-speed and RAM.
How does it work?
Well, when using a conventional cracker, comparing the guess hash to the password hash doesn't take long at all. The bottleneck (slowest part) of conventional cracking is actually turning the guess into the guess hash.
Now, since the cracker is inevitably going to try the same list of guesses on every password it ever tries to crack, the obvious question arises: "Why not calculate all the hashes one time and store them for later use?" It was a clever idea, until someone pointed out that storing every hash for even a limited (length 1-7, lowercase letter only) password would take up over 133 GB of space.
Instead of calculating every single hash, RainbowCrack creates, and stores to disk rainbow chains which are organized in rainbow tables. I'm not a cryptographer, so I can't describe the mathematical details of how rainbow chains operate, but in my opinion these details aren't vital for a network security professional to understand anyway (if you're interested in these details, definitely check out Philippe Oechslin's paper listed above).
Practically, rainbow chains provide a highly efficient middle ground between terrabytes of precalculated hashes and the redundant and slow "conventional" cracking approach.
IMPLEMENTATIONS OF RAINBOWCRACK
According to the designer of RainbowCrack, it will take 2 days and 18 hours to generate the rainbow tables neccessary to crack a lowercase-letters-only Windows (LM hash) password that's anywhere between 1 and 7 characters in length. Once the tables have been generated, 99.9% of passwords will be cracked in 74 seconds on modest hardware (666 MHz, 256 MB RAM).
A group called Sarca ( http://sarcaprj.wayreth.eu.org/ ) generated tables capable of cracking complex passwords (1-15 characters, alpha-numeric plus some symbols). It took them 3 months to compile the 18 GB of tables, but password cracking still only takes "minutes", according to them.
PRACTICAL IMPLICATIONS OF RAINBOWCRACK
At this point, it should be apparent that this program puts a significant dent in the security of many common cryptographic algorithms such as LM and MD5. Mike Mahurin details a scenario ( http://www.giac.org/practical/GCIH/M...hurin_GCIH.pdf ) where a professional attacker uses RainbowCrack to discover the Administrator password to a government network immediately after accessing the hash file. Using any other cracking method, obtaining this password would take months or years.
The most obvious advice to take from this is to guard password files like SAM, shadow, and .htpasswd with your life. While this may already be done, RainbowCrack is a sort of proof-of-concept demonstrating that reading said files is synonymous with full access to your system.
A more interesting implication is that periodic password changing may no longer be as effective as it used to be. If it takes a cracker 5 months to decrypt a user's password, but passwords are changed every month, the system didn't used to be vulnerable to brute-force password cracking. RainbowCrack changes that.
USING RAINBOWCRACK
If you want to try your hand (and your patience) at generating your own rainbow tables, there is an excellent tutorial by the designer of RainbowCrack at ( http://www.antsight.com/zsl/rainbowc...cktutorial.htm ). If you examine the various parameters he provides it should become apparent how to customize the table generation any way you'd like. If not, maybe I'll write another tutorial on how to generate rainbow tables...
It's worth noting that although you have to calculate several different rainbow tables, it's not neccessary to do so sequentially. For example, if you had access to 5 computers, you could have them each compute a fraction of the total tables, and thereby finish 5 times faster.
If you don't have the patience or the harddrive space to cook up your own tables, the Sarca folks have an online script which will take your LM and NTLM hashes, use their massive rainbow tables to attempt a crack, and email you the results. ( http://sarcaprj.wayreth.eu.org/ )
Good luck!
Re: Password Cracking with Rainbow Tables
Just some criticism/comments.
Quote:
Originally posted here by 3rr0r
"Conventional" password crackers execute this process in real time, calculating hash after hash until the matching one is found. The catch is that even if the target password is 1-7 characters long (which is relatively short), and even if it's limited only to lowercase letters (a very insecure password), there are still 8,353,082,582 possible combinations. This means that even if your cracker can calculate 150,000 hashes per second, it will take over 15 hours to run through every possibility.
There are mitigating factors to the number of combinations, such as delegating every instance of more than three consecutive occurances of two letters (ie: zzzabcd is invalid, zzabcde would be valid) to be attempted at the end. Steps that are taken to improve password security as an administrator may also be capable of helping a cracker limit those possibilities, but that involves writing it yourself. Perhaps you could discuss these mitigating factors (such as knowing the hash algorithm, hash computation time, etc.) a little bit more in depth.
In all it was a very well done tutorial, if a bit lacking in the detail department for my particular tastes. Then again, I find cryptography an interesting topic. ;)
Well done.
