Getting strong cryptographic algorithms was hard (centuries upon centuries of human study into mathmatics). But it's a mostly-solved problem now. It also turns out that this was the easy part. The hard part is useing these algorithms correctly.

I'm not a cryptographer. My math background isn't strong enough. But that's OK, because a lot of other people are cryptographers, and I can benifit from their studies. Further, people who are cryptographers often have little experiance with implementing their algorithms in real applications. So that's where I find my niche: practical application of cryptography.

I'd say that #1 was never really sound, but if you've read about and understand the problems of this approach, then keep it in. (Other posters seem to have mentioned this one, and I don't really have anything more to add).

For #2, I'd use a cryptographic hash with salt value (pseudo-code below):

hash( salt + hash( salt + plaintext_passwd ) )
[download]

You store the resulting value and the salt in the database. When you need to authorize a user, you put the password they gave you through the same hashing function and then compare it with the value in the database. The beneifits of this approach is that it is computationally infesible, even for the superuser, to reverse the function to get a plaintext password. The problems are that if a user forgets their password, you'll have to reset it to something instead of giving them the orginal password. Which I don't consider to be a big deal.

However, in your case, I'd be more concerned that the user's channel (HTTP) is not encrypted.

For #3, you'll run into the same problems with #1--how do you keep the master key safe?

The recent collision found in MD5, all on its own, is not a big deal. MD5 wasn't expected to last much longer (indeed, it was expected to fall a lot sooner). Cryptographers and security people have been discouraging the use of MD5 for years.

The big thing about this attack is that it might be extended to other algorithms. SHA-1 might be vulnerable, and we expected that to be good for a while.