There are two important risk categories here:
- Attacks on the live system (e.g. guessing a user's password)
- Attacks on offline password hashes (e.g. from a database dump)
The first type of attack can be split into various sub-categories:
- A brute-force attack on a user's password.
- Guessing the top 1000 most-used passwords on one user's account.
- Guessing the top 3 most-used passwords on 1000 users's accounts.
Password complexity requirements largely solve the last two categories, and makes the brute-force style attack much harder. When combined with proper rate limiting, all three categories can be effectively made infeasible. Traditionally the "live system" attacks were the primary driver for stronger password requirements.
The second type of attack usually occurs after your server is compromised. Despite everyone's best intentions and efforts, sites and servers do get hacked. You can't protect yourself from every possible attack vector, and that's a given in the world of security. You will get hacked at some point.
There are three major problems with having a database dump stolen:
- Private user data is leaked, often consisting of personal information.
- User passwords are leaked, either as plain text (if you're not doing your job!) or as a hash.
- Users re-use passwords across different services.
You cannot stop the private user data from being leaked. Attempting to reversibly encrypt or obfuscate the data in the database just leads to a layer of complicated abstraction in your code, and provides little or no security benefit. The best thing you can do is have rigorous quality assurance testing and security testing performed on your products, services, and infrastructure, in order to minimise the risk of having the data stolen.
However, you can protect the users' passwords. By hashing the passwords with a one-way cryptographic function, we can make it difficult for an attacker to discover the original plain-text password.
Standard techniques using MD5 or SHA1 alone were discovered to be flawed, since large databases (called rainbow tables) could be pre-computed ahead of time, allowing an attacker to look up a hash value in a table and find its corresponding plain-text password. This technique was combated using salts, which aim to make each hash unique to the user by introducing a per-user unique random value, which made rainbow tables infeasible. Attackers later discovered that hash functions could be computed in a highly parallel way by GPUs, using technologies like OpenCL and CUDA. Instead of a few million hashes per second on the CPU, attackers could now compute billions of hashes per second on a GPU, or hundreds of billions per second on a GPU cluster, all utilising nothing more than off-the-shelf consumer hardware and freely available software. This means that a pure sha256(pass+salt) type of hash is no longer secure. The alternative is a key-derivation algorithm that is designed to be slow, such as PBKDF2 or bcrypt. These are more difficult to compute on parallel devices like GPUs, and reduce the number of computations per second down to a level that makes a full brute-force infeasible. However, dictionary attacks will still be reasonably feasible, especially if common passwords are used.
So, in conclusion: no, I don't think we're putting too much weight on password complexity requirements. The attack vectors involved are complicated, and the computational power available to people today is high enough to make common passwords dangerous no matter how slow and computationally expensive the key-derivation function is. Users re-use passwords, so we must protect those passwords as best we can.
