Skip to content

Research: Even Password Complexity is a Tradeoff

Stronger passwords are always better—at least this is the working theory of most folks in information technology, security or otherwise. Such blanket rules should raise your suspicions, however; the rule11 maxim if you haven’t found the tradeoff, you haven’t looked hard enough should apply to passwords, too.

Dinei Florêncio, Cormac Herley, and Paul C. Van Oorschot. 2016. Pushing on string: the ‘don’t care’ region of password strength. Commun. ACM 59, 11 (October 2016), 66-74. DOI: https://doi.org/10.1145/2934663

Begin with this simple assertion: complex passwords are primarily a guard against password guessing attacks. Further, while the loss of a single account can be tragic for the individual user (and in some systems, the loss of a single password can have massive consequences!), for the system operator, it is the overall health of the system that matters. There is, in any system, a point at which enough accounts have been compromised that the system itself can no longer secure any information. This not only means the system can no longer hide information, it also means transactions within the system can no longer be trusted.

The number of compromised accounts varies based on the kind of system in view; effectively breaching an online banking system may require guessing 10% of the account passwords, while effectively breaching a social media site may only require guessing 5% of the account passwords. These numbers vary widely, so it is best to represent them as a simple curve. Below some point on the curve, the system is trustable (even though individuals are losing value!); above this point, the system itself is compromised.

There are also two kinds of attacks that can be used to guess passwords: online and offline. In an online attack, the attacker uses the normal access mode—the interface used to access the system—to guess passwords until they find one that works. In an offline attack, the attacker somehow obtains a file containing an encrypted form of all the passwords in the system, guessing passwords against this file very quickly. You can assume all offline attacks by a determined attacker will ultimately succeed; no matter how strong the door is, an attacker with a hardware store at their disposal, and unfettered access to the door, will eventually find a way through the door. There are password schemes that cannot be broken, even in off-line attacks, of course, but these are not practical for “everyday use.”

Protecting the password file is important. Even if the file is encrypted, or only contains hashes, an attacker with this file will ultimately obtain enough passwords to compromise the entire system.

Given your password files are well protected, this leaves on-line attacks. A key factor here is the rate at which passwords can be guessed. Does the system rate limit the number of bad passwords in any time period? Does the system blacklist IP addresses from which too many failed logins have been attempted (at least until manual intervention)? If an attacker requires a specific number of guesses to compromise an account, then controlling the rate at which an attacker can guess the password controls the length of time required to compromise a single account.

Rate limiting, blacklisting, and other forms of controlling on-line guessing are important. Even if some accounts are compromised, rate limiting allows the defender to see the action across a longer stretch of time, more time to analyze the attack, more time to counter the attack, and more information about which accounts might already be compromised.

The figure below might be helpful.

To the left of line 1 are passwords that can be guessed through on-line mechanisms only. Using rate limiting and other means can move line 1 to the left, making the entire system more secure. Forcing users to use harder to guess passwords can also move line 1 to the left, but not as much as other mechanisms. Beyond some point of password complexity, the difficult of guessing inevitably moves someplace between line 1 and line 2; in this area, the excess complexity does not add any further security against on-line or off-line guessing attacks. Going to the right of line 2, where off-line guessing attacks are ineffective, is extremely difficult.

Where is line 1 in the real world? It is hard to with any precision, as this will depend on the system being protected, the user population, and other factors. At the same time, we can be almost certain the requirements placed on users today—such as 8 characters in length, one from each character set—are beyond line 1, and yet far below line 2. There is little research, in fact, into how password strength, rate limiting, two factor authentication, and other security measures combine to produce an overall security stance.

So even with passwords—if you haven’t found the tradeoff, you haven’t looked hard enough.

Scroll To Top