What would be your recommendation for replacement of an MD5 hash approach to password storage within an MS-SQL database be?
I think: SHA256, SHA512 are more safe at this moment.
As of 2009, the two most commonly used cryptographic hash functions are MD5 and SHA-1. However, MD5 has been broken; an attack against it was used to break SSL in 2008. The SHA-0 and SHA-1 hash functions were developed by the NSA.
In February 2005, a successful attack on SHA-1 was reported, finding collisions in about 2^69 hashing operations, rather than the 2^80 expected for a 160-bit hash function.
In August 2005, another successful attack on SHA-1 was reported, finding collisions in 2^63 operations. Theoretical weaknesses of SHA-1 exist as well, suggesting that it may be practical to break within years.
New applications can avoid these problems by using more advanced members of the SHA family, such as SHA-2, or using techniques such as randomized hashing that do not require collision resistance.
See Wikipedia for more information.
Way back in 1978, Robert Morris and Ken Thompson published the Unix "crypt" password scheme with two innovations that are crucial for password hashing: salts and iteration counts. Without a salt, hashes are very vulnerable to hash tables and rainbow tables. Even with a salt, iterations are also needed to prevent very quick brute-forcing of most any password with 8 or fewer characters, to say nothing of simple variations of dictionary words. How long does it take to actually generate rainbow tables?
So please use a real hash designed for passwords - i.e. one that is slow and salted. Some good candidates are:
You can tune them to not take up too much server time, but people don't authenticate very often, so don't be stingy.
See also: Password hashing - IT Security
The most important piece of advice is to migrate to an algorithm designed for password hashing: bcrypt, PBKDF2, or scrypt. These algorithms are designed to meet the needs of hashing passwords; for instance, to deter dictionary attacks, they use iteration to ensure that hashing is slow, and to deter amortization attacks, they include a salt in the hash.
There is no need to migrate from MD5 to SHA. You may have heard that MD5 is broken. This is true, but not in a way that endangers MD5 for password hashing. The attacks on MD5 are on its collision resistance. However, MD5's one-wayness is still going strong. For password hashing, all that you need is one-wayness. Therefore, there is no need to migrate from MD5 to another hash like SHA256 or SHA512 (except possibly for "appearances" sake).
So, the most important thing you can do is switch to bcrypt/PBKDF2/scrypt to make dictionary search harder.
See also the following posts with excellent advice about how to hash passwords:
SHA-2 with salt works nicely. However you'll have to think about how to migrate the passwords.