MD5 Rainbow Tables
From Computing and Software Wiki
Contents |
Overview
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.
What is MD5?
MD5 is a way for computers/servers to store passwords after applying an algorithm to the original password so that they become encrypted. This method is applied so that if a host compromised, then the passwords will still be encrypted. MD5 hashing is still used in many applications such as websites and forums, so MD5 Rainbow tables are a serious security risk.
What are Rainbow Tables?
Rainbow tables are tables which contain a hashed key and the real password associated with the hashed key. This essentially makes a rainbow table a lookup table.
How it works
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
Earlier, time-memory tradeoff was introduced, so what is the time-memory tradeoff in using MD5 rainbow tables?
Solutions
Adding salt as a solution
Salt, in security, is the act of appending a random number of bits 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).
Forcing Users to Use Unconventional Symbols
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.
