Effective Account Lockout

If your application processes credit card information of any type, there are two requirements in PCI DSS 1.2 that should scare you to death - "8.5.13 Limit repeated access attempts by locking out the user ID after not more than six attempts" and "8.5.14 Set the lockout duration to a minimum of 30 minutes or until [an] administrator enables the user ID."

In my opinion, account lockout is one of those security controls that should be used sparingly and only in the most extreme circumstances.  My reasoning for this stance is that almost any lockout mechanism can be used by an attacker to purposefully deny legitimate users access to a site.  In its simplest form, this attack can be accomplished with a simple shell script that submits the proper parameter names over HTTP/S through cURL.  Knowing this, you should be asking yourself Why would PCI require me to implement something that could have such a dramatic effect on the availability of my site?.  The short answer, from what I can gleam, is that they are more concerned about preventing a breach of sensitive information than you performing any business transactions.  In essence, the lockout becomes the ultimate fail closed approach to security, in that if no one can access the site then the data stays safe.

So how can you overcome this obstacle, while still maintaining your compliance?  Here are a few possibilities that I have come up with.  Note that with any of the solutions below, the number of failed attempts needs to be reset to 0 upon successful login.

1. Implement the lockout mechanism to maintain a count of the number of failed login attempts in the user's unauthenticated session.  If this count ever reaches the threshold (six in this case) then lock the account by setting some flag in the database.  Although this appears to work, it has a major design flaw.  The count of failed attempts is maintained in the session until it is written to the database when the threshold is met.  For all but the most incompetent attacker, this implementation is easily bypassed.  All that is required to bypass this is to submit five passwords, send a new request without the session cookie (which effectively gives you a new session token with the number of failed attempts set at 0), and submit five more passwords with the new session repeating until the password is found.  Needless to say, this implementation is broken.

2. Modify the mechanism above to store the number of failed attempts in the database upon each failed attempt.  This actually gets us closer to what we really want, because it allows us to persist the number of failed attempts, but can increase overheard dramatically with numerous small updates to the database which are not always efficient.

3. Implement a mechanism that does not perform a lockout, but "meets the spirit of the control."  (Disclaimer: By no means am I trying to say here that you should try to skirt PCI, or that it is even possible.  What I am trying to show here is something that you may be able to implement that demonstrates you are implementing a compensating control that effectively provides the same level of protection as an account lockout mechanism without the potentially large negative impact to your legitimate users.) 

Obviously, the the control is being required so that sites will have something to prevent an attacker from easily brute forcing user's passwords.  My question is what about a mechanism that progressively delays the success/failed response, thereby making an attacker have to wait longer with each request to find out if the supplied password was correct.  Here is a sample with completely arbitrary delay offsets:
    Request 1  -->  Immediately return success/fail
    Request 2  -->  Wait 2 seconds, then return success/fail
    Request 3  -->  Wait 5 seconds, then return success/fail
    Request 4  -->  Wait 10 seconds, then return success/fail
    Request 5  -->  Wait 20 seconds, then return success/fail
    Request 6  -->  Wait 40 seconds, then return success/fail
    Request 7  -->  Wait 80 seconds, then return success/fail
    Request 8+  -->  Wait 160 seconds, then return success/fail

The key to this entire scheme is that the attacker still has to wait the full time delay before being told of the password was correct or not.  At no time other than the first request should the mechanism immediately return.

4. Modify option #3 and combine it with option #2 in such a way that the database is updated with each failed attempt, but you still maintain the progressive delay determining the time to wait on the latest value pulled from the database.  In addition, you could still lock out the account if a threshold was ever met.  Here is some pseudocode with completely arbitrary delay offsets and an assumed threshold of 6:
    Request  -->  if count < 1 then
                           count => 1; 
                           return success/fail;
                       else if count < 2 then 
                           count => 2; wait 2 seconds;
                           return success/fail;
                       else if count < 3 then 
                           count => 3; wait 5 seconds;
                           return success/fail;
                       else if count < 4 then 
                           count => 4; wait 10 seconds;
                           return success/fail;
                       else if count < 5 then 
                           count => 5; wait 20 seconds;
                           return success/fail;
                       else if count < 6 then
                           count => 6; account_locked_flg => 1;
                           wait 40 seconds;
                           return success/fail;
                       else
                           count => count + 1;
                           wait 40 seconds;
                           return account_locked_message;

Overall, I like option #3 the best, but if you want to combine these options in other ways I haven't thought of here, or have other solutions that you have come up with feel free to drop me a comment.