Last year there was a lot of press around how MD5 was finally proven to have significant issues. Then there was a bit of an uproar in the webappsec community around abandoning it for other safer hashing systems. When I first read the news, I was really saying to myself, “Well, even if it wasn’t broken in this way, rainbow crack is a more significant threat to hashing algorythms than anything else anyway.” Rainbow crack uses a time memory trade-off by precomputing all hashes. (It gets is name because the tables sorta look like a rainbow if you gloss your eyes).

I wouldn’t even bother using L0phtcrack anymore now that rainbowtables is in existance and free versions availible by the schmoo group. There are even companies that sell rainbow tables on CDs and talk of a distributed rainbow tables project.

MD5 isn’t broken. It’s got a flaw, yes. For normal password length strings, it’s broken by time-memory trade off. But is it broken for web application use? I dare say no.

What is a hash? A hash is a one way algorythm (at least in theory) that in general has non-repudiation built into it (that’s one of MD5’s flaws actually - for any plaintext it should create just one hash, but in reality multiple plaintexts could end up being a single hash). To put it in simple terms, a hash is a mathematical computation that creates an answer that is very difficult (impossible) to derive the question from.

Where are MD5 hashes generally used? There are two places I see MD5s in wide use in web applications. The first is in password storage. Okay, you got me, MD5s are an issue for password storage as rainbow crack shows. The second usage is in cookies. People often hash long strings with a regularly changing secret string (or salt) to compute a hash that they include in the payload of the cookie. Cookies that are tampered with will not match the hash and the website can detect that the cookie has been compromised.

Rainbow crack really is a great tool, but it has one major flaw in it. It takes a LOT of time to calculate every known hash of every password and worse yet, a lot of space to keep them all organized. Passwords are generally less than 8 characters, but even still, I’ve seen passwords that can get up to dozens of chars long (like GnuPG or PGP passphrases, for instance). What about long strings, like cookies? Cookies are arbitrary things that can be any lenght (well, in reality they must total less than 4k otherwise Internet Explorer can’t deal with them in JavaScript space). So let’s just use 4k as a hard stop.

Four thousand characters is slightly longer than say, 8 (the size of a normal password) to say the least and even with 8 characters you are talking about a CD sized rainbow table disc of possible combinations. With every extra digit you add an order of magnitude. Given the size of the total possible combinations of a cookie, even though rainbow crack can technically do what I am proposing the amount of disc space to generate such a table would be ultramassive, and far beyond the scope of the rainbow tables projects. Will I continue to use MD5 in web applications? Of course! It’s a valuable tool. Will I rely on it for password integrity alone? Absolutely not. Is it broken? Sorta.

This entry was posted on Saturday, June 24th, 2006 at 4:17 pm and is filed under Webappsec. You can leave a response as well.