All You Wanted To Know About Rainbow Table Attacks

Contrary to what the name suggests, rainbow tables are nowhere as picturesque and pose a severe threat to users and businesses using the digital world. This article will attempt to break down the hows and whats of a rainbow table and arm you with knowledge on preventing a rainbow table attack. Primarily used as the base of a password cracking tool, this table helps crack password hash values or crack passwords.

Rainbow tables are a way to reduce the amount of time taken for dictionary attacks. They work by taking all of the hashes for every word in a given language and then sorting them according to their corresponding passwords. So if you have a rainbow table for English words, and you know the hash for the word “password”, then you can look that hash up in the table and find the matching password. Rainbow tables are much faster than a standard dictionary attack, but they require more time to create.

What is a rainbow table attack?

A rainbow table attack is a type of dictionary attack that uses precomputed tables of data to reduce the time required to crack passwords. Rainbow tables are usually created by hashing all possible passwords with a cryptographic hash function and storing the hashes in an extensive database. When a user attempts to log in, the password is hashed and compared with the values in the table. If a match is found, the user’s password is identified.

Users’ passwords in a computer system are not stored in the system directly as plaintext. Instead, a hash value generated by a hash function is used. When a user tries to authenticate, the user submitted password is converted into a hash value. This value is then compared with an already stored hash value. If the value matches, then the user gets authenticated.

A rainbow table attack is a type of hacking in which an attacker tries to use a rainbow hash table to crack the hash value of passwords stored in a database. It is a collection of precomputed dictionaries of plaintext passwords and their corresponding hash values that can be useful in finding what plaintext password produces a particular hash.

Let us first look into what password hashes and hash functions are:

Password hashes

Password hashing is a method by which plain text passwords are encrypted using some hashing algorithm. Hashing passwords makes it impossible for an attacker to reverse the password hash to the plaintext password, and even a tiny change in the input would drastically change the output value. Whenever you hear or read about hashed passwords being stolen, attackers have the challenge to crack these passwords using a password cracking method before they see clear-text passwords.

Once hashes of a particular value are found, they are stored in a database. Hash algorithms use functions to map the object value to an integer value which would make the process of locating a particular hash like in the case of an authentication process much easier. The hashes are stored in the form of a key-value pair so that a specific hash can be searched using its key part.

Example of how a standard hash function would work-

When a string “morning” is given as input into a md5 hash function the output returned is c7c3169c21f1d92e9577871831d067c8.

If the input is slightly changed and the first letter is capitalised (“Morning”) and then given as input then the output is b311a3fe13ac9b0ee02985f4759a2e46.

This shows that the slightest change in the input brings about a significant change in the output. This property is known as the avalanche effect, and it is one of the most powerful features of hashing algorithms.

Hash function

A hash function is an algorithm used to convert a plaintext of arbitrary length and convert it into a password hash of fixed length. Hash functions use the reduction function to form the output. A hash function is a one-way function, which means that a hash value cannot be reversed to its plaintext even if we find the algorithm used.

A reduction function is a function that consistently maps a hashed value into a valid plaintext value and returns the hash value h.

The main property of hash functions is that however long or short an input be, the output returned will always be of a fixed length.

Example: If we input a word “see you” into an md5 hash function the returned output value is 8a0422b3390a2403eeb55f12be6f38e6.

And then, if we input another phrase, “see you in the morning”, the output is bf4b15339b364251ea84701ac4eef0a2.

From the above examples, it is pretty evident that even though the output is very different, the length remains the same even when the input differs a lot in length.

Rainbow Tables

Before delving further into how rainbow table attack works, first let us first see what a rainbow table is:

Databases storing passwords use some form of hashing method to make it safer. For example, Linux systems use MD5 algorithms to hash the passwords stored in the /etc/shadow file.

A rainbow table is a precomputed table for reversing cryptographic hashes. It is a data structure that allows one to quickly reverse the process of hashing to obtain the original value. Rainbow tables are usually created due to exhaustive search algorithms that calculate all possible combinations for a hash function.

History of the rainbow table

Rainbow tables are often thought of as simple large databases of scomplex or straightforwardpasswords or hash combinations. Even though this is how the mechanism of rainbow tables appears to work from the outside, this is not how rainbow tables work internally. The precomputation process of the hashes has obvious advantages in storage. Storing a large amount of data plainly in a database would require much more memory than when it is stored in the form of hashes in a rainbow table. Hence, not only does the rainbow table makes cracking password hash value faster, but it also saves expenses in storage.

Philippe Oechslin described this challenge: “Cryptanalytic attacks based on exhaustive search need a lot of computing power or a lot of time to complete. When the same attack has to be carried out multiple times, it may be possible to execute the exhaustive search in advance and store all results in memory. Once this precomputation is done, the attack can be carried out almost instantly. Alas, this method is not practicable because of the large amount of memory needed.”

Rainbow tables rely on a clever time/memory tradeoff, meaning that computation of passwords can be faster if provided with more memory, or memory expenses can be saved by allowing more time to the computation processes. This technique was researched by Martin Hellman and improved by Philippe Oechslin.

In this process, long chains of the password–hash pairs containing thousands and millions of pairs are connected together into one corresponding chain called a rainbow chain and many chains may be formed, connected via different reduction functions. In the end, everything in the chain except the first and last entry can be removed on the basis of requirement. This can save a large amount of storage space, in exchange for some time and CPU cycles.

How does a rainbow table help an attacker?

In other traditional password cracking methods, when an attacker gets access to a hashed password file from a database, the attacker must first analyse the hashes and find out which type of hashing algorithm is used.

After this process, the attacker then applies the same algorithm to the password dictionary file containing plaintext passwords or generates a custom password file for performing a brute force attack on the password. This makes the whole process of password cracking rather time-consuming.

These issues can be avoided by using a rainbow table, rainbow tables help to compare a password hash with the values in the rainbow table and returns the one with the same hash value. Rainbow tables make the password cracking process much easier and less time-consuming.

Rainbow table vs Brute force attacks

Brute force attacks use a type of trial and error method to guess login info. It is still useful when trying to guess a plaintext password, an encryption key, hidden web pages etc. The time for a brute-force attack depends upon the data. Brute force attacks can take from just seconds to even years depending on the length and complexity of the password and this is one of its main drawbacks.

Simply trying to brute force a long or hashed password may take days to complete and would require expensive computational power to make it faster. That is where the rainbow table attack comes in.

The main difference between a brute force attack and a rainbow table attack is that there is precomputed data involved with a rainbow table when trying to crack passwords whereas there is no precomputed data when a brute force is to be performed. Rainbow tables greatly speed up the process compared to brute force attacks. Some software can crack password hashes of 14-characters in under 160 seconds!

Prerequisites to perform a rainbow table attack :

• Original password hash or hashed password database must be available to the attacker.

• Make sure that salting techniques are not used in the hashing process as rainbow tables work only with unsalted hashes.

• The target system should only be using a one-factor authentication system.

Example of how attackers use a rainbow table in the “real world”

If an attacker finds a vulnerability in a system or server’s Active Directory, he can then use various techniques to gain access to the password hashes file. Once they get hold of the list of hashes, they can then execute a rainbow table attack to decrypt the hashes into plaintext passwords.

If a system uses outdated applications with vulnerabilities, this can lead to an attacker taking advantage of this weakness and planting a backdoor/malware in the system. The attacker then escalates his privileges and dumps the password hashes. Using a rainbow table, they can then decrypt the passwords of all user accounts in the system.

Generating rainbow tables using “RainbowCrack”

Let us see how we can create rainbow tables using a command-line tool called rainbow crack. You can download this tool in Linux using the command: “apt-get install rainbowcrack”. There are many features available with this tool but for now, we will be using the rainbow table generation tool known as “rtgen”.

Inserting the input to produce a table. Input values given include the type of hash to be used, the type of alpha-numeric elements to be hashed and added to the table and also the character length, table index, chain length, etc.

After completion of the process, the rainbow table file will be stored in the tool’s directory.

Advantages & disadvantages of using rainbow table attacks:

Advantages

Since everything is precomputed, the process is simplified into a simple search and compare operation on the table and reduces the time required by an attacker to brute force password.

There is no need to find the same password string in this type of attack. By comparing the two hashes, if the stored hash value is matched, it will be authenticated.

Disadvantages

Storage issue- Rainbow tables need to be of large size for making the attack more efficient and require a lot of space for storage.

Nowadays rainbow table attacks are almost obsolete mainly due to the increased use of the salted passwords.

Useless if a two-factor authentication system is implemented.

Preventing rainbow table attacks:

Salting: One way of defending against attacks using rainbow tables is by using salting mechanisms in hashing algorithms. Salt is a random collection of data that is passed on to the reduction function along with the plaintext and provides a different hash value for even the same input string.

Key stretching: Another method is key stretching, in which, the possible salt value, password and some random hash values are passed through the hash function multiple times to increase the computation time required to hash each password which can make a stolen passwords file less useful to a hacker as he would require more computing power.

Key strengthening: Expanding the key with a random salt and then deleting the salt value is called key strengthening. It secures the original password with a random value salt but renders a later brute force search from both the attacker and the user useless.

Less dependency on passwords: For authentication purposes either by implementing authentication mechanisms like biometric security or by using a two-factor authentication process that combines some other form of authentication along with the normal password-based authentication, threats can be minimised.

Use modern hash functions: Avoid using hashing algorithms like md5, sha1 etc. which are more vulnerable to rainbow table attacks. Use modern and more secure hash functions like sha3 instead.

Conclusion

Rainbow table attacks help compare a collection of hashes to another set of hashes known as a rainbow table. Rainbow tables make computations much faster when compared with other methods, and it still remains effective against unsalted hashes. It is imperative to keep up with the changing dynamics of password security to keep your business and users safe.

Why not give your passwords a go and find out more about statistical analysis through our password cracking exercise.