1. Introduction
Nowadays, there are several mechanisms intended to provide security, privacy, and authenticity in the digital world. Among these mechanisms, we can find the hash functions. Hashing is a mapping technique that transforms a given sequence of bytes of any size to another sequence of bytes of a predetermined size.
It is relevant to note that hashing has many applications. For example, hashing is suitable for storing passwords and creating digital signatures.
However, as with every mechanism that aims to provide security, hashes have particular vulnerabilities. So, attackers exploit these vulnerabilities to breach the security mechanism.
In this tutorial, we’ll study a specific attack of hashing: the rainbow table attack. Initially, we’ll have an overview of necessary hashing concepts. So, we’ll investigate the central idea of a rainbow table. Finally, we’ll explore the rainbow table attack itself, showing a simple example.
2. Hashing
In practice, hashing is a mapping technique. It uses a function to transform sequences of bytes into other sequences of bytes. The data provided to the hash function may have variable lengths. However, the data generated within the hash function (called hash code or digest) always have the same length.
The following figure depicts the described process:
It is relevant to note that a hash function is a one-way function. So, it is not possible to recover the original plaintext input given only a hash code.
A characteristic of hashing is that exists a finite number of hash codes. The hash codes’ length defines this number.
Thus, as the input’s length is variable and non-limited, we map an infinite size set to a finite size set. It means that, at some point, different plaintext inputs will generate the same hash code. This phenomenon calls collision.
However, to solve collisions and get extra security layers, it is possible to execute an operation known as salting for hashing. Salting consists of reducing a hash code in a plaintext (different from the original input) with another one-way function and hashing it again, generating a distinct code from the previous one.
The following image intuitively shows the salting process of hashing:
3. Rainbow Table
Rainbow tables are pre-computed tables to revert hash codes to the original input plaintext. In short, these tables keep the original input plaintext associated with the corresponding hash code after some operations of hashing and reduction.
Rainbow tables emerged as a mid-term solution: they do not require executing all the hashing/reductions operations at every request and provide better security than using a lookup table associating straight hash code with the original plaintext.
Lookup tables, in this context, are basically rainbow tables with non-salted hash codes.
In summary, processing several hashes and reductions for each input requires lots of time. Otherwise, keeping all the possibilities of hash codes for a given input requires lots of memory.
By creating relations between plaintexts inputs and final codes, rainbow tables facilitate the general management of hashing operations.
The following image exemplifies a simple rainbow table:
4. Rainbow Table Attacks
In summary, a rainbow table attack compares stolen hash codes with a rainbow table of a given hashing method.
In such a way, the very first step of a rainbow table attack is stealing a list of hashes. Commonly, these hashes contain private information, such as passwords and credit card numbers.
Attackers can steal a list of hashes, for example, by exploiting vulnerabilities of poorly secured databases or by using phishing techniques.
After obtaining the hashes, the attackers compare them with rainbow tables intending to find some match between them and a table entry. If there is a match, the attacker gets the plaintext of the hash.
With the original plaintext input, the attacker can, for example, try to access accounts (if the plaintext corresponds to a password) or go shopping online (if the plaintext corresponds to credit card numbers and other information).
4.1. Example Scenarios
Usually, a rainbow table attack occurs together with other types of attacks. It happens since it is necessary to access a list of hash codes, which may require other attacking techniques.
Let’s consider a possible scenario: first, the attacker executes an SQL injection in a vulnerable web server to read the database. Next, the attacker searches for a password table and accesses its data. Finally, with the list of password hash codes, the attacker uses rainbow tables to get the plaintext data.
Another possible scenario is executing a distributed denial-of-service attack to breach the security systems (such as firewalls). Thus, the attacker can invade database systems, steal hash code lists, and execute a rainbow table attack.
4.2. Countermeasures
Besides securing the database keeping the hash codes, other countermeasures can be adopted to avoid rainbow table attacks. We describe some of these countermeasures next:
- Improve the security: a good option to prevent the consequences of a rainbow table attack from being catastrophic is not depend only on password security. Multiple factor authentication is a great option to improve security in this context
- Do not use easy passwords: frequent passwords, such as 0123456 and qwerty, are present in most rainbow tables. Thus, using large and unusual passwords reduce the probability of it being mapped in a generic rainbow table
- Use salting technique: salting makes it much hard to execute a rainbow table attack. Moreover, eliminating alphanumeric characters in the reduction operations can improve the security too
- Use modern hashing algorithms: obsolete hashing algorithms, such as MD5 and SHA1, are preferred for rainbow table attacks – it is a good idea to avoid them
5. Conclusion
In this tutorial, we learned about rainbow table attacks. At first, we reviewed the basic concepts of hashing. Thus, we focused on understanding what rainbow tables are. Next, we in-depth studied the rainbow table attacks. In this context, we explored concepts, scenarios, and possible countermeasures.
We can conclude that hashing is an essential technique for the current Internet. However, as well as any security technique, it has some weaknesses explored by malicious attackers. So, to keep our systems safe, it is essential to know these weaknesses and prepare the proper countermeasures to avoid possible attacks.