As I'm sitting here in FAIR training this week in Cincinnati, I've been starting to apply rational thought to some of the staid and true "best practices" that have become cornerstones of our industry. To me, password complexity has always been somewhat ridiculous, since given enough time any captured password can be broken. This leads me to wonder, what are the common threats passwords, and how does password complexity help protect against those threats?
Sitting here thinking about it, I think there are three common scenarios against which we're developing controls:
1) Brute-forcing an authentication interface.
2) Brute-forcing a captured password hash.
3) Guessing passwords (not using automated controls).
Brute Forcing - Authentication Interface
In this scenario, some malevolent force is attacking an authentication interface using an automated tool in an effort to break an account via brute force. These attacks have historically been quite common, and I imagine will continue to be. However, at the same time, there are fairly easy methods to protect against outright brute-forcing that have nothing to do with password complexity. Specifically, if an interface experiences a login failure N number of times consecutively for a given account X in a time period of T, then the account should be locked, preventing any further attempts.
Similarly, if you're seeing a high number of login attempts from a single IP address, then it's likely a bad actor and should be blocked. Whether those logins are failed or successful ends up being less important than the number of tries in a short period of time from a common source (though there are obviously exceptions to this rule - e.g. logins from behind a NAT gateway). In general, though, if you monitor source IPs for failed logins, then you can often build a reasonable trigger for an IP hold-down.
Notice how none of this is really impacted by password complexity rules.
Brute Forcing - Captured Password Hash
Let's now assume that a password database has been captured and that the attacker knows how to hash passwords in the same way that the database of password hashes were generated (I'm assuming hashing here, but obviously encryption could be an option). Under this scenario, historically, is where we would have started saying "ah-ha! password complexity matters!", but today that is pretty much not the case. With the advent of rainbow tables and cloud-based password cracking services, while you may be able to encourage mild resistance to cracking with password complexity rules, the sad reality is that it represents a minor speed bump.
Allow me to say this more clearly: If your password database is compromised, then you are SOL and should not hang your hat on password complexity rules. Rainbow tables and cloud services make cracking cheap and trivial. Therefore, password complexity is not your primary control here. Instead, protecting your password database is far more important, as is being able to detect the compromise.
Guessing
Here we have an area, finally, where password complexity seems to have a part to play. After all, our primary tool against easily guessable passwords is to simply not allow them by requiring complexity. Or is it? When you take brute forcing off the table as a threat, then here you're likely looking at more of a lowest common denominator situation. Instead of focusing on complexity, then, we're really concerned about prohibiting values that would be easily guessed, which means no dictionary words and no obvious strings of numbers (that could be things like key dates in a user's personal history).
If you take this point as true, then it potentially changes our approach to password strength. It means that what we consider to be truly "weak" passwords are a fairly small population, generally limited to words and dates. However, where we find the interesting challenge is how you systematically enforce a policy that says "no words or dates." Consider a few examples (again, in the context of guessability):
* Falcon - a weak password
* Falcon99 - maybe a weak password, depending on the significance of 99
* 9Falcon9 - less weak password, again depending on the significance of 99
* Falcon! - less weak, perhaps, or then again, maybe not?
* F4lc0n - not a weak password
* 01011999 - likely a weak password, assuming Jan. 01, 1999 is a notable date
* ThisIsMyPassword - not a weak password, or at least not easily guessed, right?
The problem here is in defining an algorithm that can easily prevent guessability. Herein, I think, lies the answer in how we've arrived at this point of defining password complexity rules. However, I have to wonder: does it really matter? How often are we dealing with manual password-guessing attacks? And, more importantly, how hard would it be to embed a language-specific dictionary in an authentication mechanism. Or, failing that, what about using spell-checker logic instead of password complexity rules? Of course, in the last example above, the password would likely fail a straight dictionary check (since there are 4 words), and yet the password is probably fairly strong, or at least not easily guessable.
Lessons Learned
Walking through this narrative-based analysis, as well as performing a limited FAIR analysis on the side (for class we had a very narrow context focused on guessability with specific asset and threat profiles), it seems that password complexity requirements, in and of themselves, are fairly pointless today. Manual guessing of passwords seems to be the only case where password complexity provides much value, and this can be impacted with a more-or-less rudimentary scheme that picks off dictionary words and numeric-only strings. Beyond that, the value seems to diminish quickly.
Recommended Controls
There seem to be a few common-sense controls that make sense in general, perhaps more so than password complexity requirements.
* Failed login lockouts: Multiple failed logins on a single account in a relatively short time period should result in an account lockout.
* IP hold-downs: A high rate of failed login attempts from a single IP in a relatively short time period should result in the IP being temporarily blocked. Multiple ongoing attempts over time from the same IP should result in a long-term block.
* Protecting against capture: Access controls, such as at the file system level, should be leveraged to minimize the ability of an attacker to capture the password database.
* Detecting attacks: Similar to protecting against capture, it's also equally (if not more) important to detect when a compromise has occurred. To that end, it may actually be useful to setup special audit mechanisms to analyze file access (including copying) for suspicious behavior.
* Eliminate easily guessable passwords: Perhaps a bit trickier to implement, but it really does seem that you really only need to prohibit dictionary words and numeric-only strings. Perhaps instead of writing algorithms for complexity, we should instead focus on password length. Consider, for example, requiring a password with a minimum length of, say, 16 characters (whatever seems reasonable in terms of the average length of words). I don't, then, care if it's a string of all numbers or all letters or a combination thereof, so long as it's long and easily remembered, but not easily guessed. By making it longer than the length of the typical long words (note that the longest word in this section has been 12 characters) this will generally force people to use a modifier that makes guessability that much more difficult. If people combine two or more words, then that's ok, right? Well, maybe, unless it's a first+last name. Hmmm... :)
Diminishing Returns
What becomes clear in analyzing password complexity is that the law of diminishing returns quickly kicks in. How common are manual guessing attacks? How much of a threat is there? Is it really worthwhile investing much in password complexity? The word "password" is 8 characters in length. If you require a password that is at least 12 characters in length you've now eliminated "password" as a viable choice. What else do you need to do? I'm sure some may argue vehemently against this perspective, but in the grand scheme of things - particularly taking into consideration modern password cracking methods - your concerns around passwords really have very little to do with picking "strong" passwords rather than with implementing controls to limit the effectiveness of given attacks.
So, what do you think? Ready to toss out password complexity in favor of a basic length requirement? :)
Agree with all of your points, but aren't all the 'rules' admins enforce really just to get regular users to stop using trivial passwords? Regular users could care less about security implications, and want the process to be as painless as possible, no? Rules and algorithms to prevent users from being 'lazy' will never quite cover them all. Not to say that we don't need them - they're probably 'good enough' to keep the majority of folks inline. Of course, too high a bar results in other issues, like passwords written on post-it notes. I suppose multiple use passwords + regular users = always have issues.
@Julie -
I think the various rules sort of exist to defeat trivial passwords, but much of those complexity rules seem to be oriented toward defeating brute forcing, which I think is no longer viable. If you're then just looking to defeat simple dictionary word passwords, then length seems to be about the only real "complexity" requirement that you need. Don't want people to use "password" as their password? Require a 9+ character password.
Of course, along these same lines, it also lends more credence to promoting use of passphrases instead of passwords (a practice that's never really made it in the mainstream, in part I think to the bias toward (useless) complexity rules).
Thanks for the comment!
-ben
Awww come on, Ben, 1995 called and it wants its cutting-edge security back. =)
Yes, brute-force attacks do occur. Distributed SSH scanning is a personal favorite of mine--if you block an IP address, they scan from a different one.
If you're worried about password complexity, you need to not be using passwords. In the SSH example, switch to using RSA keys.
@rybolov -
Of course brute-force attacks on authentication interfaces happen (as I noted). However, password complexity is not generally your primary control against that. You use account locks based on failed login attempts, you use rate-limiting, you use IP hold-downs, etc. And sure, a savvy attacker is going to hop IPs (I've seen it first-hand, too), but password complexity still seems to have a minimal utility.
As for SSH keys - that's a whole different topic and really bears no relevance to this post on password complexity. I'm not "worried" about password complexity. In fact, just the contrary, I increasingly find it to be stupid. *shrug*
-ben
Been working on this vary thing the past week. Notice you didn't reference Spaf's post on this (http://www.cerias.purdue.edu/site/blog/post/password-change-myths/)
Anywho, I came to almost the same conclusions as you with a few additional tweaks.
One, password length at length 12 or better makes Rainbow tabling a bit harder (check out what you can buy and you'll see they're < 12 chars)
Frequent required password changes are also not a significant defense. I like 90 days but some "best practice" dolts thing 45 or 60 is better (for no reason they can explain)
@dunsany -
Thanks, excellent points! I wrote this post mostly offline after a discussion in a training class this morning, so didn't have time available to ID other resources on the topic. I know Spaf has written on this, as has Schneier an others. Thanks for providing the link!
As for length, yes, I agree. Someone here in the class thought the tables were now up closer to 14 characters in length. Also, I couldn't remember specifics off the cloud password cracking services publicized over the past few weeks. At any rate, I presume this number will continue to increase until it becomes pointless. :)
I'm right there with you on change frequency, too. Especially if you can improve detection capabilities that would catch an unauthorized copying of a password database. I'm not convinced that routine password changes really "solve" any particular problem here in a 2010 context.
Thanks for commenting - good stuff! :)
-ben
This is a a very technical and systems lens -- think about how an identity and AAA type specialist sees passwords. In their world, passwords are one of the things they rely on to know an authenticating user is very likely the person they're claiming to be -- so they want that password to be as reliable as that (dated, limited) technology can be. A weak, guessable, trivially bruted password is just not a very good credential for that use, so they'll attempt to define "good" ones. The access controls etc. they administer will depend on this. Now, shops this concerned about identity and access control should be doing something else of course, yes -- but let's face it, there are passwords everywhere out there still, and lots of dimensions to their use past the "can I get into system XYZ using any of these passwords" mode of thought. This especially holds true in B2C relationships where providing other, better credentials is just not on.
@TD -
I think you might want to re-read my post. I'm not advocating "weak, guessable, trivially bruted password[s]". Instead, I'm simply suggesting that there is really only one attack scenario where we even care about the password "strength" - and that comes with guessability, which seems like it could be addressed simply through a relatively long-lengthed password (12+ chars).
As for the "identity and AAA type specialist" having a different perspective - I don't see your argument. Again, I specifically speak to addressing the guessability of a password, so I don't understand the disconnect.
The bottom line here is that the primary controls used to protect authentication mechanisms have very little to do with password strength. The only area where we care about complexity is in reducing the guessability of a password, which can be tackled in myriad other ways that don't require things like special characters. *shrug*
-ben
You guys are forgetting the most important aspect of password 'strength'... the more complex you make a password, the more likely it will be written down.
There are many scientific studies showing incidence of writing down passwords hovers between 10% to 55%, and the single largest factor is password complexity. By forcing 12-character passwords in a user population of 10,000 with 30-day expiry, you're close to 66,000 Yellow Sticky Attacks a year, probably compared with 1-2 brute force attacks.
It's a balancing act. In primary research using Bayesian stats and expert systems I did in 2005, I showed that #if you have LANMAN hash, and most of you DO#, the strongest password is 6-character alpha, because it minimizes the Yellow Sticky attack.
Also, brute force will crush your passwords, no matter how "strong" you make them. If an attacker gain access to your LANMAN hash, it's game over, regardless of your complexity rules.
Just sayin'.
-ddh
@Dan -
Actually, writing down passwords should go away with what I suggest. If you remove complexity requirements and allow people to use a really long word, or 2 words, then it's far more likely that they'll remember the password, and far less likely that it'll be written down. Don't think of 12+ characters as a random string, think of it as "ThisIsMyPassword" (literally).
On brute force, fully agree, which is why I say that using brute force as a reason for big, nasty, complex password is folly. If your password database is compromised, or if you allow unlimited grinding against an authentication interface, then you have much bigger issues than password "strength."
I don't suppose your research is available online? :)
Thanks for the great comments!
-ben
I think there's something more to this here, and that's convenience. You're right -- if someone is targetting ME specifically, and has a copy of a hashed password, eventually they will crack it. But in reality, the economics of evil factor in. If you're harvesting accounts to sell, you want to crack them quickly. An attacker is likely to have thousands to hundreds of thousands of accounts to compromise, and can sell them for at most a buck each. As a result, they just want to crack the quick ones so they can turn them around for sale.
IMO, password complexity matters here. Additionally, as a user, you can't rely on your provider of service to "do the right thing" when it comes to locking out IP's that fail attempts N times in M minutes. The provider has a responsibility to do so, but the consumer has the responsibility to set a password other than "snow" or "password" or "pauliscool" just in case the provider doesn't do the right thing.
Let's put it another way -- would you go change all of your passwords to "ben123" today and be comfortable with that?
@Paul -
A couple things... first, I think your estimates on brute-forcing are way too high. Combining rainbow tables and cheap cloud computing resources, easily any password 12 characters or less can be cracked quickly and cheaply. Thus, if the password hash is compromised, the probability that it will be cracked is very high. Complexity ends up being irrelevant.
If you take this as a given, then really the only concern you're seeking to address through password strength rules is how easily guessed it might be. As such, I'd say that "pauliscool" is an ok password at 10 chars, and "paulisverycool" is even better at 14 chars.
Now, as for changing all my passwords to the same single password... I wouldn't do that, because as a security person I look at that and realize that each site will have its own level of competence in protecting those password databases. If you always use the same password, and you've used it in dozens, if not hundreds, of different places... well, you're just asking for trouble. However, note that, again, none of this has anything to do with password complexity. In the grand scheme of things, "ben123" is not necessarily all that bad a password, though I personally think it's far too short. Beyond that, however, just how guessable is "ben123" in the grand scheme of things? Would someone who knows me well somehow leap to that option before an account become locked? It seems unlikely...
-ben
Yes, if you're using a pure MD5 or SHA1 hash of a password string with no salt, rainbow tables and cloud services making cracking easier. But salting the hash makes the effectiveness of rainbow tables plummet. I have never created a password scheme that didn't first involve creating a random salt to ensure randomness of the hash.
Also, don't assume your provider does the right thing in terms of locking out an account. See how many failed authentication attempts it takes to lock your facebook account, for example...
My comment here is that you're suggesting that users can simplify their passwords if and only if their providers are doing the right things. They aren't, as evidenced by unclear and varying rules on how passwords are hashed, stored, complexity requirements, aging requirements, and lockout times (if any). The user must do whatever they can to protect the integrity of their account, and for now, I think that means choosing a complex password.
@Paul -
One clarification: my post was more geared toward enterprises than consumers, though I think the principles still hold.
In terms of brute-forcing, I don't know about anyone else, but if I login to Facebook from a different location they're hitting me with CAPTCHAs and "name that picture" a lot. I think you underestimate what they may be doing to protect against brute-forcing attempts.
Is it safe to assume that providers are doing the right thing all the time? No, of course not. However, foisting the responsibility onto the end-user is just plain stupid. The service provider has culpability and responsibility. Time to own up, or get ready to get fined and/or sued.
As for salting hashes, yes, sure, and how many OS installs are having the salt values changed? Very few, if any. Also, consider how and where that salt value is being stored. If /etc/passwd can get dumped, then why can't the salt value?
Last comment, and a bit of vindication for me: research confirms that password complexity is pretty much pointless and that we essentially need really long passwords. See:
"Short passwords 'hopelessly inadequate', say boffins"
http://www.theregister.co.uk/2010/08/16/password_security_analysis/
Thanks for the great discussion!
-ben
@Paul -
One last comment - I think you're missing the point of my post. I'm simply saying that all the complexity rules are pointless as all that we need are long passwords (>12 chars). If people want to chain words together to make a long password, then great! However, there is absolutely no benefit to making people choose "complex" passwords that require uppercase, lowercase, numbers, and special characters. If they want to use those things, then fine, but it should be because it makes for an easily remembered password/passphrase, not because of some contrived complexity requirement based on 1990s threat profiles.
cheers,
-ben
@Ben,
Also a final comment -- the principle I read in the post was that rainbow tables made complex passwords pointless if the password file was compromised. Rainbow tables work by precomputing password values and storing their hashed sums. Adding a random salt changes those values and makes rainbow tables useless. Additionally, salts are random, and not a static value.
For a rainbow table to work against salted hashes, they must precompute the hash for every possible value for every possible salt.
Given this, my comment is that if enterprises want to protect against rainbow table attacks, they should generate random salts for their passwords. UNIX has been doing this since passwords started getting shadow'ed, or earlier. For those interested, here are the relevant entries from my /etc/shadow file:
salty:$1$ohuhKM8Y$36yPz7MwNGcX2/qJiCCFQ1
This tells me that user salty has a stored password of $1$ohuhKM8Y$36yPz7MwNGcX2/qJiCCFQ1. The $ signs are seperators, with the $1 showing that it's an MD5 password, the ohuhKM8Y is the random salt, and the 36yPz7MwNGcX2/qJiCCFQ1 is the actual password hash.
This is a complex, salted password that I have provided the hash to. I challenge anyone to break it and post the password back, along with how long it took to crack. No rainbow table will have this salted hash stored, I guarantee it. So now, you're down to a dictionary attack, which won't work, because it's a complex password.
@Paul -
Yes, salting protects against rainbow table attacks. However, once again, this doesn't change anything about the conclusion that complexity really serves no purpose. When you factor in cloud-based password cracking, it only highlights further the importance of protecting the password database from compromise and being able to detect such a compromise.
-ben
More mainstream coverage of this topic:
NYT: "A Strong Password Isn’t the Strongest Security"
http://www.nytimes.com/2010/09/05/business/05digi.html?_r=1
XKCD provides a great, simple analysis that further reinforces my assertion here:
http://xkcd.com/936/