Thursday, August 24, 2006


Why are passwords weak?

When I talked about the scene in the movie "Mission: Impossible" where Tom Cruise broke into the CIA computer, I made a comment about how the fictional ultra-secure computer system was compromised by its use of password authentication:

Yes, it's as simple as that: this complex system, protected by an intricate high-tech system of biometrics and sensitive sensors, succumbed to the simplest, silliest, low-tech "I stole his password" attack.
But password authentication is a weak point in most computer systems for a number of reasons, some inherent in the use of passwords and some that come from the implementation of the authentication system. Today we'll look at what makes the use of passwords bad.

First, a quick review of what password authentication is and how it works: A password is what we call a shared secret — you and the computer you're authenticating to, which we'll refer to here for brevity as the server, both know the password for your user identity. To authenticate with the server, you tell it your user ID (which is not secret) and your password (which is). The server looks up your user ID in its authentication database, finds your password, and compares it with the one you sent. If they match, you're in.

When we consider authentication systems, we put passwords in the "what you know" category. You can be authenticated based on what you know, what you have (such as a "smart card"), what you are (fingerprints, eye scans), or some combination of these.

Let's start with a list of points, and then talk about them in more detail. Password authentication is weak by various combinations of the following (and this is not an exhaustive list):

  • People don't choose good passwords.
  • If they're made to use good passwords, they write them down.
  • Even good passwords don't have enough unpredictability.
  • The password authentication systems themselves expose passwords to attack.

Many years ago, your login password was stored in plaintext on the server. That's not generally done today; they're now stored in encrypted form, so that if someone should get access to the authentication database the passwords wouldn't be trivially accessible. Anyway, back when they were in plaintext, we did occasional password audits, where we'd look at the passwords only (without the user IDs), to see whether the passwords were likely to be good protection. On that computer system, when a user entered an ID to log in, the system responded, "Enter password:", and the user would type the password. Do you have a guess about what the single more commonly used password was, by far? Yes, indeed: "password". There were also a few other very popular ones that were taken from other words that appeared on the computer screen during the login process. Others were based on the month that the password was last changed, the name of the company, and other easily guessed things.

Another factor in bad passwords is the use of "default passwords" when software is installed. When you buy a certain wireless router, for instance, it comes configured with an SSID of "default" and an adminitrator password of "admin". If you don't change that, anyone can reconfigure your router. When you install Windows, it makes you select an administrator password yourself; there is no default. That's how it should be.

Another thing we saw in the password audits is that people often use things realted to themselves to create passwords — this is what's often depicted in movies. Passwords like "99chevy", or the name of one's spouse or child are vulnerable to directed attacks against you, specifically. Similarly, many people use patterns. If your password's always the name of a sports team, once that pattern is discovered it's not so hard to guess your next password when you change it.

To get around these problems, some computer systems select a password for you, and they tell you what it is. The trouble with that is that you're likely to write it down because you have trouble remembering what was assigned. People have been known to write their ATM PINs directly on the ATM cards. Not a good idea.

OK, let's assume you pick a "good password", and you don't write it down. How good is it? Here, we often use the term "bits of entropy", which basically measures the degree of unpredictability in the password. Consider this: The computers we use represent each character with 8 bits, allowing each character 256 (28) different values. But in practice, most passwords comprise a sequence of lower-case letters and digits, which means that each character really only has 36 possible values (62 if you add upper-case letters too). And often, password length is limited to eight characters — sometimes fewer. These are both artifacts of history, when computer systems had less memory and poorer input mechanisms. With these limitations, an eight-character password only has 368 possible values. That's less than three trillion, which is not a huge number by current computing standards. That's about 40 bits of entropy at best (down from the theoretical 64 (8 characters of 8 bits each)), and the desire to use passwords that are easily remembered will reduce it to between 20 and 30 bits — say, 20 million possibilities.

I mentioned ATM PINs above, and they're pathological cases of this: limited to four characters, digits only. That's 104, only 10,000 possible PINs! That may be fine to use at a physical ATM, but often the same PIN is protecting your account on the bank's web site, where it's much more prone to hacking. It can be reduced even further by noting that people are less likely to use leading zeroes, repeating digits, and other such patterns, thinking that they somehow make the PIN less secure, or "less random". So reduced, a 4-digit PIN only has 10 or 12 bits of entropy.

A better approach to passwords, which would fix all of these issues, would be to allow arbitrarily long "pass phrases", which could contain upper- and lower-case letters, digits, punctuation, and even characters from other languages and various symbols. It would be extremely hard to guess a pass phrase like this:

Cogito, ergo sum!® exclaimed René Descartes
...and it would be easy to remember, and not that hard to type, really.

So... you have a truly good pass phrase, and you're protected, yes? Well, no. Because you still send your password to the server for verification, so you're still exposing it. It can be intercepted en route by someone with the technology to snoop network traffic. It can also be snatched by a successful "phishing" attempt — by tricking you into sending it to the wrong server. And once it's snatched, it can be used to impersonate you on many other servers if you do as most of us must, and use the same password in many places.

Fixing this requires a basic change in how we do password authentication, but it's feasible, and technically simple. The way we do it is by making you (well, your computer, actually) use the password in a way that proves you have it, without your actually sending it anywhere. Here's one mechanism, which uses public-key encryption:

  1. There is no fundamental change in what you see as a user. You're presented with a window into which you enter your user ID and password.
  2. Instead of step 1 being done in a web form or some other interface offered by the server, it is done in a window presented by your computer (by your web browser itself, for instance).
  3. Your password is validated locally, by your computer system, and it provides access to the private key (also stored locally) of a private/public key pair.
  4. Your user ID, but not your password is sent to the server. The server looks up the public key of your key pair.
  5. The server sends back a challenge: some data that your computer must process and respond to. Typically, the challenge is encrypted with the server's private key and your public key.
  6. Your computer decrypts the challenge, re-encrypts it with your private key, and sends it back to the server. Note that this step can also confirm that the server is the one you think it should be.
  7. The server decrypts the challenge, using your public key, and compares it with what it had sent you. If they match, you're in.

What makes this mechanism work is that no one can create the encrypted version of the challenge to send back in the last step without having your private key, and at no point was any secret information transmitted that could later be used to impersonate you or to retrieve any other information about you. It's also immune to replay attacks because the server will only accept responses to that specific challenge right now; next time, the challenge will be different. You've been authenticated securely and safely, and no "phisher" can take advantage of this transaction to steal your identity.

For more discussion about web authentication issues, see Web Phishing Requirements, currently an Internet Draft by Sam Hartman of MIT.


The Ridger said...

I love the way the IT department at work sets things up so that we have to have these ultrastrong passwords - at least 10 characters; at least one each of upper case, lower case, numeral, special character; and cannot even contain a dictionary word. And then makes us use a different one for each frelling application - and change them all every couple of months. Of course people write them down...

Barry Leiba said...

Well, now, that brings up another peeve of mine: making you change your password at fairly frequent intervals. The theory is that if your password is exposed, changing it frequently limits the time during which the attacker can make use of it. There's also the minor issue that the change defeats iterative attacks.

But the reality is that if you have a "good password" to start with, making you change it hurts far more than it helps. There've been studies on this, which I can't cite just now, but making you change too often results in selection of poorer passwords, the use of patterns, and more dependence upon writing the password down somewhere.

A year or two ago, the Italians actually included a 90-day password change interval in a computer privacy law. Because my company uses the same authentication system worldwide, in order to comply with that law in Italy we had to make everyone, worldwide, change their passwords every 90 days now — we used to be able to go for 180. Sigh.