Unfortunately, one cannot simply ask for password complexity.
What you really want, for password security, is that the password has a high entropy; but entropy is not a property of the password. Instead, entropy qualifies the way the password is chosen. "High entropy" means "the password could have been a lot of other values".
Usual "password checkers" cannot enter the brain of the human user, so they cannot really guess how the user chooses his passwords. Similarly, "password complexity rules" cannot ensure strong passwords; they just try to evict the user from his comfort zone, to avoid some classic weak password generation methods. But in practice, they don't work. Randomness is hard for human brains. Humans cannot make really random choices in the privacy of their minds; instead, they make witty choices. Also, they don't like to be forced to make pseudo-random choices. When password complexity rules are in force, the usual outcome is that users create witty workarounds, resulting in passwords which comply to the rules, but are not random; thus, weak passwords.
A typical case is when complexity rules mandate that a password shall have at least one digit and at least one punctuation sign: in practice, users react by systematically appending "1!" to whatever password they would have liked. So the rules make the password longer but not stronger. In fact, they even make passwords weaker because that kind of systematic suffix will still count as two characters with regards to password length. If your system enforces a minimum password length of eight characters, then people will need to choose passwords of eight characters; but if they append a systematic two-character suffix (and the attackers knows that, because the attacker is a smart guy who knows how typical users think), then they can get away with the password-length rule with only 6 actual random characters. In such a case, the password complexity rules backfire: they induce user behaviours which are detrimental to security, i.e. weaker passwords.
The only "complexity rule" which is sensible is a minimum length (typically 8 characters) because while a long password is not necessarily strong, a very short password is always weak, because there are just not enough possible 6-character passwords.
All of the above aims at explaining that user-chosen passwords will be weak, for a substantial proportion of the users. This is bad, but the point is that "password complexity rules" don't really improve the situation.
What can be done is the following:
Use a proper password hashing function. That's what you do with PBKDF2 (
Rfc2898DeriveBytes implements PBKDF2). Salts and iterations help cope with low entropy passwords, to some extent. You may want to increase the iteration count, though: chances are that your server could sustain much more than 1000 iterations, and the higher the better.
Try to make the question void. Password hashing must be used because it sometimes happen that attackers gain a copy of (part of) the server database, with all the hashed passwords; SQL injection, in particular, often results in such an outcome. However, it is much better if you prevent that. Password hashing is a necessary second line of defence, but that does not mean that the first line of defence is unimportant.
For online dictionary attacks, where the attacker talks to your server for each password guess, apply deterrents: if too many login requests come from a single IP in too short a time, temporarily ban that IP.
Educate your users. A good way to make users choose strong passwords is to provide a password generator. It is important that the generator is optional, otherwise users will feel it as a constraint, and refuse to use it. A generator can rely on actual randomness (that's a computer, it has
RNGCryptoServiceProvider) and thus meet a reasonable entropy target. A favourite password generation method of mine is an "aa00aa00" pattern (two letters, two digits, two letters, and then two digits). Such passwords are relatively easy to remember and to type in, and still provide a bit more than 32 bits of entropy, which is enough provided that you use PBKDF2 with a high enough iteration count.