In April of that year three RFCs appeared that covered MD2, MD4, and MD5. MD5 survived several years of cryptanalysis until a significant, practical attack was announced at the Crypto 2004 conference. Additional information appeared at the EUROCRYPT 2005 conference. Currently, the U.S. government only approves five hash algorithms: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512.
Note that the attacks against MD5 are based on cryptanalysis of the algorithm. This attack differs greatly from those based on "Rainbow Tables." A Rainbow Table trades the computational time required to discover, via brute force, the input value of a hash with the memory required to store all possible hashes for a set of input values. This technique, a time-memory trade-off, is hardly new. An IEEE paper by Martin Hellman described an approach to attacking DES in 1980.
However, the feasibility (and popular adoption) of rainbow tables also needed the cost of memory -- gigabytes to terabytes of disk space -- to drop. In 2008, it is trivial (though perhaps still expensive) to have three terabytes of disk space in a desktop computer. Consequently, the input value of a hash can be discovered in a matter of seconds or minutes rather than days or years. Rainbow tables are generated by running through a key space, say all seven-character alphanumeric combinations, once and storing the mappings between input value and hash. Any subsequent lookup merely requires the user to look up a hash value and then find the input value that generated it. In other words, all of the exhaustive brute force only needs to be executed by one user and the results shared with multiple users.
Rainbow tables can be generated for any algorithm, from MD5 to SHA-512 to certain modes of AES. They are based on simple brute force attacks rather than any underlying weakness of the algorithm. However, rainbow tables can also be trivially defeated.
Think of a rainbow table as something like this:
hash = MD5(input value)
Where hash is the result of an MD5 operation on input value. Typically, input value will be the complete key space of a length of characters (e.g. seven character alphanumeric).
Now, consider this small modification:
hash = MD5(salt + input value)
In this case, a fixed set of characters, the salt, is prepended (it could also be appended) to the input value to produce the hash. The salt doesn't need to be secret or even random -- it could be "apple" or "zombie." The function of the salt is to extend the length of characters used as the input and to prevent trivial hash comparisons. The combination "zombie" plus "password" turns an eight-character input value into a 14-character one. For an attacker who relies on a rainbow table to attack eight character passwords, the addition of "zombie" doesn't make the table any bigger, but it makes it different from the rainbow table for hashes without a salt. As a result, the attacker needs to rebuild the table -- which turns the problem back into a time-consuming brute force attack.
If your application stores hashed passwords, then make sure that the hashes are salted. It won't make the passwords more secure against phishing, sniffing, or replay attacks, but it can make them resistant to rainbow attacks if the hashes are compromised.
If your web application stores passwords in plain text, then it has more fundamental security issues.
0 quips:
Post a Comment