What do you think about using services like this one for validating user password quality by checking if common hash databases does not contain password proposed by user - i.e. if hacking it using dictionary attack wouldn’t be to easy? Is this worth implementing such checking?
Nah, I would just use a more secure hashing method or develop some custom hashing method.
To make a password more secure use a salt. Basically consists on adding a random string to the user password.
Example:
a user enters password "123"
your system calculates a random string: "a1Kkmmdjen3321Mdr33"
your system encrypts the password adding both strings
$actualPassword = md5( $password . ' ' . $salt );
store the encrypted password
store the salt along with the password
whenever you need to check user’s password you will have to add the salt.
The result is that the user password is "123a1Kkmmdjen3321Mdr33"
And to protect login form from brute-force use a secure captcha and/or add a limit on login-tries per ip per hour.
I knew the idea with using salt (storing it along with password or in separate table field) but I wasn’t sure how much this alters security? I.e. is all this talking about rainbow tables or reverse hashing a bull shit when using random generated salt? Does it affects only strings hashed without using salt?
Using rainbow tables, you can crack a 5 char password hash in some minutes I guess (maybe less?). With a long and unique salt, the 5 char password hash becomes a 13 char password hash if you use a 8 char long salt. So if the user has password "12345" and salt is ").§0!X?*", then the final hash is much more secure (practical impossible to crack with rainbow tables).
Thanks for explaining this.
Using SSD disks a 14 char complex password can be hacked in 5 seconds.
If you haven’t heard yet about this… check this article - http://cyberarms.wordpress.com/2010/10/21/cracking-14-character-complex-passwords-in-5-seconds/
Adding the salt removes the predictability of the users password and quantifies the amount of possible combinations 
If my Math is right,
A 5 char password can have 916132832 possible combinations (upper, lower and numbers).
Where a 5 char password with a 5 char salt can have 839299365868340224 combinations.
Also a good idea to implement some basic checks so some numbers and upper case letters are used.
But that is LM Hash. In comments it says:
From Wikipedia:
I doubt this is possible with SHA-1.
But, if I’m not missing something, even this enormous speed (300 billion passwords per seconds) requires access to my website, to determine if currently tested combination is valid or not (a brute force access - cause how in other way an attacker would know which password is correct). Am I right? Then, implementing what Yii proposed - limiting login attempts to five per minute or something similar to that, would break even fastest password cracking routine. Am I right or do I miss something?
All this cracking stuff has an assumption… that you "somehow" got the MD5 hash from the victim database…
Then using Yii idea of storing salt along with password would be a nice approach to make crackers’ life harder even if they somehow get hashes:
And if we would extend it even further by storing in one field user password hashed with a random salt along with that salt again hashed by a constant build-in salt, the crackers’ life would become even harder, as they would have no way to determine, where hashed password starts and where hashed salt ends, right?
or to use a custom schema… like md5( md5(username)+md5(password) )
Sure, you can make the algorithm as tricky as possible. In the worst scenario an attacker would have access to your db and code. You can use a custom generation as mdomba suggests, store salts in a different system… but a supposed attacker eventually would know how to crack it too. It’s a never-ending discussion.
I think a salted password makes an acceptable trade-off between security and “paranoia”. Bear in mind that if you’re afraid that your passwords table has been compromised, you can simply generate a new salt and rehash you passwords (or you can do it on a monthly, weekly or dayly basis) so even if someone steals your data it would be useless!
As far as I know, the most secure hashing method is bcrypt. You can easily implement bcrypt with the PHPass framework. It takes care of salting passwords and supports fallback hashing methods if bcrypt is not available on your machine.
By the way: I would not recommend to use md5 hashes anymore. Attacks against md5 (and some other algorithms) are implemented for example in hashcat.
Yeap! And key to the success is to understand (and accept!) that there is no security method or solution created by a human, that another human wouldn’t be able to crack. Until we create artificial intelligence that will be able to build own security solutions, we can only make cracking process not-affordable long.
And talking about paranoia! :] What about idea of hasing passwords with random generated salt stored in second field in DB and hashed before storing with salt generated by third fields, which is user registration date? Building security upon three different variables?
I’m sorry, but this will be a dumb question. HOW can I rehash password if I don’t have source (plain password) as we are talking about storing in DB only hashed passwords plus salts? Rehash hashed passwords?
You’re right…my fault 
I didn’t think about it thoroughtfully enough. But you can regenerate salt and rehash everytime a user logs in.
About your other solution, hashing from several fields…is like making a salt fo 20 chars instead of 10…
Maybe I don’t know enough about hashing/cracking… but if you use md5(md5(password)+md5(username))… even if a hacker knows this he cannot use rainbow tables to get the password… the only way he can try to get the password and username is bruteforce and calculate those values… but this we solved by using the captcha and max login tries by IP or username…
I have read a lot about this subject the last couple of days. The most important thing to keep in mind is that the hash of the password is just one tiny part of securing your application. When a hacker has access to the users hashes he has probably full database access. The hashed passwords are probably the least interesting pieces of information the hacker will find in your database.
It is really easy to hash in such a way that it is too expensive for 99.99% of all hackers to decrypt the passwords. Use php’s hash_hmac function with for example sha256 or sha512 as algorithm. It is very important to use a unique salt for every hashed password. With the hash_hmac function you also need a constant key. You can save this key outside the database so that if your database gets compromised the hacker still doesn’t have access to this key. If you use hash_hmac with a unique salt you are done, nobody will decrypt the passwords within the next 50 years. But to be sure you can hash the resulting hash an extra 1000 times so that nobody will decrypt the hashes in the next 1000 years.
But remember, hashing is just a small part of securing your application. Other important aspects are:
Your hosting. What type of hosting do you use? Who has access to your server?
How can users recover their lost passwords?
How do you make sure users use a strong password which they don’t write down and don’t use for other applications?
Security leaks. Is you application XSS and SQL injection proof?
Which user has access to what data? How do you prevent them from leaking sensitive data?
Your connection to the user. Do you use SSL?
And a lot more…