MD5 Rainbow Tables
From Computing and Software Wiki
A popular way of storing passwords for many websites, forums and other applications are through the use of MD5 hashing. When a user registers for a subscription and enters a password, that password is more than like passed through a MD5 hash function which outputs an encrypted key. This encrypted key is stored on a server, to keep a record of it for log in purposes. The next time the user tries to log in, they enter a password and this password is once again passed through the MD5 hash function and generates a temporary encrypted key. This temporary key is compared to the encrypted key that is previously stored and if they match then the server grants this user access. If the server is compromised, the attacker will only be able to retrieve a collection of hashed keys instead of the actual password of the users. However, through the use of MD5 rainbow tables, it allows the attacker to retrieve the original passwords as we shall see.
Contents |
What is MD5?
Message-Digest 5 (MD5) hashing is an algorithm which converts a message into a 128-bit encrypted key, often called a hashed key. This hashing method works as a one way hash, meaning that original password is not retrievable from the hashed key alone. It has been implemented by many applications because it is a standard in RFC 1321. Recently, researchers have discovered that MD5 hashed keys were not collision proof. This means that two different passwords, when hashed together can result in the same hashed key.
What are Rainbow Tables?
Rainbow tables are tables which contain a hashed key and the clear text message/password associated with the hashed key. This essentially makes a rainbow table a look up table, which allows an attacker to discover original passwords associated with a hashed key in a very short amount of time given that the rainbow table contains the hashed key. As one can guess, the more variations of hashed keys that are stored in a rainbow table, the more memory this table will require and the more time a computer would require to compile this table. This is known as the time-memory trade off.
How it works
Each time a cracker obtains a hashed key, they can try to retrieve the corresponding clear text message by getting a computer to brute-force attack the hashed key. However, for a message length of 7 characters, this may take hundreds of days; at which time, the message may no longer be relevant. When brute-force is used, a non-matching hash that was calculated would just be discarded, forcing the user to recalculate the discarded hash again the next time they stumble upon a new hash key.
Since the MD5 algorithm is just one single function that transforms a password to an encrypted hashed key after passing an algorithm, one can make a complete table of all the different combination.
The main key to using rainbow tables instead of cracking on the fly is that rainbow tables offer a time-memory tradeoff. Cracking on the fly may take a very long time with a much lower percentage of success. However, by having all the combination that are possible in a table, one can just compare the stolen hashed key to find a match in the table and they will have discovered the original password.
Time-Memory Tradeoff
Time-memory trade off is the act of sacrificing memory in order to reduce computation time or vice-versa. For our particular application of rainbow tables, we can demonstrate this idea by the following example:
One MD5 Hash entry in a rainbow table = 128 bits = 16 bytes
One character can have (26 uppercase letters) or (26 lowercase letters) or (10 numbers 0-9)* = 62 choices
In order for a rainbow table to store all the variations of 1 character with all the combination's, it would require 16 bytes x 62 = 992 bytes.
If we increase it to 2 characters, it would be 62 choices for the first letter and 62 choices for the second letter, giving a total of 3844 different choices.
To store this combination, it would require 3844 * 16 bytes = 61504 bytes ~ 60 kilobytes
Continuing this trend to 6 characters, we get 908803769344 bytes = 846.39 Gigabytes
| Number of Characters | Total number of variations | Total memory required |
| 1 | 62 | ### |
| 2 | 62x62 = 3844 | ### |
| 3 | 62^3 = 238328 | ### |
With a terabyte of space costing around 100 dollars in today's market, a rainbow table with all combination's up to 6 character can easily be stored.
However, if we increase the number of characters to just 1 more, we see that it will require 51.25 Terabytes. Costing about $5200 in order to store it.
[*]This is a very general scenario, most online applications allow special symbols such as @,# etc and even spaces.
Solutions
Adding salt
Salt, in security, is the act of appending a number of bits (random or defined) to a password to increase its length. For every salt bit we add to the password, the number of raw brute-force attempts required increases by a factor of 2. So say we add 32 salt-bits to a password, it increases the attempts required to find the original password to (4,294,967,296) x (length of original password).
Using Variety
Many researchers agree that MD5 hashing algorithm is full of flaws and that it is not longer secure enough. So instead of using MD5, people can employ a different hashing algorithm such as MD6, SHA or wait for SHA-3 to be completed. As mentioned earlier, the time required for a rainbow table depends heavily on the hashing algorithm. So by choosing an algorithm that is slow, even a fast computer will take a long time to compile a table with a modest amount of variations.
Adding to the Menu
For every symbol that a system allows a user to use, it increases the variations in a rainbow table by a factor. For example, if a system only allows lower-case alphabet letters as passwords and limited to 6 letters, then a rainbow table only requires 26^6 = 308,915,776 entries. If a similar system allows the use of an extra symbol (!,@,# etc) then the calculation would be 27^6 = 387,420,489, which is an increase of nearly 80 million. As mentioned before, most systems now use upper-case, lower-case and numbers, required passwords to be of length at least 8. This would require:
<math>62^{8} \times 2.18340106 \times 10^{14}<math>
As we can see, this number is still not much problem for a decent computer with enough space.
Frequently Changing the Order
By imposing a security policy which forces users to modify sensitive information, such as passwords, on a frequent basis, then there may be a chance that by the time an attacker finds a match in their rainbow table, the information that the attacker holds is no longer relevant.
Double the Serving
Another solution is to hash a hashed key. By hashing a hashed key, it increases the difficulty in finding the original message by many factors.
Links
References
See Also
External Links
--Yuw7 20:14, 7 April 2009 (EDT)
