Reminder: Encryption is Falling Apart

By on September 29, 2004

I started writing something that needed a password store today, and stopped myself short as I got all prepped up to store the passwords as a one-way MD5 hash. As we’ve reported earlier, MD5 isn’t all it’s cracked up to be these days. There’s no direct ‘crack’ of the MD5 algorithm, but collisions have been found, which, given the birthday paradox, halves the useful code distance. Researchers seem to think that MD5 may soon fail. In fact, collisions have been found in all of the major 128-bit ciphers.

I went hunting for another hash algorithm, and Wikipedia, as always, had some fantastic info.

MD5 has been widely used, and was originally thought to be cryptographically secure. However, research has uncovered weaknesses which make further use of MD5 questionable.
On 17 August 2004, collisions for MD5 were announced by Xiaoyun Wang, Dengguo Fen, Xuejia Lai and Hongbo Yu [1].
Their attack was reported to take only one hour on an IBM P690 cluster.

When it comes to passwords, it’s not so much the potential vulnerability of MD5 itself as it is the size of the input. As we’ve also mentioned, standard password protocols may not work anymore.

Given the speed of modern computers, and distributed tactics, it’s possible to compute and store every possible hash value within the range of good old 8-character letter-and-number passwords. A different algorithm only solves this until someone builds up a big image of hashes for your new cipher.

Here’s where we start to run up against the limits of the human brain. Users have found a way to cope with ‘8 characters, must contain at least one number’ and etc, but when you up that to 14 characters, you’re going to increase the rate of failure due to plain old human forgetfulness (and here come the sticky notes on the monitors).

Some of the sharp tacks in the Microsoft drawer are big on ‘pass phrases’ instead of passwords these days, that is, using (for example) the first letter of every word in the chorus of your favorite song. (The linked article seems to suggest that network admins drop lockout policies once passphrases are in place. So viruses can try all day? No spank you, pal.)

Soon, someone is going to have to take a big step forward by inventing a way to enter a more specific authentication mechanism that users will be able to pull off more easily (preferably without hooking some new gizmo to every computer in the world).

As for my immediate problem, I’ll be switching my hash algorithm to SHA-1, since it’s a 160 bit cipher, there are lots of readily available implementations, and as far as anyone knows, it’s never been weakened. (SHA-1 was developed in secret by the Men In Black, but if that scares you off, RIPEMD-160 will also supposedly do the deed. You’ll also need special headgear). I’ll have to rethink how the password policy works.

It doesn’t make much news since its mostly a bunch of math nerds pushing polynomials around, but one weak algorithm could bring down information security as we know it.

If you write any code that deals with passwords, you owe it to yourself to dive in to the linked Wikipedia articles and read up (I just learned most of this today, and see how smart I sound now?)

Have you dealt with these issues before? Changed your security policies? Put your head in the sand? Leave us a comment.



  1. That’s pretty interesting. I myself am getting ready to put in a password store in an app I am working on and was planning to just do it via MD5 as normal. Since there were some pretty strong recommendations against it in the Wiki, I guess I’ll do it as SHA-1. Of course, I’m pretty sure no one will be attacking my system and there won’t be too much to get from it, but better to make a change in practice now.

Comments are closed. If you have something you really want to say, tweet @gadgetopia.