How to reason about password strength

This is an issue I see come up a lot, it's discussed on Security Stack Exchange all the time. It came up on the Sage-AU mailing lists recently. But every time I see this discussion come up there are misunderstandings, mistakes or people talking at cross purposes so I wanted to write up a set of principles or assumptions that we can use when discussing passwords that will hopefully make it easier to have a conversation about password strength.

These are some thoughts on how I think strength should be measured, none of them are set in stone and I could be persuaded to change my views on any of these points by reason and logical argument.

Assume the algorithm to generate the password is known.

This is basically Kerckhoffs's principle "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge." only applied to passwords.

I often see people saying things like "If I repeat my password twice, will it increase the strength?" or "If I add a non-ascii character..." and "what if I sha1 my weak password then use the output as a password". The response usually comes back along the lines of "Well, maybe, kinda, yeah but not really" with people saying "Now crackers know you do that, they will just adjust their method".

The problem is that people get caught in the trap of thinking too much about what the attackers currently doing. That ends up in an infinite cat and mouse game that no one can win. Crackers are using dictionaries so people add a number to the end of the word. Then crackers start adding numbers to the end of their dictionaries so we add special character and crackers add special characters too. Rinse and repeat.

I've seen people say things like "Now crackers will generate four random words when they attack so the xkcd system is broken" but they are missing the point. The comic assumes (in both cases) that crackers know exactly how the password was generated. If you have a list (a public list) of 2048 common, easy to type, lowercase words, and pick 4 at random (truly random, use a computer) that's 2048^4 options or 44-bits of entropy. You can give that advice to anyone, everyone in the world could use that method, it could be the only method of generating passwords, and the only one crackers target, and it would still give 44-bits of entropy every time.

It makes it much easier to calculate and compare methods of generating passwords if we only look at the entropy.

Assume the whole password needs to be guessed at once.

In general if password are stored well using something like PBKDF2 (or even if they are not stored well, using something like md5) you need to guess the whole password at once. For example if I use a password like "correct battery horse staple" if the passwords are hashed, a cracker can't work out that the first word is "correct" and then start working on the second word.

There are some situations where this assumption dose not hold. For example when the Adobe database was leaked, the passwords were encrypted with triple-DES ECB in 8 byte blocks. So passwords could be "cracked" 8 bytes at a time.

If you are talking about a situation where an attacker can break passwords a bit at a time you should explicitly say otherwise it should be assumed that the whole password needs to be guessed at once.

I think many people already make this assumption which may have been the reason why there was so much debate around the Telepathwords

Measure algorithm strength in bits.

Often people people discuss the strength of their algorithm using a calculation based on how it works. For example if someone is talking about a key space of 8 lower case letters they might say 26^8. Someone else might be talking four random words from a list of 2000 common words so they might say 2000^4 or 1:16000000000000 if they want to make it seem larger. While another might be using scientific notation and to describe a 13-character base64 password 64^13 as 3.02231e+23. I use dd if=/dev/random count=18 bs=1 2>/dev/null | base64 for passwords and I call it 144-bits because to me, I could output it to base32 or hex or some other arbitrary encoding, so it could be 64^24 or 16^36 depending on how I output it.

• 16^36
• 64^24
• 1:22300745198530623141535718272648361505980416
• 2.2300745e+43
• 144-bits

are all valid ways of talking about password strength but it's a bit like talking about the temperature in celsius, fahrenheit and kelvin. You can convert between them but it's hard to eyeball them and instantly see which is bigger.

So why bits? I could be persuaded to change my mind on all of these points, but this one more so. I do think it's helpful to use a consistent system to measure strength, but don't feel that strongly about bits. There some points in favor of bits over other systems but really a lot of it comes down to "I like bit, it feels intuitively right to me". Some points in favor of bits are:

• There is some president for it, cryptographic systems traditionally measure key space in bits, systems like KeePass show a password quality meter in bits.

• It makes it easy to add up entropy form different sources, for example in the xkcd comic the first letter 'T' it's got one bit for common caps. That's pretty easy to follow it could be a 't' or 'T' so it's one bit. Or where there is punctuation at the end it's got 4 bits, that could be one of 16 common punctuation character, so we add 4 bits. Work out all the places there are entropy and add them together.

• It keeps the numbers low, generally < 300 which is nicer than working with unwieldy numbers with lots of zeros or decimal places.

Don't measure the strength of an individual password measure the algorithm.

When I generate a password I use dd if=/dev/random count=18 bs=1 2>/dev/null | base64 but this has exactly the same odds of producing AAAAAAAAAAAAAAAAAAAAAAAA as it dose producing k7pwVtt3XzJlVmijr09lrTbO someone could use their dog's name as a password, but the dog could be some 30 character Inuit word that's not in any dictionary.

Put simply one password is simply not a large enough sample size. Instead you need to look at what is the "key space" or how large is the pool of password that this one came from.

Security of a Password Vs Strength of a Password.

I'm going to try to define some terms here, I'm going to say the security of a password is how well it dose it's job (preventing unauthorized access to something) and that the strenght of a password is how hard it is to guess.

A practical example of this is with storage of passwords. It's an important issue and deserves a lot of attention as it can affect the security of a password but not the strength. There are two places a password needs to be "stored" (and I use that term loosely because I can't think of a better word than "stored"), the user and the service both need to store the password. How they are stored is important, depending on how they are going to be stored it might change how they should be generated, and how strong the need to be.

A password is likely to take ~900 CPU days to crack on modern hardware might be good enough but to encrypt a document which is embargoed for 7 days but might not be good enough for the Snowden documents.

The User The user needs a to "store" their password somewhere, this could be in their head, in a password safe like KeePass or Lastpass, or on a post-it note under their keyboard.

This will change how you want to generate your passwords I'm a huge believer in AviD's Rule of Usability "Security at the expense of usability comes at the expense of security." An xkcd style one is going to be easier to remember while a base64 password will be shorter and easy to store in KeePass.

While it is possible to not know any of your passwords (you can store them all in a password safe and use a YubiKey to open the safe) in most real world, practical situation your going to want at lease a few passwords that you can remember.

As above if users write their password down on a post-it, it affects their security but doesn't fundamentally change the strength in terms of bits of entropy.

The Service People could write (and probably have written) entire books on password storage on the server side so I'm not going to dig into that here, although for most situations it usually boils down to "stick to the standards, use something like PBKDF2."

How the service stores the password will also affect how you generate passwords, maybe it's a service that's limited to 16 characters (looking at you Microsoft) so you want to jam as much entropy into those 16 characters as you can.

Again if a service stores passwords in plain text, it affects security but doesn't fundamentally change the strength in terms of bits of entropy.