What are rainbow tables?

What sounds like a fun children’s game is actually a powerful tool for de­crypt­ing passwords. A rel­a­tive­ly large group of people on both sides of the law pour lots of energy into cracking passwords – either because they stand to profit from the criminal process or because they’re experts who regularly check security standards for ef­fec­tive­ness. Rainbow tables make it possible under certain cir­cum­stances to find out passwords within seconds.

Even if you’re not up to any criminal activity, it’s worth un­der­stand­ing the process. With this knowledge in the back of your mind, you can better un­der­stand as a user why complex passwords are necessary, and as a provider of a web offer what must be con­sid­ered to secure your passwords.

Passwords these days are (hopefully) no longer stored online without en­cryp­tion. When users set a password for their account on an online platform, the string doesn’t appear in plaintext on any database or server. This method would be far too unsafe: a hacker would only have to gain access to the database and could then im­me­di­ate­ly break into the accounts of each user.

For e-commerce, online banking, or online gov­ern­ment services, these would be fatal cases. Instead, online services use various cryp­to­graph­ic mech­a­nisms to encrypt their users’ passwords: only the hash value of the password appears in the database itself.

The password can’t be directly iden­ti­fied from the hash value, either – even if you know the crypto function. There’s no way to re­cal­cu­late the operation. Hackers use brute force attacks instead: with this, a computer program keeps guessing until it’s found the correct character sequence.

This method can also be combined with password dic­tio­nar­ies. These files – which can be obtained via the internet – contain numerous passwords that are either very popular or were captured during a previous attack on another system. This saves hackers time with the de­cryp­tion: First, they try all passwords in the dic­tio­nary. Depending on the com­plex­i­ty of the passwords (length and used char­ac­ters), this can cost some time and computing power, though.

Rainbow tables go a step further than password dic­tio­nar­ies, as they can also be found online, and can be used to crack passwords. These files, some of which can be multiple hundred gigabytes large, contain passwords together with their hash values along with the en­cryp­tion algorithm used. It’s not complete, though. Instead, certain chains are created from which the actual values can easily be cal­cu­lat­ed, which reduces the storage re­quire­ments of the still massive tables. With rainbow tables, hash values found in a database can be used to sort your passwords into plaintext.

To un­der­stand how rainbow tables function, you have to un­der­stand the basic workings of crypto-al­go­rithms. This makes it easier to see the benefits of the pre-made tables and un­der­stand the time-memory tradeoff.

Since cryp­to­graph­ic hash functions started being used in en­cryp­tion, the cor­re­spond­ing al­go­rithms have been changed time and time again. Standards that were un­crack­able 10 years ago are now con­sid­ered a serious breach of security. What they all have in common, though, is that the content to be encrypted still runs through al­go­rithms and a hash value is generated at the end. This hash value is generally a hexa­dec­i­mal number with a specified length. It doesn’t matter how long the original content is, because at the end it’s always a 128-bit hash value, for example. Three prop­er­ties are decisive for en­cryp­tion:

1. The same input always generates the same hash value, and is the only way that the value can function as a checksum. Is the entered password identical to what’s saved in the database? The system may only grant access if both hash values are the same.
2. A hash value should always be unique, so different entries can’t generate the same hash value. Only in this way can the function make sure that the correct password was also entered. Since the number of possible hash values is limited, but the number of possible entries isn’t, such col­li­sions can’t be excluded. Modern hash functions and hashes with a suf­fi­cient length minimize the risk as much as possible.
3. Hash values can’t be re­cal­cu­lat­ed: original content can never be derived from the hash value itself. This is why hash values can’t also be decrypted, as is sometimes vaguely claimed. Instead, hash values can only be com­pre­hend­ed.
4. Hash functions have to be rel­a­tive­ly complex – but not too complex: to ensure security, an algorithm can’t work too quickly, because that would also make the work easier for attackers. The con­ver­sion also shouldn’t be too complex, as it does still need to be applied in practice.

The hash values contained in rainbow tables aren’t created with an attack, but already exist be­fore­hand, meaning attackers can obtain rainbow tables and use them to find out passwords. These files are very large, though. So that the required storage space doesn’t get out of hand, rainbow tables use a reduction function that change the hash value into plaintext. Important: The reduction function doesn’t reverse the hash value, so it doesn’t output the original plaintext (i.e. the password) – because this isn’t possible – but instead outputs a com­plete­ly new one.

A new hash value is them generated from this text. In a rainbow table, this takes place not only one time, but many times, resulting in a chain. In the final table, however, only the first password and the last hash value of a chain appear. Based on this in­for­ma­tion and taking the reduction functions into account, all other values can also be de­ter­mined. The hash value to be cracked is then reduced again according to the same rules and hashed, and each in­ter­me­di­ate result is compared with the values in the table.

The challenge of creating a table is that the source content, which rep­re­sents the beginning of a new chain, can’t have already appeared as plaintext in a previous chain. With this tech­nol­o­gy, the size of such tables can be extremely reduced, and yet they still are several hundred gigabytes large.

A time-memory tradeoff is basically when you accept a longer runtime in favor of fewer memory re­quire­ments – or the other way around. A brute force attack takes up very little storage space, since the cryp­to­graph­ic cal­cu­la­tions for each attack are performed anew. A table, on the other hand, in which billions of passwords are presented together with their hash values, takes up an enormous amount of storage space, but can very quickly run de­cryp­tions. Rainbow tables represent a com­pro­mise of both. In principle, they also perform real-time cal­cu­la­tions, but to a lesser extent, and so save a lot of storage space compared to complete tables.

The initial situation: You have a specific hash value and would like to discover the actual password behind it. First, search through the list for the hash value. If it’s found either at the beginning or the end of a chain, then the password can be found rel­a­tive­ly quickly, so you only have to decipher the rep­e­ti­tions of the chain to get the desired result. But what happens when you don’t find the hash value in the table?

In this case, you start with a reduction of the hash value using the same function that was used to create the chains. The result then passes through the hash function. Repeat this until you find the hash value in one of the end points. This doesn’t give you the password you’re looking for, though. But you’ve now found the cor­re­spond­ing chain for the hash value. So, you now start at the beginning of the chain and carry out the re­duc­tions and hashing al­ter­nate­ly until you reach the desired hash value and the plaintext of the password.

At the end of the day, you may very well ask yourself what these tables have to do with rainbows. In practice, you can use not only a reduction function, but also a different one in each step. This provides better reduction results and avoids the rep­e­ti­tion of hash values in the table, but also has the dis­ad­van­tage that finding com­bi­na­tions of hash values and passwords in the chain is somewhat more complex.

The re­duc­tions then must be gone through in order: if you assume that the chain was built with the re­duc­tions R₁, R₂, and R₃, then you would start the search with function R₃. If this doesn’t return any results, then start with R₂ and then go to R₃, and so on. Within the table, the different reduction functions can be marked with colors, which leads to a colorful rainbow with a cor­re­spond­ing number of it­er­a­tions – and, the name.

The ex­pla­na­tion: The entered password is k. In this case, m is any mul­ti­pli­er (2000 in this example). Usually a quantity of the golden ratio (0,618) is set for A. Modulo (mod) extracts the remainder of a division, performed in this case by 1. The Gaussian brackets round off the result to a whole integer at the end, if necessary. The result h(k) is then the hash value h for input k.

Since our hash value consists of four digits, we fill out the beginning with a 0: 0408.

In a rainbow table for this hash function, reduction functions now need to be run. One very simple option for reducing the hash value is, for example, to use only the last two digits. So, in the case of the password 78 and the cor­re­spond­ing hash value 0408, the reduction is 08. A hash value is formed again from this with the help of the presented function, and so on.

The frequency of rep­e­ti­tions is up to you. The more often you run a rep­e­ti­tion, the less storage space the rainbow table needs – but the pro­cess­ing time increases. In this example, we run a reduction three times.

The above table shows the complete chain with the results of the hash and reduction functions. The goal of a rainbow table, though, is to shorten the range. That’s why, in the finished rainbow table, only the left and right columns of the table are included. All other values can be derived from these.

Now not all hash values are available in the table. If, for example, you knew that there was a password behind the hash value 1888, you would now search the created rainbow table and find that the value doesn’t appear in the table, but is hidden in a chain. Now you need to reduce the value, which results in 88. This value is also not part of the table, so you’ll re­cal­cu­late the hash value (0768) and the reduction (68). The cor­re­spond­ing hash value 0048 is in the third line. But the password in the same line (03) doesn’t belong directly to the hash value, so it’s only the beginning of the chain.

It provides a good starting point for the next cal­cu­la­tion, though: from 03 you can calculate the hash value 1708. This reduces to 08 and builds a new hash value: 1888 – the target hash value. So, the password 08 belongs to this value.

Now that you un­der­stand how attackers can break into user accounts using rainbow tables, it should also be clear that you need to use suitable defense mech­a­nisms. Both users and those re­spon­si­ble for the website can take measures to prevent such attacks, or at least make them more difficult.

For users them­selves, the following generally applies: passwords should be as long as possible and contain upper-case letters, lower-case letters, numbers, and other char­ac­ters – this helps against brute force attacks and rainbow tables, since it makes de­cryp­tion too elaborate. The length of the password also ex­po­nen­tial­ly increases the size of the required table. It’s also rec­om­mend­ed to not use any real words, but instead use random strings of char­ac­ters to protect against attacks based on dic­tio­nar­ies. A password manager could help with this.

It’s also very important – re­gard­less of which form of attack is being used – to not use passwords more than once. Once someone has managed to corrupt a database, decrypt the passwords, and access personal data, it’s easy to try out the exact same password on all other online accounts.

But server operators can also do a lot to protect users. To start with, you should obviously try to not let attackers access the databases with the hash values in the first place. But that’s easier said than done, as is proven by the large number of attacks on the servers of big companies. You’ll in­evitably need to secure the hash value. That begins by not using outdated al­go­rithms.

Both MD5 and SHA-1 have long been con­sid­ered unsafe, and cor­re­spond­ing rainbow tables are very easy to find online. Passwords that have been hashed this way can be uncovered within seconds. This is why it’s essential to keep yourself informed as to whether there are new al­go­rithms or how safe the used hash function still is. SHA-2 and its best-known variant SHA-256 are still con­sid­ered safe, but SHA-3 is now also available, which promises even longer safety.

To make de­cryp­tion using rainbow tables a bit more difficult, you can use something called salt: when a user sets a password, the system also creates a random value, the salt. This value flows together with the password into the hash function and so generates a different value than the password alone.

Salt and hash value are stored together in the database. This can be confusing: attackers who receive the contents of the database have the username, hash value, and cor­re­spond­ing salt. Brute force and dic­tio­nary attacks can’t be avoided, but the ad­di­tion­al measure par­tic­u­lar­ly helps against rainbow tables. Such a table is created in advance, based on a hash algorithm and in­de­pen­dent of the database being used. The salts also can’t be contained in rainbow tables, since the creator of the table didn’t know the salt yet.

Another benefit of salt is that the user can’t make note of it. This means they can be com­plete­ly chaotic and in­cred­i­bly long. It makes the hash values them­selves so complex that working with them is more difficult. A salt also prevents two or more people from entering the same password and so writing the same hash value into the database. Finally, salt helps with the problem that users insist on using the same password for various services. The stored hash value is different for each service, based on the salt.

In addition to salt, there’s also pepper: this com­pli­cates attacks with brute force or dic­tio­nar­ies. Pepper is also a random character sequence in­cor­po­rat­ed with the password in the hash value – best if combined with salt. As opposed to salt, pepper isn’t saved together with other login data in a database, but instead is separated and stored in as secure a location as possible.

Of­ten­times, a set character string is used for all passwords on the platform. So, pepper doesn’t help with the fact that several users have the same password, because they also use the same pepper – which leads to identical hash values. Ad­min­is­tra­tors should select a com­bi­na­tion of salt and pepper as a result.