by M.L. Smith
Since 1976, the Data-Encryption-Standard has been the norm for protecting passwords. However, from its inception, academics have challenged its effectiveness. Now an asymmetrical algorithm called Rainbow Tables has taken the lead and become the stand-out contender over DES.
What you will learn:
a brief history of DES
Other challengers to DES
How Rainbow Tables work
What makes Rainbow Tables so effective
What you should know:
How to best protect your passwords
Protecting your smartphones
We always look for rainbows after it rains. Legend has it that there is a pot of gold at the end of the rainbow. That may not be true for rainbows in the sky, but in the world of computer software, rainbows can be a goldmine. Rainbow Tables have become a key to cracking passwords that have made many computers vulnerable.
ORIGINS OF PASSWORD ENCRYPTIONS
To understand how important rainbow tables are it is best to look at the history of password cracking prior to their development. In 1975, IBM was commissioned by the National Bureau of Standards (NBS) to develop an algorithm used to store passwords. Simply called the Data Encryption Standard (DES), its function was to fulfill a need by the US Government to protect unclassified but sensitive electronic documents. At this point, the information regarding DES is a little muddy. Even though it was the NBS that was in charge of the operation, there is some speculation that the National Security Agency or NSA became involved in the development of the DES for their own reasons. IBM has denied any tampering from the NSA. Originally, the Data Encryption Standard was designed with a key length of 128 bits. It is rumored that the NSA wanted the bit size reduced to 48 bits. Finally a compromise of 56 bits was agreed upon. After final approval, the Data Encryption Standard became the federal standard in November 1976. It remained the standard until it was replaced by the Advanced Encryption Standard (AES) in May 2002. The AES uses 128-bit blocks instead of the 56 bit blocks used by the DES. Despite its flaws and criticisms, the Data Encryption Standard opened the door for the academic study of cryptography. Before the DES, there were few cryptographers outside the military.
DES EARLY CHALLENGERS
One of the early non-military cryptographers was Martin Hellman. Hellman, along with fellow cryptographer, Whitfield Diffie, was an early critic of the DES. They felt that the key length was too short and would not withstand a brute force attack. The DES was designed as a symmetric-key block cipher with a relatively short key length of only 56 bits. Diffie and Hellman introduced the concept of the asymmetric key algorithms in 1976. Also known as Public-key cryptography, the idea was two keys or encryptions, a public plain text key complemented by a private encrypted key. This was a very early version of the encrypted hash value that is used today in most computers. The difference between a symmetric-key algorithm and an asymmetric-key algorithm is that the symmetric-keys use the same cryptographic keys for both plain text and cipher text. The asymmetric-key uses a different cryptographic key for each type of text. So attacking the plain text will have no effect on the cipher text and the password is still protected. Because of the assumed vulnerability of the Data Encryption Standard, various academics have challenged the DES's security over the years with a variety of proposed devices.
In 1977, Hellman and Diffie designed a machine that would cost $20 million and could crack a DES key in one day. In 1993, a key-search machine costing $1million dollars could crack a password in about 7 hours. In 1997, RSA Security offered a $10,000 prize to the first person or team to break a message encrypted using DES. That prize went to the DESCHALL Project. DESCHALL stood for DES Challenge. These machines devised to crack DES were all in theory until the Electronic Frontier Foundation, a cyberspace civil rights group, built a real DES cracker at the cost of $250,000. It took the EFF just over 2 days to force the key. Their intent was to show how vulnerable DES was in reality and not just in theory.
One of the biggest and most important attacks on the Data Encryption Standard came in 2006. The DES cracker was called COPACOBANA. Built by teams from the Universities of Bochem and Kiel in Germany, the significance of their attack was not just the time but also the amount of money and hardware used. The attack took about 7 days at a cost of only $10,000. They used reconfigurable parts which allowed them to use the machine against other code breaking algorithms.
TIME-MEMORY TRADE OFF
Previous to rainbow tables there were two ways to crack a password. These two methods were “brute-force” and “dictionary”. Brute-force is exactly what it sounds like. Numerous “attacks” are made on the password until finally all or at least part of it is broken. This took a tremendous amount of time. The second method, dictionary, took a great deal of memory. A list of possible matches is compared to the password until, hopefully, one hits and the password is cracked. Rainbow tables are a merger of these two methods. Referred to as the “time-memory trade off”, Rainbow tables became a combination of brute-force and dictionary.
Besides brute-force, there are several other types of attacks that can break all 16 rounds of the Data Encryption Standard. Even though these attacks were known in the 1970's when the DES was being developed, they were not considered feasible. Considering how far computer hardware and software have advanced in the past thirty years, they should be given a second look.
OTHER CRYPTANALYSIS TOOLS
Differential cryptanalysis discovery is generally accredited to Eli Biham and Adi Shamir in the 1980's. However, IBM was aware of differential cryptanalysis in 1974 when it was first developing DES. Differential cryptanalysis gets its name from studying how the differences in an input can affect the difference in an output. Differential cryptanalysis usually attacks block cyphers, which DES is, as well as hash functions. Differential cryptanalysis is a plain text attacker. To break all 16 rounds, differential cryptanalysis requires 249 chosen plain texts. Since IBM knew about differential cryptanalysis, DES was designed to be resistant to it.
Linear cryptanalysis involves designing linear equations that relate to plain text, cipher text and key bits. It was created by Mitsuru Matsui in 1992. Matsui was a cryptographer and senior researcher for the Mitsubishi Electric Company. He was conducting research on differential cryptanalysis when he discovered the technique of linear cryptanalysis. These two forms of cryptanalysis are the two most common types used against DES.
The Davies' attack is the third type of attack most common against the Data Encryption Standard. Donald Davies, a Welsh computer scientist, created it in 1987. He received a BSc degree in physics from the Imperial College London. Davies was an early pioneer in computer science. He is acknowledged as one of the two independent inventors of packet switched computer networking and the word “internet” can be traced directly back to his work. The Davies' attack is a dedicated statistical method for attacking the DES. The Davies' attack collects many known plain/cipher text pairs and calculates the empirical distribution of certain characteristics.
It seems from its very inception that the Data Encryption Standard was inviting challenge by the academic world. Because so many ways to attack the DES were already known, at least in theory, when it was created by IBM and so many more were created after the fact, the DES was almost obsolete before it was even in place. It is surprising that the DES lasted as long as it did with the US government. Being a symmetric-key algorithm left the DES vulnerable to attack.
HOW RAINBOW TABLES WORK
The first step in understanding how rainbow tables work is to look at how they were built and how a password is stored. When a password is created it is typed in using plain text. The computer then changes the plain text to a specific encrypted hash value and stores it in the computer's memory. The cryptographic hash function uses the Hex 16 character system; however it scrambles it, so using it to decipher an encrypted password would be useless. Before rainbow tables, the best way to try to break a password was to ignore the encrypted hash value and try different combinations of the plain text password. Reversing the process and attacking the encrypted hash was virtually useless. Rainbow tables do the opposite. It does not bother with the plain text password; it attacks the encrypted hash.
Rainbow Tables use two different functions: a hashing function and a reduction function. A hashing function is used to make plaintexts into hashes. The reduction function does exactly the opposite. It is used to make hashes into plaintexts. Rainbow Tables got its name because each column in rainbow tables uses a different reduction function. If each reduction function were a different color it would look like a rainbow.
A Rainbow Table figures out the password by using those two functions. The hashing function works to find the hashed password. Then after it is found the reduction function transforms that hashed value into something that is useable as a plaintext password. Before it can put those functions to the test a rainbow table makes all of these chains. The chains are constructed by picking a random seed value and applying the hashing and reduction functions to it. The hashing and reduction function are considered one-way functions. This works completely because the chains are also made up of one-way hashes and reduction functions. A chain can contain millions of hashes and all of them can be stored under two things: the starting plaintext and the final hash value that was chosen.
After the chains are finished and you have the starting plaintext and final hash value, the Rainbow Tables tries to recover the password. It goes through and looks for a match between the final hash and the link in the chain or the hash with an unknown plaintext you are looking for. If it finds any matches that means that the chain can be reconstructed and is reconstructed by hashing and reducing it. You then use the output of both the hashing function and the reduction function. The reconstructed chain is the key to finding the password. Eventually, you will come to both the known hash password and its secret plaintext, which is the real password.
Rainbow Tables are a very powerful tool. They are so powerful because the constructor can choose how much storage is retained. Storing all of those hash values would take up an extreme amount of memory. Rainbow tables utilize their ability to use a very low amount of memory, which saves you from having to save an unbelievable amount of hash values to your memory. The constructor chooses the amount of storage he/she uses by choosing the links in each chain. Rainbow tables are so powerful they are said to be able to crack the standard encryption used by Excel and Word in about five minutes.
Rainbow tables are not without their problems. One of the main problems is that collisions are a frequent thing when running it. Collisions happen when a given hash value is generated by multiple plaintexts. These collisions cause big problems for the chains. It makes a bunch of different chains merge into one. These collisions also cause the production of loops. Loops are created by a hash value reducing to a plaintext that has been hashed at a previous point in the chain. Another problem with Rainbow tables is that they can only be optimized if you are trying to crack complicated passwords. So, if you are trying to find a password that is common, or not complex at all, you will have a tough time.
SIM CARD ATTACKS
With technology advancing we now have access to these lovely devices called smartphones. We can do many things with them, including the use of mobile banking. Many apps require the usage of passwords, but mobile banking is the one that attracts most hackers. Rainbow tables can affect, and hack, the SIM cards on our phones. So it is not just our computers that we have to worry about. It only took Karsten Nohl, a cryptographer and security researcher, about one minute to crack the encryption key and hack onto a SIM card using a rainbow table.
The SIM cards have another downfall that allows them to be hacked further. They have a mechanism located in them called “sandboxing.” This mechanism shields programs like Visa and PayPal from the other apps and the SIM card. In some of the most frequently used SIM cards this mechanism is broken. It allowed Nohl to hack right in and access the files on a payment app installed on the SIM card. Nohl has estimated that out of all the SIM cards being used today, one eighth of them are still using data encryption standards from the 1970’s. This is something to consider when shopping for your next smartphone.
It doesn’t take long at all for the hackers to break into your SIM card. They simply send a hidden “sms” or short text message. Like blocking phone number, the hacker is sending a text message without his number being seen. The receiver's smartphone will reply to the message with the cryptographic signature the hacker needs. Then they use the rainbow tables to do the rest. Once hackers break the encryption on the SIM card, they can do anything from copying it to reprogramming it or even send premium text messages without the smartphone user even knowing. The most frightening aspects is that the hackers can redirect, or record phone calls and access billing/payment records.
It is quite disturbing to know that our private passwords can be so easily accessed. But like any hacker's tool, rainbow tables are also used for the greater good. Rainbow tables is just one of many programs and tools used extensively by government agencies and police forces on the federal, state and local level. Pedophiles, identity thieves, foreign and domestic terrorists have one thing in common; they all use computers to do business. When computers and other media devices are confiscated, the forensics team has the delicate task of retrieving information from the hard drive without damaging it. Rainbow tables makes it that much easier to crack the passwords.
There are many problems with using passwords for authentication; how easily the password can be guessed, remembering it, and how possible to intercept it across a network. To ensure safety, the storage of the registered password on the system must be performed so that someone with access cannot discover other users' passwords. When storing your actual password consider a web site with user login. Users of the website first register, and then once registered may login to gain personalized web content. Upon registration each user selects their username and a password of their choosing. Assume that the system stores these two values in a database, a website will have database tables that list the names and passwords in this manner:
There are obvious problems with this approach. One being anyone who gains access to this database can see other users' passwords. Such databases will not be publicly accessible; however within the organization maintaining the website there are multiple people who require read access to the database. This makes it very easy to view the actual passwords of other users. Although there is a potential security issue with using this method to store your actual password, in many cases, a user will trust the organization providing the webpage.
Worst-case scenario, the database becomes available to people outside the organization. For example, the security of the organizations computer system has flaws, and due to these flaws an unauthorized user can gain uncontrolled read access to the database. This user then has access to all of the users’ passwords. If they desired, the user can take this information and pretend to be another user on the website. Therefore, since many individuals re-use passwords across different systems, the unauthorized user can gain unplanned access to other systems.
There is a different method to storing hash passwords, opposed to storing the actual password in the database; a hash of the password can be stored. Assume a malevolent user gains access to the database, they can see the hash values, but because of the secure hash functions they cannot easily determine what the original password was. By storing the password in hash instead of the actual password, the system’s security significantly increases. The hash function makes it practically impossible to decode the password given you can only see the output hash value. Even with the use of the best-known systems, with current computing capabilities, it takes too long or will be too expensive to find the input password. But this is generally only true with inputs larger than the hash value. That is not the case with passwords. Most users choose short passwords that are from 4 to 8 characters; this, so that they are easy to remember and type in when logging in.
For some people it would take about 7 days to try to decode a password of this length. For other malicious users that re-use these values - because they can quickly check a known hash value against the set of pre-calculated values the process time – it can be reduce down to minutes or hours. Assume someone has already calculated all hash values; and they accessibly stored the hash value and corresponding password in a database. Then it is just a matter of performing a lookup with the users stored hash value against the set of pre-calculated hash values. Once a match is found so is the password. The advantage of this approach is that performing a lookup is much, much faster than calculating a hash.
The only problem with pre-calculated hash values is the storage requirements. Compression can be used to store the data, but most general purpose compression methods still would not reduce it to a convenient size. However by using data structures to store the information it is possible. Rainbow tables are one example of this type of data structure. When using this structure there is a significant reduction in the total storage space needed. So, rainbow tables make it much easier to store and distribute the set of passwords and hashes. A malicious user can quickly find a password and be given a hash. Some tests by Project RainbowCrack, show that if given a hash of a random password and using rainbow table, it only takes between 5 and 30 minutes to find a password.
PASSWORD PROTECTION METHODS
There are several ways to make it harder for unauthorized users that have discovered the hashed password database to use rainbow tables to quickly find passwords. These methods include:
1.Requiring longer passwords. A 9 character random password requires almost 100 times more space and time to generate the rainbow table; becoming much harder for the unauthorized user to manage. The downside is that requiring longer, random passwords is inconvenient for users. The password is harder to remember causing the users to put it on paper - leading to other security problems.
2. Use different hash algorithms/implementations to slow down the calculation rate. If, for example, hashes can only be calculated at a rate of 108 hashes per second (instead of 1010), then the time to generate the rainbow table would grow from 1 week to almost 2 years. This approach, however, does not help for existing algorithms (such as the popular MD5).
3. Use a salt before hashing the password, as explained below.
By requiring the user to increase their password length, it will be harder for unauthorized users to decode passwords, but inconvenient for users. An alternative is for the system to effectively increase the user’s password length by adding random characters to their chosen password or in other words add salt. The system chooses a random salt when a user creates an account and concatenates it with the password. After which it hashes the resulting value. So what is stored is a hash of the password with salt. The salt is also stored in the password database. With a 5-character salt, our example password database will be:
UsernameSaltH(password || salt)
John a4H*1 ba586dcb7fe85064d7da80ea6361ddb6
Sandy U9(-f 816a425628d5dee17839fffeafb67144
Daniel 5<as4 11842ced4203d4067ed6a6667f3f18d9
... ... ...
Steve LqM4^ 184b7f9c6126c568ee50cd3364257973
An unauthorized user can also attempt a brute force attack by trying all possible combinations of passwords. As the salt is stored in the password database, this user knows it so it provides no additional security. For each password they try, they must also concatenate with the salt for the appropriate user. Using this process it will take about 7 days to find the password.
But if the unauthorized user wants to use pre-calculated hashes or rainbow tables, this will no longer work due to the fact that rainbow table contains the hashes of passwords a salt. The user would need to use a rainbow table that contains the correct salt. In general, a separate rainbow would be needed for each possible salt. The amount of space and time needed to generate the rainbow has now been increased by a factor of 4 billion. This is obviously unachievable for the malevolent user.
An advantage of including a random salt before hashing the password makes the use of pre-calculated tables of hashes and passwords or rainbow tables ineffective. But note, in most cases it does little to prevent a brute force attack of hazing each password plus salt and comparing with the stored hash value.
Rouse, M (2006 July) Data Encryption Standard (DES). Retrieved from http://searchsecurity.techtarget.com/definition/Data-Encryption-Standard
What is the Data Encryption Standard (DES). (2012 March 21). Retrieved from http://www.cryptographicsoftware.com/index.php/encryption/what-is-the-data-encryption-standard-des/
Stanford University. (n.d.) Martin E. Hellman, Professor Emeritus of Electrical Engineering. Retrieved from http://www-ee.stanford.edu/~hellman/
Center for international security and cooperation (n.d.) Whitfield Diffie, consulting Professor. Retrieved from http://cisac.stanford.edu/people/whitfielddiffie/
Stackexchange, (2010, November 18). What are rainbow tables and how are they used [Blog post]. Retrieved from http://security.stackexchange.com/questions/379/what-are-rainbow-tables-and-how-are-they-used
Radcliff, D. (2007, March 01). Salting passwords thwarts rainbow table attacks. Retrieved from http://www.csoonline.com/article/221165/salting-passwords-thwarts-rainbow-table-attacks
Lemos, R. (2007, January 15). Rainbow table targets word, excel crypto. Retrieved from http://securityfocus.com/brief/407
Kuliukas, K. (2006. November 12). How rainbow tables work. Retrieved from http://kestas.kuliukas.com/RainbowTables/
Olson, P. (2013, July 21). SIM cards have finally been hacked and the flaw could affect millions of phones. Retrieved from
Security Research Labs (n.d.) Rooting SIM cards. Retrieved from
Whitwam, R (2013 July 22) Cryptographer cracks the SIM card, millions of devices may be vulnerable. Retrieved from http://www.geek.com/mobile/cryptographer-cracks-the-sim-card-millions-of-devices-may-be-vulnerable-1562875/
About the author
ML Smith is a recent graduate of California University of Pennsylvania with a Bachelor of Science degree in Justice Studies with a concentration on Forensics. Combined with her love of photography, she is especially interested in the field of steganography. She started her return to academics at community college and received a two-year full-ride scholarship to the Pennsylvania State University of her choice. She was also named a Cola-cola Foundation Bronze Scholar. Prior to returning to school, Ms. Smith worked for such companies as The Disney Channel and Amtrak. She served in the US Army from 1976 to 1980.