Crack Passwords with Google

This is an interesting story about how to crack passwords with a Google search.

If passwords are stored in clear text, an unauthorized access to password database would reveal all passwords. To avoid this, password are stored as result of a one way hash function that converts passwords into an irreversible format. This effectively hides the passwords. Mathematically, it is not feasible to find out clear text password even if result of one way hash of the password is known. This scheme is still weak. First weakness is that if two users choose the same password, one way hash of both passwords will be same; it makes it easier for an attacker to compromise two user accounts by cracking the password of one. Worse, if one of the users can get access to the password database, he immediately knows the password of the other user that has the same password. Second weakness is that if hashed password database is accessible, a dictionary of hashes makes it trivial to lookup the clear text password. The password cracking attack with Google relies on this second weakness. With hashes of many of the common text string easily searched through Google, passwords stored only as a one way hash are trivially broken.

Solutions to these weaknesses is to use salts. Salt is a set of random bytes that are appended to the clear text password before hashing. Salt is stored along with the hashed password and is visible to anyone with access to hashed password database. It solves both the problems. Same passwords now hash to different values assuming that salts are different (that is why it must be random) and dictionary of clear text hashes no longer allow easy lookup. Since, it is practically infeasible to generate a dictionary of all clear text passwords with all possible random salts.

To appreciate what happens to those passwords which we routinely use and rely on for security, we should know about some password management schemes and their relative strengths and weaknesses. Here is an excellent article on the topic.