Rainbow Table Explained

Internet Security Technology News by FileEdge on August 21, 2022 Rainbow Table 1.1K views

Usually, PC systems need passwords that store passwords as a hash value of the user’s password. The system hashes the password while a PC user enters a password and compares it to the stored hash. Once the hashes match, you will get access. You can use a rainbow table of reversed hashes to crack password hashes. These generally use precomputed hashes to recover the pre-hashed password.

What is A Rainbow Table?

A rainbow table is a list containing all plaintext permutations of encrypted passwords specific to a particular hash algorithm. Password cracking software often uses these for network security attacks.

About Rainbow Table:

It partitions a function. A set of values is a function domain, whereas a set of keys is a codomain. These keys are derived from those values into chains so that every chain is a changing sequence of values and keys, followed by a final value.

In the chain, every item comes from an earlier item. Therefore, you can reproduce the chain from the first value algorithmically. A key derivation function generates a key from a preceding value, while a reduction function creates a value from a primary key. Every chain’s first & last value is precalculated and stored. It helps to make the chain a row in a virtual table. Hence, you can find every even-numbered field with a value. In addition, every odd-numbered field has the corresponding key. You can use it to find a secret value or password given its associated key.

You can assume an instance of a space-time tradeoff where you need less processing. However, a brute-force attack requires more processing. But it consumes more space than a brute-force attack uses to compute a key on each iteration. Therefore, using a key derivation employing a salt can make it infeasible to recover a secret value from a key.

Common uses:

Almost all Unix, Linux, and BSD variations use hashes with salts. But multiple applications use hash only with no salt. In this case, they usually use MD5.
The Microsoft Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method. In this regard, you must know that it depends on MD4. Besides, it is unsalted, making its famous generated table.
As of 2020, salting has become more common. In addition, GPU-based brute force attacks have become more practical. Therefore, we see them decreasing usage. However, you can get them available for eight and nine-character NTLM passwords.

How Does the Rainbow Table Attack work?

It performs quick and effective cryptanalysis. This attack is not a brute-force attack that computes the hash function of every available string and calculates the hash value. After that, it compares it with the one on the PC. However, the rainbow attack removes the need by calculating hashes of the large set of available strings. Instead, you need to follow two significant steps:

Creating a Rainbow Table:

First, you need to take the hash of a string. Ensure you use the MD5 hash function on the first eight characters. After that, you can decrease it to make a new string reduced again, repeatedly. For instance, you can make a table of the most common password, 12345678.

Your first task is to take the string to pass it through the md5 hash function.

hashMD5(12345678) = 25d55ad283aa400af464c76d713c07ad

It can decrease the hash only by using the first eight characters. After that, you should rehash it.

hashMD5(25d55ad2) = 5c41c6b3958e798662d8853ece970f70

One chain begins from the first plain text and ends at the last hash. You must repeat it until you have sufficient hashes in the output chain. Once you get sufficient chains, you should store them on a table.

Cracking the Password:

First, you should begin using the hashed text. Hence, you need to check if it exists in the database. If so, you should head toward the start of the chain. After that, begin hashing until it matches with one. Once you obtain the match, the procedure ceases, and the authentication is cracked.

Advantages and Disadvantages of the Rainbow Table Attack:

Advantages:

You can perform the hash function efficiently, unlike brute-forcing. Moreover, as you can find all values calculated already, it is possible to simplify an easy search-and-compare operation.
You don’t need to know the exact password. Once the hash is matched, it won’t depend on the string if it is not the password itself. It will be authenticated.

Disadvantages:

You need a vast storage amount to store them.
However, as all values are calculated, you can perform an easy search-and-compare operation.

Defense Against Attacks:

You can easily prevent the attacks using salt techniques. It is random data passed into the hash function with plain text.

Therefore, you can confirm that each password has a unique generated hash. You should know that it follows the principle of asking that more than one text can have a similar hash value, which is prevented.

Key stretching is another technique that helps to prevent pre-computation attacks. It allows the salt, password, and intermediate hash values to run through the hash function many times. Hence, it aims to boost the required computation time to hash every password.

You can follow key strengthening used to extend the key using a random salt. But it removes the salt, not like in key stretching. It forces legitimate users and hackers to perform a brute-force search for the salt value. As a result, you will not get any point in bypassing salting.

Why Are They Called Rainbow Tables?

The name might seem like an odd selection for a robust tool. However, while mapping out it and using different colors to illustrate the other reduction functions, you can see it making a rainbow-like appearance.

We experienced it in black-and-white on Oechslin’s original research paper. But he selected different colors to represent different reduction functions in his research at a 2003 conference.

Rainbow Tables:

These exchange the single reduction function R with a sequence of the corresponding reduction functions R1 through Rk. Thus, these help to get rid of collisions with ordinary hash chains. Besides, these must offer similar value on a similar iteration. Otherwise, the two chains will not collide and merge. In addition, the final values are the same in the chain. With the help of a final postprocessing pass, it is possible to sort the chains. Thus, it can help you to get rid of any “duplicate” chains. These offer similar final values to other chains. After that, you can make new chains to fill out.

Hence, you should know that the chains aren’t free of collision. Therefore, these can overlap briefly. But these won’t merge. So, as a result, it can help you to decrease the overall number of collisions.

You can take the help of sequences of reduction functions to change the lookup. In this case, you need to create k different chains as the key of interest is available at any location in the chain. Hence, the first chain finds the key in the last key position. Then, it applies Rk. After that, the following chain thinks the hash value is in the second-to-last hash position. Then, it applies Rk−1, K, and Rk. It will continue until the last chain applies all reduction functions, alternating with K. Thus, it can create a false alarm. The wrong guess of the position of the hash value might evaluate a chain.

Algorithm:

These need to follow more chains. But these come with less number of tables to make up for it. The usual hash chain tables don’t get enough growth beyond a specific size. However, these can be inefficient for merging chains. That is why these balance several ones where every lookup must search through each. These can perform in a way that is k times larger. It enables them to perform a factor of k fewer lookups.

These use a refined algorithm with a different reduction function for every link in a chain. It prevents chains from merging during a key collision in two or more chains. These chains won’t merge if the collision doesn’t occur at a similar position in every chain. It boosts the chance of a proper crack for given table size. But it occurs at the value of squaring the number of steps needed per lookup. For example, the lookup routine might require iterating via the first reduction function index.

Conclusion:

A rainbow table is always specific to the key function for which function you can generate. For instance, MD5 can crack only MD5 hashes. Philippe Oechslin was the developer of the theory of this technique. Later, the implementation occurs in the Windows password cracker Ophcrack. After a while, scientists invented a more robust RainbowCrack program. It can make and used for different character sets and hashing algorithms, like LM hash, MD5, and SHA-1.