Given the known weaknesses of MD5 and the recent (May 2009) weaknesses discussed in SHA1, how should new programs be salting & hashing their passwords?
I've seen SHA-256 and SHA-512 suggested.
Programming predominately in Ruby on Rails and using PostgreSQL -- but other languages and environments might also have to calculate password hashes.
SHA-256 and SHA-512 are safe for the foreseeable future. They belong to the SHA-2 family, against which no attacks have been identified so far. This wikipedia page says that Unix and Linux vendors are just now moving to SHA-2 for their secure hashing of passwords. The SHA-3 family, with even stronger algorithms, is being developed, but won't be ready until 2012 at the least.
P.S: Unless you're hiding secret agent names from governments, you'll be safe with SHA-1 as well, but if it's no trouble implementing SHA-2, just use that one instead.
You should use a hash username, password and salt together, like:
hash(length(username)+"_veryuniquesalt4rtLMAO"+username+password)
That way, your database is not vulnerable to any existing rainbow tables, because of the salt, and with the username hashed along with the password it is also impossible to create a rainbow table for your specific hashing method.
Using a "slow" hashing algorithm will secure the passwords better, just like if they were more complex, but it is a tradeoff, once you have decided on a certain level of slowness you can't just scale back when you need the performance for other things.
It is also possible to do the slow hashing clientside using JavaScript, that way it is not going to be a performance issue, but the method will of course require JavaScript to be enabled.
No matter what you choose, a little slowhashing is far better than nothing, use 1 millisecond instead of 1 microsecond and your protection is 1000 times stronger.
You can use bcrypt, or you can make a conventional hashing algorithm do a lot of extra work, just make sure that the extra work isn't primarily string concatenation.
In the end, better not get your database stolen, a lot of passwords are so weak that they are easily extracted no matter what you do.
You should use a password-based key derivation function as the uid/pwd result; the most werll known is PBKDF2 http://en.wikipedia.org/wiki/PBKDF2 also defined as RFC 2898 http://tools.ietf.org/html/rfc2898. PKBDF2 takes your secret data as well as a salt and an iteration count. This is the standard way of solving your problem.
If you program in .NET, use Rfc2898DeriveBytes http://msdn.microsoft.com/en-us/library/system.security.cryptography.rfc2898derivebytes.aspx