I first learnt about these around two and a half years ago when I stumbled on one of security related sites (Can’t remember). The concept looked awesome. It’s used for cracking passwords that are hashed in a fraction of time than most other techniques will allow you.
Before we move further let me give brief background information on password storage
Systems that need authentication provide a means to store the authentication tokens (User ID and password) in an authentication repository(database). These passwords are stored in following ways:
1. Plaintext : Passwords are stored in plaintext in the authentication repository. Once someone has access to the repository the person can see the password without any difficulty and can use them to access the system from the front end. Obviously designers of these system haven’t thought enough on security front, cared less or plainly thought that nobody would try to steal passwords for these systems (for whatsoever reason). Nevertheless it’s a real bad design considering better practices as mentioned below can be applied with very little effort.
2. Encrypted Passwords: Designers of these systems are conscious of their security and implement a mechanism that will encrypt the password by using either a publicly or privately available encryption mechanism. Problem with this mechanism is that all encryption algorithms have corresponding decryption algorithms and can be decrypted once the key is available to the person looking to get the passwords to the system.
3. Hashed Passwords (Most widely used): Unlike encryption algorithms hashing algorithms are one way functions without any corresponding de-hashing algorithms that generate a unique hash for a given input. A mathematical representation would be
H(x) =p where no such F exists such that F (p) =x. H is the hashing function and F is the non-existent de-hashing function. The commonly used hashing algorithms in widespread use are MD5 and SHA. In general hashing algorithms generate a fixed size hash value for any given input (e.g. 128 bit for MD5, Password= 11, Hash=6512BD43D9CAA6E02C990B0A82652DCA).
There is no mathematical way for a strong (Attacks have been demonstrated on MD5 and SHA1. SHA 256 is considered to be secure. SHA 3 is under development at the time of writing of this article) hashing algorithm to retrieve the password from the hash. The methodologies that are used in general are dictionary or brute force attack where you try many passwords one after the other until you find a password that will give you the exact hash that you are looking for. If you find the exact hash for the plaintext! Voila you have cracked the password. The problem with dictionary based attacks is that dictionaries can’t be very big and a password that does not exist in the dictionary will not be cracked. Brute force cracking has its limitations in terms of huge processing power requirements that are required to compute hashes. To brute force a password of up to 10 characters containing all small alphanumeric characters (abcdefghijklmnopqrstuvwxyz0123456789), the number of hashes to be calculated would be 36^1+36^2+36^3+36^4+36^5+36^6+36^7+36^8+36^9+36^10.
Now this is a big task. It will take weeks or months to crack password this way.
A good idea would be to precompute the hashes and maintain a table of plaintexts and hashes. This will save the time of computing hashes and make the job of cracking the password easy. However the generated hash table will be very big in size.
Rainbow tables are way to keep the size of these precomputed tables low by making use of intermediate reduction functions. This was first proposed by Philippe Oechslin in his paper faster time-memory trade-off technique published in 2003.
So you want to use rainbow tables for cracking passwords. The questions are:
Q.1. What passwords you want/can to crack?
Ans. a.You can crack the passwords for which you have access to the password repository and the hashed password.
b. You will also need to have the knowledge of the hashing algorithm used.
c. You will also require the rainbow tables built for the corresponding hashing algorithm.
The most common password repository is of Windows OS (If you are using one). It stores the NTLM hashed (LM hashed too for compatibility with older versions of windows) passwords that can be recovered using many programs like pwdump, LCP and Cain & Abel (You will require administrative access to the system for recovering these hashes).
Now you need to have the rainbow tables. You can either build them yourself which is a very time taking process that you might not want to do unless you have huge processing power available or you can download rainbow tables form many of the sites that provide it either free of cost or by the way of payment (Tables sizes will be in the range of 350 MB to 100 GB+).
In case you do not want to download the tables there are a couple of resources that I have found that you can try using:
http://www.plain-text.info/
http://www.freerainbowtables.com/
The above mentioned resources allow you to submit hashes and return plain texts for free.
In case you want to download and work in a more sophisticated manner the following resources should be helpful:
http://www.freerainbowtables.com/
http://project-rainbowcrack.com/
http://ophcrack.sourceforge.net/
http://rainbowtables.shmoo.com/
One of the simplest articles that I have found that can be helpful in understanding rainbow tables is:
http://kestas.kuliukas.com/RainbowTables/
Limitations of rainbow tables
1. For all the goody goody image of rainbow tables it also has its share of limitations. In spite of excellent compression algorithms rainbow tables still are quite big in size if the character set is huge. In general it’s difficult to find rainbow tables with big character sets for password lengths of more than 14.
2. Generating rainbow tables is very CPU intensive and takes huge amount of time. This can be offset by using distributed architecture for table generation or using very powerful computers.
Q. How to protect yourself against rainbow tables
Ans.
1. Keep your passwords longer. In case of windows if your password is more than 14 characters long then no LM hashes (Which is weaker) will be stored. Do not use passwords, instead always use passphrases that are longer and easier to remember.
2. When designing a system for password storage never store password in plain hash. Use salts. Maybe double or triple hash them. e.g.
Password=hello how are you
Stored Password= SHA256(SHA256(Password+”The desired salt”))
Salts can be generated randomly and need not be secret.
This will make rainbow tables ineffective.
