Rethinking Thresholds for Account Lockouts

One of my colleagues informed me that Conficker caused quite a few password lockout of administrator accounts at his company. The worm used a list of about 200 strings to perform a quick password-guessing attack on privileged accounts. Unless an account had no lockout policy set, then such accounts would be either compromised or locked out by Conficker. We can add DoS to the list of Conficker achievements.

But its not just Conficker that is locking users out of their accounts – in fact, users can do that all by themselves. We all know that quite a few help desk calls are simply requests for password resets of infrequently used applications, or even for frequently used applications where our recall has inexplicably failed us. NetWrix estimates that 30% of all help desk calls are for password resets. One is tempted to think that security policy is more concerned with keeping help desk people occupied than realistically addressing password guessing attacks.

Automatic account lockout is a counter-measure (or control in modern security parlance) for detecting and preventing password guessing attacks. Setting the account lockout threshold to be a small number such as 3 or 5 attempts is part of the conventional wisdom of security. The less number of permitted password guessing attempts the better. But we need to strike some balance here between our own unreliable memories and the persistence of hackers.

As is often the case, a little notation will help the discussion. Let’s assume that a policy defines N possible passwords, which we may represent as

A given user U will select these passwords according their personal preferences, and let the probability distribution

denote these preferences. Lastly let’s assume for simplicity that the passwords are ordered such that

which just means that password P1 is the mostly likely choice of the user with probability p1, password P2 is the next most likely choice with probability p2, and so on.

Now if we have a 3-strikes-you’re-out lockout policy then what does this mean in terms of our probabilities? Well, assuming the attacker follows the preferences of the user, then the policy states that we are prepared to live with three password guesses with a success of

but not with four password guesses with a success of

So the critical value here is p4 since it tips the scale from what is acceptable to what is not acceptable. We can represent this state of affairs in the diagram below.

But are our password policies really so brittle that we cross a security threshold from allowing 3 to 4 password guesses? I don’t think so. There is a threshold but it is certainly higher than 3 guesses.

I recently blogged about the approach taken by NIST to this issue. Their formulation of the problem was to find the smallest value of M for which

which leads to the following graph

That is, the NIST approach is to tolerate M password guesses as long as the likelihood of success is less than the threshold 2^{-k}. The particular values chosen for NIST were k = 10 (1 in 1,000) and k = 14 (1 in 16,000), depending on the desired level of security. It is challenging to compute the exact value of M but NIST has some estimates based on deploying policies which guarantee a minimum amount of entropy in user passwords (see Appendix 1 of this document).