Saturday, August 27, 2011

Building a better password

I've recently complained about the irritating nature of the password strength checkers that have been popping up everywhere, so I feel obliged at least to try to analyze the problem and offer solutions.  This is leaving aside the question of whether password authentication is a useful approach at all.

Fundamentally the real measure of password strength is how many passwords you'd expect to have to guess in order to get the right one.  A more formal version of this is the notion of bits of entropy.  If you had a list of all possible passwords in your scheme, I could identify any particular one so long as I could get answers to a series of yes/no questions, for example:  "Is it in the first half of the list or the last?",   "Is it in the first half of that half or the last?" and so forth.  The number of such questions I need is the number of bits of entropy.  Twenty questions means twenty bits, etc..

If I know that your password is either "0" or "1", you have exactly one bit of entropy.  If I know it's an uppercase letter, lowercase letter, digit, "$" or "%", there are 64 possibilities, so you have 6 bits of entropy.  If I know it's two such characters, you have 12 bits, and if it's eight such characters you have 48 bits, which is not too bad.  Someone trying to guess your password would have to guess about 140 trillion passwords, on average, before stumbling on yours.

[Don't assume that guessing a password requires typing it in to the same text box you have to use.  If someone steals the right data from your service provider, they can throw as much computing power as they've got at guessing the passwords.  Quite possibly they'll be happy enough just to try a few thousand weak passwords for each account, since that will crack depressingly many, but attacks like running through the OED with simple substitutions of letters for numbers are absolutely feasible as well.  Here's an article from 2012 about hardware that can guess 350 billion Windows passwords per second.  48 bits suddenly doesn't seem like so much.]

This is assuming that you picked eight characters at random.  If I knew instead that your password was either "F1%ldN0t3$" or "sasssafras" (maybe I'd watched you read your password off a piece of paper with only those two words on it but couldn't quite see which you were typing), then you have only a single bit of entropy, even though both passwords are not just eight but ten characters long and one has plenty of non-letters.

More realistically, if I knew you'd picked an uncommon English word and maybe changed some of the letters to numbers, you'd have somewhere around two dozen bits of entropy.  That's not trivial, but keeping in mind that each added bit doubles the number of passwords a cracker has to try, it's tens of millions of times weaker than the 48-bit scheme above.

The fundamental flaw of password strength checkers is that they can only look at the password you gave them.  They have no idea what other possible passwords you might have chosen.  The assumption is that if you're forced to jump through enough hoops you'll be forced to expand your parameters, but in fact it's possible to generate passwords in a secure manner using only letters, and or to generate them insecurely to satisfy any strength checker out there.  Which is why I half-grimace, half-laugh when I see the "password strength indicator" jump from "poor" to "great" as soon as I type a number.

Now, it's perfectly possible to generate completely random 8-character passwords.  The problem is that something like "qcrQf1x2" or "u%js%hPQ" is a pain to try to memorize, so most people will fall back to picking a "hard" word and maybe altering it a bit.  However, as xkcd points out, it's possible to do a lot better by using random short words.

For example, here's a kind of clunky way of producing a random, memorable password:

BIG HONKING DISCLAIMER: This is just for demo purposes.  The second site I mention uses http, not https, so in theory anyone could be looking in on your session.  Even with https, the sites might be logging all your traffic and recording the results you come up with.  I personally seriously doubt they would, and it's hard to imagine they would be able to connect the dots and figure out what you were using the generated password for, but if you really want to be on solid ground, get the source, look it over, run it locally and use something like /dev/urandom or D&D dice to generate the random input (15d10 will give you close to 50 bits ... not that I would have any idea at all what "15d10" means).  There are also smartphone apps that do more or less the same thing, I believe.

[I last checked that this (slightly updated) recipe worked on 4 Nov 2018]

With that out of the way:
  • Go to this site and copy the random string you see there (e.g., A6727933B0169E89).  To get more randomness, just reload the page.
  • Go to this site.
  • Type some short number and a space into the Challenge box and paste the random string from the first step in after it (e.g. 123 A6727933B0169E89)
  • Type anything at all into the Secret box (e.g., "secret").  This doesn't have to be hard to guess.  The real entropy is coming from the random string (alternatively, put any number you like, a space, and anything else into the "challenge" box and paste the random bytes into the "secret" box).
  • Press the Compute with SHA-1 button.  Again, the cryptographic details of how strong SHA-1 is don't matter here.  You're just converting a random number to short words.  A simple table lookup would do just as well.
In the Response box you will see six short words followed by some hexadecimal gibberish (in this case, LANE RICH ACE HIS TWIN BLUE (AA59 E401 0D7F 1CB3)).  Each of those words represents 11 bits of entropy (technically, slightly less, since we only started with 64 random bits, but who's counting?).  Take at least four, preferably five or all six.  If you don't like those words, just try again with fresh random bits, or change the number you used in the "challenge" box, or ask for more than one password in the "Compute __ passwords" box.  This will give you a fresh window with however many six-word passwords you asked for.

Feel free to take the short words you need from them in any order you like. Strictly speaking, this may reduce entropy since it will bias towards things that make sense, but that shouldn't be a huge problem if you, say, generate six passwords and take one word from each.  If you really want more entropy, go through the process twice and get more than six words.  The sky's the limit.

Then add a random punctuation character or whatever makes your site's password strength checker happy.  Voila!  Your password is now richtwinacelane5 or whatever.

If your site's password checker imposes an 8-character limit (and, incredibly enough, some do), cry.


earl said...

indonesiatooverseas said...

sometime it’s hard to me for remember what my password is if the password too long and complicate

David Hull said...

The important thing is to find something that's memorable to you, but not easy to guess. Different people's memories work differently. If the short random words approach doesn't work, a couple more are:

Shocking nonsense, which recommends picking random words that are memorable for being offensive in some way. Personally, I'd rather not have logging in be a shocking experience just for the sake of being memorable. Also, I'd rather not find out I'd just typed something obscene into a key logger or a chat window when I thought I was logging in.

Taking the first letters of a memorable phrase (shocking or otherwise). Including punctuation and capitalizing the first letter will probably also keep strength checkers happy. Such a password will be reasonably short (but not too short, at a guess you'd want at least a dozen characters), and if you picked something offensive and someone does get your password, you can always say it stood for something else. On the other hand, such passwords can be difficult to type, and you have to remember what punctuation to include (was that comma there or not ... or did I use a dash?).

In any case, one fundamental rule of passwords is to pick something that, as far as you can tell, has never been written down anywhere, ever. For the first-letters approach, that would also mean that the underlying sentence should be brand new.

Hope that helps.

earl said...

My password may never have been written down, but it's going to be, because I can't remember it. Of course, that means an attacker has to get into my house and find that piece of paper. Could happen, but I'm not lying awake...