Skip to main content

How to calculate Password Strength (Part III)

This is the conclusion to a three part series on calculating password strength using a brand new algorithm that I've been teasing about for a while.

Read Part I and Part II for the earlier bits to this story.

If you are a programmer and just want the tl;dr nitty-gritty (i.e. the source code to my algorithm), then you will need to download the SSO Server and Client and extract the code from 'server/support/functions.php'. The two relevant functions are:

SSO_GetNISTNumBits($password, $repeatcalc = false);

SSO_IsStrongPassword($password, $minbits = 18, $usedict = false, $minwordlen = 4);

The algorithm I developed essentially attempts to break a password in an optimal amount of time (less than 1/4 sec). But how does one do that? The first step is to calculate the entropy of the password. NIST has done some work in this regard but they only published a set of suggestions not actual recommendations. The next step is to apply a threshold at some acceptable bit level that rejects bad passwords. Displaying a password strength meter is not sufficient.

When calculating entropy, it is important to not hand out bits. Be stingy. The NIST algorithm gets to be reasonably accurate when a password gets past 20 characters in length. Shorter passwords tend to not be very accurate. This is where the "suggestion" part likely comes from. What I've done is use the NIST algorithm as a starting point - a fast pre-filter. I've got both the original and a modified version of that algorithm that reduces character reuse values by 75% per character (e.g. the letter 'a' repeated many times is not a strong password).

The next step in my algorithm is to check for keyboard layout passwords and "tricks" (shift by one). For example, 'qwertyuiop' is not a strong password because it uses aspects of the keyboard's layout to come up with a password.

The final step is optional but highly recommended. The relevant SSO Server Generic Login module checks the password and keyboard sliding variations against a 300,000 word English dictionary. It only needs to check for the first matching word up to the minimum entropy level because "correct horse battery staple" is actually a strong password (a password phrase). Sentences generally make for secure passwords, so the Generic Login module encourages such behavior. Passwords should be able to be any length.

At each step of the process, the goal is to attempt to find a lower number of bits of entropy so that the password fails to pass the tests. Each test takes a little bit longer than the previous test. Still, rejecting 99% of all bad passwords at 18 bits of entropy (18 bits is roughly 8 characters long) is a fantastic solution to the problem of users selecting weak passwords.

The most important thing with calculating password strength is to do something with the calculation. Letting a user know that their password is weak won't do squat. You have to actually enforce it. Requiring a minimum number of bits of entropy is called thresholding. Any password that doesn't meet a minimum number of bits of entropy must be rejected if we want to rid the world of poorly selected passwords (a good thing). Using my algorithm with dictionary checks enabled, I've got a good set of rules in Part II of this series.

So there you have it, the anticlimactic conclusion of this nerdtastic series. Now get out there and do some password thresholding! Save people from themselves!