Back

# Fast hash decryption with rtgen and Rainbow Tables

Understanding what rainbow tables are and how they can help researchers and other's to crack hashes and recover plaintext values.

Table of Content

## Cracking systems

Breaking any encryption system can be done with unlimited time and unlimited computing power, both of which do not exist. Anything less than that unlimited power and time will require chance and good investigative skills. Several methods to break encryption include dictionary attacks, brute-force attacks, and rainbow tables.

## Rainbow Tables

A note on rainbow tables first:

They do not have rainbow colors

A rainbow table is a precomputed compilation of plaintexts and matching ciphertexts (typically passwords and their matching hashes). Rainbow tables greatly speed up many types of password cracking attacks, often taking minutes to crack where other methods (such as dictionary, hybrid, and brute-force password cracking attempts) may take much longer.

Though rainbow tables act as a database, they are more complex under the hood, relying on a time/memory trade-off to represent and recover passwords and hashes. Most rainbows tables can crack most, but not all, possible hashes.

So, in short, rainbow tables are created by precomputing the hash representation of passwords, and creating a lookup table to accelerate the process of checking for weak passwords.

## What are rainbow tables used for?

Today, passwords are no longer stored unencrypted - or so it is hoped. When users of a platform set a password for their account, this sequence of characters does not appear in plain text in a database on some server, as it would not be secure: if he could find a way into it, a hacker would have a very easy time gaining access to all the accounts of a given user.

For eCommerce, online banking or online government services this would have fatal consequences. Instead, online services use various cryptographic mechanisms to encrypt their users' passwords so that only a hash value (summary value) of the key appears in the databases.

Even if the originating cryptographic function is known, it is not possible to deduce the password from this hash value, because it is not possible to reconstruct the procedure in reverse. This leads cybercriminals to resort to brute-force attacks, in which a computer program tries to “guess” the correct sequence of characters constituting the password for as long as it takes.

This method can be combined with so-called password “dictionaries”. In these files, which circulate freely on the Internet, numerous passwords can be found that are either very popular or have already been intercepted in the past. Hackers first try out all the passwords in the dictionary, which saves time, although, depending on the complexity of the passwords (length and type of characters), this process can take longer and consume more resources than expected.

## Encryption technology

Since cryptographic hash functions began to be applied in encryption, algorithms have continued to evolve and standards that ten years ago were considered unassailable are now seen as serious security breaches. They all have one thing in common, however, and that is that the content to be encrypted is subjected to various algorithms until a hash value is finally generated. This summary value is usually a hexadecimal cipher with a fixed length, which does not depend on the length of the initial content. At the end of the process, for example, a hash value of 128 bits always results.

Three aspects are decisive in encryption:

• The same input always generates the same hash value: only then can this value function as a checksum. Is the key entered identical to the one in the database? The system only authorizes access when both hash values match.
• A hash value should always be unique: two different entries should not generate the same summary value, as only being unique can guarantee that the correct key is entered. As the number of possible hash values is limited, but the number of possible entries is not, it is impossible to rule out such matches, called collisions in this context. Modern hash functions and hash values of sufficient length attempt to keep this risk at bay.
• Summary values are not reversible, i.e. it is not possible to deduce the original content (the key) from the summary value. Therefore it is also not possible to decrypt summary values, as is sometimes somewhat inaccurately claimed. They can only be reconstructed.
• Hash functions must be very complex, but not too complex: if an algorithm works too fast, it makes the attackers' job easier and can no longer guarantee security. But the transformation should not be overly complex either, because it ultimately has to be put into practice.

## Reduction functions

The hash values contained in rainbow tables are not created during an attack, but beforehand, so that hackers can get hold of them and use them to find access keys. But since these files are very large, a memory-saving reduction function is applied. This function converts the hash value into a plain text - it does not return the original value of the hash value, i.e. the original password, as this is not possible, but generates a completely new text.

From this text another new summary value is created, a process that in a rainbow table does not happen only once, but many times, so that a string is generated. In the final table, however, only the first key and the last summary value of the string appear. With this information and using the same reduction functions it is possible to find out all the other values. The hash value to be broken is reduced and summarized again and again following the same rules, checking each result against the values in the table to find its corresponding key.

The challenge in creating a table lies in the fact that the initial word representing the beginning of a string cannot appear as plaintext in another preceding string.

This method can greatly reduce the size of these tables, even if they still have a volume of several hundred gigabytes.

## Rainbow tables properties

### Scaling properties

• Fast lookups means bigger tables, assuming coverage stays the same.
• Better coverage means either slower lookups, or bigger tables.
• Smaller tables means either slower lookups, or worse coverage.

### Rainbow table computation time

To understand Rainbow table computation time, lets see an example!

If a hash+reduction operation takes a $1 \mu s$, then generating a table with a $1 \cdot 10^6$ chains and $1 \cdot 10^4$ reductions per chain would take about $3$ hours: $$chainLength × chainCount / reductionsPerSecond / secondsPerHour =$$

$$1 \cdot 10^4 × 1 \cdot 10^6 / 1 \cdot 10^6 / 3600 = 2.8h$$

### Rainbow table lookup time

Usually, rainbow tables are considered to have a lookup time of $O(n)$

## Create rainbow tables with rtgen

Now the time to generate the rainbow tables. There is an utility called rtgen or rtgen.exe if you work with Windows. This tool is the rainbow table generator.

### Default supported charsets

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  numeric = [0123456789] alpha = [ABCDEFGHIJKLMNOPQRSTUVWXYZ] alpha-numeric = [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789] loweralpha = [abcdefghijklmnopqrstuvwxyz] loweralpha-numeric = [abcdefghijklmnopqrstuvwxyz0123456789] mixalpha = [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ] mixalpha-numeric = [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789] ascii-32-95 = [ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~] ascii-32-65-123-4 = [ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_{|}~] alpha-numeric-symbol32-space = [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#\$%^&*()-_+=~[]{}|\:;"'<>,.?/ ] 

### rtgen Command

To run rtgen, the command to be used needs to have following parameters

 1  rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index 

For example, to compute MD5 hash based rainbow table of length 1-7 and a chain length of 3800, we would use the command

 1  rtgen md5 loweralpha-numeric 1 7 0 3800 35000000 0 

#### Parameters description

• hash_algorithm: rainbow table is hash algorithm specific. Rainbow table for a certain hash algorithm only helps to crack hashes of that type. The rtgen program natively support lots of hash algorithms like lm, ntlm, md5, sha1, mysqlsha1, halflmchall, ntlmchall, oracle-SYSTEM and md5-half. In the example above, we generate md5 rainbow tables that speed up cracking of md5 hashes.
• charset: The charset includes all possible characters for the plaintext. “loweralpha-numeric” stands for “abcdefghijklmnopqrstuvwxyz0123456789”, which is defined in configuration file charset.txt.
• plaintext_len_min, plaintext_len_max: these two parameters limit the plaintext length range of the rainbow table. In the example above, the plaintext length range is 1 to 7. So plaintexts like “a” and “abcdefg” are likely contained in the rainbow table generated. But plaintext “abcdefgh” with length 8 will not be contained.
• table_index: the table_index parameter selects the reduction function. Rainbow table with different table_index parameter uses different reduction function.
• chain_len: this is the rainbow chain length. Longer rainbow chain stores more plaintexts and requires longer time to generate.
• chain_num: number of rainbow chains to generate. Rainbow table is simply an array of rainbow chains. Size of each rainbow chain is 16 bytes.
• part_index: to store a large rainbow table in many smaller files, use different number in this parameter for each part and keep all other parameters identical.

And that’s all. This is the basics about how to create your own rainbow tables. Remember that this is your only requirements:

• CPU time
• Enough storage space
• Patient

## Conclusion

Rainbow tables can be considered a time-memory trade-off: one stores only a small part of the table and recovers it through some extra computation on lookup time. Configure them wisdomly or buy already computed tables (that’s a business too)!

### How to protect data againts rainbow tables

Both MD5 and SHA-1 have been considered insecure for some time now and their rainbow tables are easily found on the Internet. With them, hashed keys can be found very easily. It is therefore the duty of the web administrator to keep up to date on the existence of new algorithms or the effectiveness of the hash function that has been used. SHA-2 and its best-known variant, SHA-256, are still valid, but SHA-3` has now been released, which promises even more security for longer.

Easy:

• Choose strong hashing algorithm with collisions resistance.
• Choose secret/salt based hashing algorithms.