how do you compute password complexity ?

Question

See also What is the best way to check the strength of a password?

Some applications (or websites) compute a password complexity when you type it. They typically display a red bar which turn orange, then green, then even greener as your password get longer, and contains more classes of characters (ie lowercase,uppercase, punctuation, digits...)

Here's the algorithm I use.

  private int GetPasswordComplexity(string password)
        {
            if (password.Length <= 4)
                return 1;

            int complexity = 0;

            int digit = 0;
            int letter = 0;
            int cap = 0;
            int other = 0;


        for (int i = 0; i < password.Length; i++)
        {
               if (char.IsDigit(password[i]) && i!=password.Length-1)
                digit = 1;
            else if (char.IsLower(password[i]))
                letter = 1;
            else if (char.IsUpper(password[i]) && i!=0)
                cap = 1;
            else
                other = 1;
        }

            complexity = digit + letter + cap + other;

            if (password.Length <= 7)
                complexity = Math.Min(3, complexity);

            return complexity;
        }

I'm concerned by the fact that my algorithm would rate "Password1!" as "very strong" and "]@feé:m" as "weak" because it's only 7 char's long.

EDIT : I've slightly updated the algorithm to ignore Capital letters and digits when they're respectively the first and the last char of the password.

Does anyone here has experience with this kind of problems? How would you add a dictionary to detect common words?

Answer 1

I would not simply set a flag when you see a digit, capital etc. but give points for them. Something like a score system. A normal letter counts 1, a digit 2 and a special character 3.

Now your total number accounts for both the number of characters and how the password is made up. You only have to draw lines for what is weak and what is strong.

Answer 2

I'd recommend using cracklib for this.

Answer 3

Using something like cracklib is very good if you can afford the time of checking against all of the potential rules. If you just want something quick -- say for a javascript-based strength meter -- then consider estimating the number of potential guesses that would be required for a brute force attack. For every character type seen update a multiplier based on the number of potential characters of that type. So if you have only digits, then the multiplier would be 10. If you have only lowercase, then the multiplier is 26. If both, then the multiplier is 36 -- that is for each character in the password, a brute force attack would need to try up to 36 different characters. A password containing both upper and lowercase characters, digits, and punctuation, then would have a multiplier of 10 + 26 + 26 + 32 = 94 (more or less depending on the allowable punctuation).

To estimate the average number of permutations a brute force method would take, raise the multiplier to the power equal to the number of digits in the password. This gives you then average number of guesses it would take to break the password using a brute force attack. Assume that each guess takes one cpu cycle and given the fastest processor calculate how long it would take to break a password given a certain number of permutations. For example, if my multiplier was 10 and the password was 10 characters long, then I would have 10,000,000,000 potential combinations. On 3GHz processor, this ought to take 10/3 * k or 3k seconds (where k is the number of cycles per guess, typically small). Clearly, this is a weak password.

Now, establish some ranges that represent reasonable password strengths. For example, if you think that an 8 character password with upper and lowercase characters is minimally required for medium strength, then your cutoff would be 52^8 or approximately 1.5 years on a 3GHz processor (assuming k = 1). If you add in digits, then the cutoff becomes 62^8 or approximately 8 years on 3GHz processor.

To put it in use, then you only need keep track of which kinds of characters you see, construct the appropriate multiplier, calculate the expected permutations based on password length, and compare it against your predefined cutoffs to determine what strength the password has.

Answer 4

You should also check against a dictionary. I think apple does this in it's built-in password checker.

Answer 5

Hi, I wrote a small Javascript application (GPL). Take a look: Yet Another Password Meter. You can download the source and use/modify it under GPL.