Does larger hash size improve the security? Is it overkill to use 512 bit hash?
If I stored only 256 bits of the PBKDF2-SHA512 derived key, is it less, equal or more safe than 256 bits of PBKDF2-SHA256?
Edit:
Is the hash size only used to avoid hash collision, or does it improve security?
Is it secure if I only stored part of the hash (say the first 128-bits) of SHA-256 or SHA-512?
A larger output length makes it stronger, up to a certain point which is already reached, by a large margin, when you have a 128-bit output. Enlarging it any further does not change security.
Details: barring any structural weakness, the security of a hash function depends on its resistance to generic attacks (aka "luck": attacker tries random inputs until a match is found), and that resistance depends on the hash output size. For a hash function with an output of n bits, it takes effort 2n for the attacker to find a preimage (i.e. some password, not necessarily the "real" one, which matches the output). Efforts beyond about 280 are too far away into the technologically infeasible to be envisioned by an attacker. At 128 bits, you already have a 248 margin, i.e. a factor of almost 300 thousands of billions over that which was already overly expensive. It would be like boasting about reimbursing the US national debt while not having more than 0.01$ in cash.
Larger output size also help against collisions; there again, the generic luck-based attacks have cost 2n/2 (and there you see why SHA-1 has a 160-bit output: to make the collision cost of 280 unreachable). However, collisions are not an issue for password hashing. The ability to compute collisions does not give any advantage to the attacker. It so happens that collisions are also infeasible with usual hash functions, but if they were feasible it would not be that much a problem.
The real weakness in password hashing is not the hashing; it is the password. Or, more accurately, the human mind behind the password. Successful attacks on hashed password are attacks which try potential passwords, not attacks which work on the hash function structural weaknesses, if any. Mitigations include slow hashing and salting, which is what PBKDF2 does.
You can store only 80 bits or so of PBKDF2 output (and the salt); things will still be safe. (For purely aesthetic reasons, make it 128 bits: these computer people, they just love powers of two.)
Yes, a 512-bit hash is overkill. 128 bits is plenty.
Keep in mind that the security of your system is only as strong as the weakest link. The weakest link, in this case, is almost certainly the entropy of the user's password. Most users choose poor passwords that are readily guessable. Increasing the hash length does nothing to stop this attack.
For this reason, the most important thing is to use a password hashing scheme that is designed to slow down guessing attacks on users' passwords, such as bcrypt, PBKDF2, or scrypt. Choose a number of iterations that makes password hashing as slow as you can tolerate. Make sure to use a random salt, too. Make sure to use SSL to protect transmission of the passwords from the user to your site; I recommend you use SSL site-wide. Elsewhere I've offered other suggestions for how to improve the security of password-based authentication.
There's lots of additional information on this site about securing password storage. Try the search bar: it you should find all sorts of good tips and helpful advice.
While the security of any two hashing schemes is functionally equivalent onces its over ~100-bits unless there's some major flaw -- I wouldn't say a 512-bit hash is overkill. The length of a hash as long as its more than 128-bits is largely irrelevant.
Do you have enough passwords in your database that storing an extra (512 bits=64 bytes; 128 bits = 16 bytes) 48 bytes per user is significant?
Hell, many systems will store your hashes as ASCII hex-strings (meaning every byte takes two ASCII characters between 0-9a-f to store), which so you can often optimize down the size of your hashes by going to a binary blob if you want. However, you rarely don't care about saving dozens of bytes on a modern system. If you have a million users its still only an extra 48 MB, which is still trivial to throw hardware at. And we recommend using slow hashes (e.g., bcrypt/scrypt), the performance issues of fetching/comparing the hash are irrelevant (in fact larger hashes are slightly better in this respect as they'll be slightly slower).
I use SHA-512 crypt on my linux systems. (This is not a simple sha-512 hash; but by essentially 5000 (default) rounds of SHA-512.) I don't use this because I need more than SHA-256 crypt, but it was the default with my distro (and the extra 43 bytes per user is completely irrelevant (its in a base64-like encoding)). It has the added small benefit if a future attack on SHA is ever found that reduces its complexity significantly, I started from a much safer starting location. (E.g., if you find a pre-image attack that makes it simpler by a factor of 264, 128-bit hashes are compromised while 256/512-bit hashes would be fine).
