EXPLORING RAINBOW TABLES

When we are using any computer which requires password authentication, the need to hide the passwords arises. The passwords related to systems are stored in the database either hashed or in plain text or using various other methods. These tables are vulnerable to theft as plaintext passwords are a dangerous attempt. Mostly, the passwords are stored as cryptographic hashes of user’s passwords. By using hashes for the passwords no one can determine the actual password. The authentication requires matching of two values, the entered one and the value stored in databases. The access is granted only when the two values match.

If anyhow, a thief steals hashed passwords tables, there is a very low chance of getting access of the system. For this the concept of Rainbow tables is used. Rainbow tables are the tools that have been developed to derive a password by looking only at a hashed value. Brute force attacks and dictionary attacks are the simplest methods available for password identification. But these methods are not effective for the systems to store large passwords, due to difficulty in storing and searching through reverse-lookup of a hash.

What is Rainbow table??

A Rainbow Table is a way of performing cryptanalysis easily and effectively. More specifically, a rainbow table is a pre-computed table for reverse cryptography hashes function for cracking the user’s secured passwords. These tables are used to crack passwords, which are in encrypted and can’t be read. This means Rainbow Tables are used to find the original plaintext for hashed passwords, which are hashed using different hash functions like MD5, LM, and NTLM. Using Rainbow Table ensures that the password will be cracked in a short duration of time as compared to brute force attack or the dictionary attack. The success rate of rainbow table is much higher than that of other methods. Technically, the rainbow tables are the collection of rainbow chains.

Rainbow Chains:

For this we need to be aware about rainbow chains. Rainbow chains are the backbone of rainbow tables. Each table contains millions of Rainbow chains for the generation of rainbow tables. It is basically a 2x64 bit integer. The first integer is the starting point, and the last integer is the ending point. The sizes of chain will remain the same: 16 bytes, irrespective of length of chain.

How to generate Rainbow chains, a big issue :

Earlier, a random start number is used, but now mostly tables are generated sequentially. So we start with a number used as a seed for the chain. This number is now reduced to fit within the keyspace       (Keyspace is the amount of words needed to cover a given set of characters with specific word length. For Rainbow tables with character set lower alphanumeric and the password length 1-7, the calculation includes -36^1+36^2+36^3+36^4+36^5+36^6+36^7 =80603140212.36 is the amount of character in the character set a-z =26 and 0-9 = 10). The resulting number is the starting point for the chain and stored in the table. A special function (IndexToPlain) is used for mapping the starting point to the plain text password. Now, this plaintext is hashed using a hash function (MD5, NTLM, LM etc) called as PlainToHash.This resultant is then processed by a reduction function which will convert the hashes into a 64 bit that fits within the key space  called as HashToIndex. And this process is repeated L times to create L number of chains for a rainbow table where  the resulting HashToIndex () is used as the seed for the IndexToHash (). L is the chain Length of the table. The resultant value after L reputation is the end point of the chain

How numbers are used for password recovery?

When a hash is to be cracked, it uses the HashToIndex to convert the hash into 64 bit integer. It then generates a 64 bit index position, P, in the chain and has an L number of indices generated. And performs a search  for each of these indices in the table. If the endpoint in the table matches the index number, then there may be a hit. To confirm the hit, it needs to regenerate that chain. For regenerating the chain to the current position, it uses starting point as a seed. The resulting index number is converted to the plain text using IndexToPlain. To verify, a hit, PlainToHash  to compare the 2 hashes. If it matches, we recovered  the password and the cracking stops. If It does not match, It was a false alarm and we have to try the next match. When all the searches have been searched, the process is completed.