Going from unsalted to salted MD5 passwords

Question

I have a LAMP (PHP) website which is becoming popular.

I played it safe by storing the user passwords as md5 hashes.

But I now see that's not secure; I should have salted the md5 hash - because it's currently possible to decode unsalted md5 hashes using rainbow tables.

What can I do?

I don't want to make everyone type a new password.

Answer 1

You can do a "2 step hashing" instead of creating a hash in a single step.

You could append each password hash to the username, and then hash it again. This will create an undecryptable hash thats salted with unique informations.

The usual process of salting is

salt+PWD -> hash

You could do something like: PWD -> Hash -> UserID+Hash -> Hash

(Note the UserID was only picked so a unique salt for each double hash exists... Feel free to make your salt more complex)

Answer 2

You can salt them on the fly. Add a piece of code so that, when someone logs in, it does the normal process (computes the MD5 sum of the password and checks it against the stored hash) and if that succeeds, recompute a salted version of the hash from the clear-text password they entered, and store it in the password file.

The only wrinkle is that you'll need to add an indicator for whether each MD5 is salted or not, since you'll have a mix of both for a while. Or, for a minor loss of security, you can check each password salted and unsalted and if either one hits, accept the login. Of course, if you detect that it was unsalted, then you upgrade at that point.

Answer 3

The answer is simple, make sure the keep a record or some sort of flag of which users have passwords on the new system of hashing, when they next login, authenticate them, calculate the new hash, flip the flag.

Now whenever someone logs in and the flag is set, authenticate them with the new hash.