Is it safe to store passwords hashed with MD5CryptoServiceProvider in C#?

Question

We are storing hashed passwords in a database table.

We prepend each password with a random salt value and hash using MD5CryptoServiceProvider.

Is this safe? I have heard MD5 was "broken".

If not, can you recommend an alternate hash method to use (specific .NET framework class)?

Answer 1

The security of a hash function mainly comes from the length of its output (message digest): a longer digest gives greater collision resistance. The birthday paradox tells us that on average you'd expect to find a collision from a work function of the square root of the digest size: in other words, given a 128-bit digest, an attacker would expect to hit paydirt after 2^64 trials.

MD5 has been frowned upon by the cryptographic community for some years now because it only has a 128-bit digest, and there are also some interesting cryptanalytic results which might effectively reduce its strength. SHA1 (160 bit digest) had been the preferred alternative, but even then it is starting to look like it was not long enough for a well-motivated adversary and there are also some interesting results in the research community. The SHA-2 family (output sizes from 224 to 512 bits) are the current preferred hash functions in widespread use. There is an active research competition organised by NIST to find a successor for SHA-2, but we won't have a new standard until 2012 or so.

Now, in the specific case of storing passwords, I note you are using a salt. This is the strongly recommended practice; without a salt you would be vulnerable to a rainbow table attack. I believe that this leaves you with only the brute force attack to consider; this is where keylength.com comes in. It brings together recommendations for key and digest sizes from across the cryptographic community and gives expected security timescales for various algorithms, considering current computing power and taking Moore's Law into account. Consider what sort of assets you are protecting and how long you need to a password to remain secure for (do you have an enforced password change policy, for example?) and that should pretty much answer the question of the digest size you need.

Of course, the best password storage in the world won't help you if your users use easy-to-guess passwords. Do you provide your users with tips for strong passwords? Have you considered a password strength meter or similar?