Protecting passwords from password guessing techniques

The OpenID Foundation met Apr 29th 2009 with NIST in DC to talk about their requirements for protecting against brute force password hacking. The decision was to define an industry best practice for use of CAPTCHAs to prevent online password guessing which would meet the INTENT of the current NIST requirements. The rest of this document describes a suggested industry best practice based on feedback from members of the OpenID community.

Section 9.2 of NIST SP800-63-1 lists a set of Authentication Process Threats. There is one additional threat that many identity providers need to consider:

Denial-of-service: An attacker performs repeated logon trials with the attempt to force the identity provider to lock the user out of their account for a significant period of time, or require the user/provider to perform some complex/expensive process such as out-of-band authorization of a user to reset their password. Example: Attacker uses a hard to detect botnet to sent a large number of random login requests to different accounts in the hope of degraing the quality of service provided by the identity provider.

Section 9.2.1 lists Other Threats. There is one other threat that many identity providers need to consider:

Usability: Identity providers for consumers, as opposed to for employees/contractors, need to make sure their account signup, account recovery, and authentication mechanisms are highly usable by non-technical users without requiring them to need customer support.

Then Section 9.3.1 describes Threat Resistance per Assurance Level and notes that for Level1, one requirement is to protect against Online Guessing of passwords. Section 9.2.2 has more detailed on Threat Mitigation Strategies for Online Guessing. The key description is that the provider's "authentication process is resistant to online guessing attacks if it is impractical for the Attacker, with no a priori knowledge of the token authenticator, to authenticate successfully by repeated authentication attempts with guessed authenticators." There are frequently two parts to that resistance. One part is using high-entropy passwords as described in Appendix A. The second part is to limit unsuccessful authentications.

For that second part, the NIST document describes some mechanisms such as forcing password resets, or temporarily disabling login attempts for a few hours/days, after a number of failed login attempts on an account. However in the last few years, attackers have determined that they can leverage those types of protections to create denial-of-service attacks against one or more accounts at the provider. This is primarily the case in consumer settings where the provider does not have a way to force password resets because there is no second factor of authentication and in-person-proofing is not feasible.

What providers can do instead is to use CAPTCHAs in a manner that is similar to temporarily disabling login attempts. Login attempts that meet certain risk levels can be required to answer a CAPTCHA before the provider attempts to validate the login credentials, thus providing resistance to online guessing attacks. While CAPTCHAs can be solved manually by an attacker, the cost of doing so is many orders of magnitude more then traditional brute-force password guessing, and thus is designed to make such attempts impractical. Thus, when properly deployed, CAPTCHAs can meet the intent of section 9.2.2 for an authentication process that is "resistant to online guessing attacks" and makes such attacks "impractical for the Attacker."

For the purposes of the the rest of this document, we will use the term "login resistance" to refer to techniques that will increase the resistance to online guessing attacks, such as CAPTCHAs or temporary disabling of login attempts.

The difficulty of deploying "login resistance" in this manner is to make sure it does not compromise the Usability of the identity provider as referenced above in relation to section 9.2.1. One simple option would be to add login resistance on all login attempts. While some providers may choose that route, that is not necessarily the only option, and it certainly will impact usability. Providers can instead use a risk-based strategy to identify the most likely online guessing attacks, and force those attackers to answer passwords. Some common examples of such strategies include the following:

1. Do not increase login resistance for login attempts where the IDP has high confidence that it comes from the actual account owner based on details such as cookies, IPs/subnets, client application type, time of day, or other details that match previous activity for the account.

2. After X login failures on any account, increase login resistance on that account for Y minutes.

3. After X login failures on multiple accounts using the same password (or a list of known common passwords), increase login resistance for that password on any account for Y minutes

4. For any logins from a pre-determined list of high risk IPs/subnets, increase login resistance

5. If an account has a long history of only logging in from certain cookies/IPs/browsers/etc. then after a very small number of login failures on that account, increase login resistance on that account for Y minutes.

6. After X login failures from a particular cookie, increase login resistance from that cookie for Y minutes

7. After X login failures from an IP/subnet (after adjusting for IP proxies), increase login resistance from that IP/subnet for Y minutes

8. For potential high-volume attack patterns that seem to be bypassing the login resistance (such as by answering all CAPTCHAs with high accuracy), increase the level (times/complexity) of the login resistance

The combination of strategies 1, 2, and 3 (or similar strategies) is one combination that can provide a level of resistance that meets the intent of Level 1. The other strategies are listed as examples of other techniques that can be used in addition, or instead of some of the first three, to achieve the desired security level of the identity provider. In addition to these resistance mechanisms, it is also suggested that providers attempt to minimize the amount of login resistance for actual users, otherwise attackers can force all users to encounter login resistance as a light-weight denial-of-service mechanism that hurts usability. The values of X and Y in the examples above do not have specific suggested values because the providers can vary their strategies in more complex ways. For example, in strategy 2, the value of Y might be increased if the account owner is normally not active during the time period of the failed login attempts. Providers should start with conservative values for X and Y, and then refine their algorithms both to improve usability, and to protect against online guessing attacks.

For a provider to meet the Level 1 NIST requirements for mitigating online guessing attacks using login resistance, they will need to be certified, or self-certify, that they use strategies that provide a comparable balance of security and usability as the combination of strategies 1, 2, and 3 above.