Improve password hashing with a random salt

I'm starting a website and I'm trying to decide how to encrypt user passwords to store them in a SQL database.

I realize that using a simple md5(password) is very unsecured. I'm considering using a sha512(password.salt), and I have been researching the best way to generate a useful salt. I read numerous articles stating that a salt should be as random as possible to add entropy to the hash and it looks like a great idea. But:

• you need to store the random salt along with your hash
• given that an attacker somehow got access to your hashed passwords (and is trying to reverse the hash to plain text), it means he probably dumped your database, then got access to your random salts also

Isn't it obvious that the weird looking value next to the hash in the database is a salt? If the attacker can access the salt along with the hash value, how is that more secure?

Anyone has any expertise in that area? Thanks!

An attacker is "allowed" to know the salt - your security must be designed in a way that even with the knowledge of the salt it is still secure.

What does the salt do ?

Salt aids in defending against brute-force attacks using pre-computed "rainbow-tables".
Salt makes brute-force much more expensive (in time/memory terms) for the attacker.
Calculating such a table is expensive and usually only done when it can be used for more than one attack/password.
IF you use the same salt for all password an attacker could pre-compute such a table and then brute-force your passwords into cleartext...
As long as you generate a new (best cryptogrpahically strong) random salt for every password you want to store the hash of there is no problem.

IF you want to strengthen the security further
You could calculate the hash several times over (hash the hash etc.) - this doesn't cost you much but it makes a brute-force attack / calculating "rainbow-tables" even more expensive... please don't invent yourself - there are proven standard methods to do so, see for example http://en.wikipedia.org/wiki/PBKDF2 and http://www.itnewb.com/tutorial/Encrypting-Passwords-with-PHP-for-Storage-Using-the-RSA-PBKDF2-Standard

NOTE:

Using such a mechanism is these days mandatrory since "CPU time" (usable for attacks like rainbow tables/brute force etc.) is getting more and more widely available (see for example the fact that Amazon's Cloud service is among the top 50 of fastest supercomuters worldwide and can be used by anyone for a comparatively small amount)!

given that an attacker somehow got access to your hashed passwords (and is trying to reverse the hash to plain text), it means he probably dumped your database, then got access to your random salts also

The whole point of salting is to defeat "rainbow tables":

http://en.wikipedia.org/wiki/Rainbow_table

See why a sufficiently long salt defeats any rainbow table under the section "Defense against rainbow tables".

how is that more secure?

It used to be more secure because it forced the attacker to try a, back then, very costly brute-force approach instead of an instant looked in precomputed rainbow tables. If you had a 64 bit salt, the attacker needed to have 2^64 precomputed rainbow tables instead of one... In other words: it made rainbow tables useless.

Note however that modern GPUs can crack billions of passwords per second making it mostly pointless for an attacker to store huge rainbow tables (instead of storing billions of hashes, simply compute them in a few seconds).

Nowadays you want to store your "passwords" using something like PBKDF2 or scrypt.