Don’t Think About Password Complexity
As a non-technical consumer, you don’t need to be thinking about password complexity.
Really, forget everything you might have heard about complex passwords and how to make passwords.
As a consumer, there is only one thing you need to know about passwords: how to use a password manager.
Why? Because even the most technically aware human is never going to make and remember good passwords. A password manager removes the problem.
Decades of well-meaning experts teaching consumers tricks to make secure passwords was trying to solve the wrong problem, in part because the password managers of 20 years or 10 years ago were not user friendly.
Today, many password managers, including F-Secure’s, are extremely user friendly.
As a user, you have all your passwords available on whatever device you are using, ready to auto-fill into any login form in one click.
You can create a new strong unique password for every service in one click, without ever having to remember anything.
And you have peace of mind knowing your passwords are backed up to multiple devices.
Using a password manager is far easier and far more secure than anything you are likely to be doing with your passwords today.
Really you shouldn’t be thinking about password complexity, you should just use a password manager and forget about it.
What is Complexity?
That is, you shouldn’t be thinking about password complexity, unless you find the subject interesting – so for the curious and the brave, let’s dive into some information theory!
All science requires precise definitions, so what do we mean when we talk about password complexity?
Complexity is a technical concept from an area of mathematics called information theory, which is a science invented in 1948 by Claude Shannon and still very important today in a wide range of subjects from genetics to thermal physics, from linguistics to software development.
Essentially complexity is a measure of how random something is. In information theory, the idea of “random” has a very precise meaning, which is slightly different to our human intuition or how the word is used in everyday language. In fact, the meaning is so precise that normally mathematicians don’t talk about how “random” something is, they talk about the amount of “information entropy” it has.
We can think about information entropy as the idea of how compressible the information is.
Have you ever watched a film and after thought the last 30 minutes didn’t add anything? Have you ever read one of those mass-produced self-help or management books and afterwards thought they could have written the whole book in just 1 page – everything else was repetition? Have you played a game and got bored after a while because it is always the same adventures and monsters repeating? Have you ever thought “all these songs sound the same”?
Those are all examples of things we can think of as being compressible – you could get the same information in a shorter time or in a smaller product. In information theory terms, the information entropy of those products is low.
Random in this mathematical world just means that the information entropy is as high as possible. There is no possible way to make the film, book, or game shorter while keeping all the information.
Why is complexity important for passwords?
This idea of complexity, or information entropy, is important for passwords because bad people are trying to hack all of our accounts. In general, they are doing this en masse, using automated software.
How does that work? The baddies have software to do two kinds of things.
First is software to try lots of different passwords on a login form, looking for one that works. Think of it like a burglar who comes to your front door and tries millions and millions of different keys in your lock until a few seconds later one of them opens your door. Software is fast.
This “try different keys until one works” approach is, for example, one of the key components of Mirai, a malware for IoT devices and home routers that managed to take down the internet for the whole country of Liberia in 2016.
Second is software to try lots of different passwords to see if they encrypt (hash) to the same encrypted (hashed) password they see in a passwords database they have stolen as part of another hacking operation. Think of it like a bank heist gang getting back home and trying hundreds of billions of different combinations on the millions of safes they just stole, until a few hours later well over half of those millions of safes are open. Again, software is fast!
This is one of the key steps behind the identity theft and account takeover cases you hear about in the news.
Both types of software used by the baddies are forms of what we call “brute force” attacks, although the first example is also normally called “credential stuffing”.
Like always, reality is more complicated and cleverer than the “brute force” name suggests. In their purest form, brute force attacks are like what we do when we forget the code to our suitcase padlock – we try every number: 0000, 0001, 0002, 0003, 0004, until it opens. Worst case we will have to do ten thousand attempts and it will take a few hours – on average we will have to do five thousand attempts which still takes a couple of hours.
In reality, we will try likely numbers first (for example 1234, family members’ birthdays, etc), and then plausible variations (for example 1 up or 1 down) on those likely codes, before we really sit down to do a few hours of mindless 1-by-1 attempts.
Password brute forcing software does the same thing. They contains dictionaries that are tried first. Dictionaries can be what you or I think of as dictionaries – e.g. all the most common words in the English, or Spanish, or Mandarin Chinese, or Hindi, or Arabic, or Russian languages (we always start with the most used/likely languages).
Dictionaries can also be specialised for the task – for example a dictionary of the top 10 million passwords seen in all previous stolen password databases, or a dictionary of the most popular first names worldwide, business names, and football team names (these are common things for people to use in their passwords).
Similarly for variations – password brute forcing software knows to also try replacing letter “o” with number “0” and all the similar tricks we have been taught. And the software can try all the different versions at breakneck speed. The software can even combine 2 or 3 dictionary words together along with replace tricks, and it has clever rules to decide which combinations to try first, based on what we know about real world passwords most users make.
People are not random
In other words, all this music sounds the same! Most people’s passwords are very very predictable. Being predictable means the baddies can take short cuts, they do not have to try every possible case to find yours. In information theory terms, most passwords have low information entropy – they are not (even close to being) random.
There’s a good reason for this – humans are incredibly bad at making random patterns. In fact, we are so bad at it that mathematicians can easily win money off us by betting on what next “random” head or tail we will say. Most people will remove 77% of possible information entropy before they even start because our intuition thinks something like “head head head head” can’t be random.
We are predictable. Predictable means that computers can take shortcuts – they do not need to try every possible password to find yours.
Back in mathematical language, we talk about the domain of possible passwords. The domain is basically a list of all possible choices – those ten thousand codes like 0000 for your suitcase padlock. By being predictable, we are reducing information entropy, which means that we can compress the domain of possible passwords to a much smaller domain.
The smaller the domain to check, the faster software can find our password. This is why we want the domain to be as big as possible.
And again, this is why we all need to use password managers – computers know how to make the highest possible entropy (ie random) and long passwords, people do not. Even if we could make passwords like this, we couldn’t remember them. And even if we could remember them all, one click autofill on every device is much easier!
How do we calculate the domain size?
There are 2 factors that impact the size of the password domain that baddies need to search to break into our accounts.
As discussed so far, the first is the randomness (or information entropy) in how we chose passwords in that domain. Obviously we want to choose with maximum randomness, so that there is no possible way to take a shortcut and search only part of the total domain.
In other words, we want the person who stole our suitcase to need to try all ten thousand combinations to the padlock, and not be able to open it by guessing only the 10 most common codes.
Aside: We also don’t want them to be able to open the padlock using simple lockpicking – which in this analogy is like the online service saved your passwords with a very bad quality or no encryption (hashing), something that does unfortunately happen. This is another reason we want each service to have its own unique password – so the baddies can’t then reuse their lockpick to open all our other suitcases.
The second factor is how many possible passwords are there in the domain. For example, your 4 digit padlock has ten thousand possible combinations. If your padlock had only one wheel, there would be only 10 possible combinations: 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0. If that one wheel had English letters instead of numbers, there would be 26 possible combinations.
Calculating the domain size is easy.
We take the number of possible choices for one “wheel” (let’s call it C for “choices”) – for example a single number has 10 choices, a single English letter has 26 choices (or 52 if we include both lower and upper case letters), a single Japanese character has approximately 2000 choices (at least for the ones you need to know for basic literacy).
And we take the number of “wheels” (let’s call it W for “wheels”) – for example most number combination padlocks have 4 wheels. Your 8 letter password has 8 “wheels”.
The domain size is the first number multiplied by itself the second number of times. Or in other words the first number to the power of the second number. In mathematics, we would write the equation for D (for “domain size”) like this in algebra:
D = CW
When you go to one of those (very misleading) “how strong is my password” websites, this is the calculation they are making. They are then dividing the number they get by an approximation for how many passwords brute forcing software can try per second.
Let’s do a calculation
Let’s imagine you have made a really random 8 character password. You have used numbers, upper and lower case English letters, and the 10 most common special characters. That means:
C = 10 + 26 + 26 + 10 = 72
W = 8
D = CW = 722,204,136,308,736
722 trillion possible passwords. That’s a lot right? If we as humans were to try every possible password, and we could test 1 per second and never take a break, it would take almost 23 million years. You can use Wolfram Alpha to do huge calculations like this using normal language.
Unfortunately, computers are much much quicker than people for this kind of thing. How much quicker? TinkerSec did an experiment in February 2019 using a low-specification specialised computer – the kind of thing you can rent for a few dollars at your favourite cloud provider – and the latest version of an open-source password brute forcing software, Hashcat.
His computer tested every single 8 character password in about two and half hours. In other words, his computer was able to test more than 80 billion passwords per second.
Computers are really fast!
This means that even with a perfectly random 8 characters, with all those symbols and numbers, your password is more or less useless.
Those complexity rules don’t help
Remember all that advice we learnt over the last decades? To add numbers, upper case, lower case, special characters, star signs, pictures of kittens, etc to our passwords? Did they really help?
Let’s do the same calculations again with an 8 character password, and this time we will only use lower case English letters. It will be much worse right?
C = 26
W = 8
D = CW = 208,827,064,576
And if we used TinkerSec’s computer guessing at 80.2 billion tries per second? It would take a bit less than 3 seconds to try every possible password.
It’s faster, just not that much faster.
Let’s try 12 characters like this, which is the current absolute minimum password length security professionals recommend:
C = 26
W = 12
D = CW = 95,428,956,661,682,176
TinkerSec time = 13.7 days
Just by adding a few characters to our password, we have more total complexity than a shorter password with much more choices over what each character is. In other words, making the password longer matters MUCH more than adding more possibilities for each character.
2 weeks to find our password really isn’t enough – this is why we all should be using the maximum length allowed by our password managers.
If I do the same calculation with one of my normal 32 character passwords we get this:
C = 72
W = 32
D = CW = 272,044,459,736,735,201,869,892,920,105,124,744,453,565,613,497,784,693,948,416
TinkerSec time = 7.8 million trillion trillion times the age of the universe
It won’t take that long to find my passwords, because computers are getting faster every day, still this gives me a big margin of protection from Moore’s law! Even if next year’s computer is 1 million times faster than TinkerSec’s computer, he will still need to run it for 7.8 trillion trillion times the age of the universe.
I’m hoping nobody will be that patient.
Maths to compare total domain complexity
So how do we easily compare how complex two password domains are without doing these calculations? Algebra time!
C1 and C2 are the different number of choices available per character in the two passwords being compared.
W1 and W2 are the different lengths of the two passwords.
We want to know how long a password with less choices per character needs to be so that it is as strong as a shorter password with more choices per character. In other words, how did I know trying with 12 characters of English lower case letters would work in the example above?
In other (algebra) words we want to know what W2 we can use so that:
C2W2 ≥ C1W1
So let’s do algebra magic to get the equation in terms of the W2 we want. We do this by taking logs of both side. Taking logs is just one of those maths tricks – invented by inspired people like Napier, Leibniz, and their followers – that you need to know when you are playing with exponentials.
log (C2W2) ≥ log (C1W1)
Then we use the exponent identity of logarithms to simplify:
W2 log C2 ≥ W1 log C1
W2 ≥ (W1 log C1) / log C2
So let’s try the equation with our case in the previous section:
C1 = 72
C2 = 26
W1 = 8
W2 ≥ (8 log 72) / log 26
So the lower case English letters password needs to be more than 10.5 characters to be as strong as the 8 character password using upper, lower, number, and symbols.
That’s why the 12 character “weak” password was in fact stronger than the 8 character “strong” password.
What if I am a Mandarin Chinese speaker and I make my passwords using Chinese writing? Doesn’t that give me a big advantage in complexity?
First we have to assume that most online services allow you to enter a password using Chinese characters. Unfortunately, a huge part of the internet is still very anglo-centric, even down to the basic software level. If you try to use Chinese, Hindi, Russian, Arabic, or any other non-standard for English-speakers characters in a password, most services will fail in amusing ways. Still, I have to assume at least many of the services popular in mainland China will accept passwords with Chinese characters.
To be literate, Chinese people need to know between 3 thousand and 4 thousand characters, so let’s say we have 4000 choices on each wheel of our suitcase padlock.
How long do I make my lower case English password so it is stronger than my Chinese friend’s 12 character password? Here’s the same calculation:
W2 ≥ (12 log 4000) / log 26
So I need at least 31 characters. That’s a lot longer – still nothing like 4000 characters longer.
What if I don’t like letters and symbols and want to only use numbers? How long do I make my password to be a strong as a standard number, upper, lower, and symbols 20 character password? Same calculation:
W2 ≥ (20 log 72) / log 10
It’s not that the number of choices per character doesn’t matter – it does matter. It is just that exponentials grow very very quickly, so the number of characters matters a lot more.
In any case, leave this up to your password manager – they know what they are doing.
Diceware and Passphrases
Unfortunately, there are still a few places where you will still need to make and remember a password. I have 4:
- the password to open my password manager
- the password to unlock the disk encryption of my computer
- the password to log into the operating system of my computer
- the password to open my phone
What should we do for these? I am one of those people who has at times really memorised proper password manager generated passwords. I do not recommend doing that, unless it is a hobby for you.
The modern security industry recommendation is to create a passphrase, like in the famous XKCD comic strip from August 2011 that made “correct horse battery staple” one of those passwords that you really don’t want to use.
The idea is that you take 4 or 5 or 6 words in your native language, and put them together. Like this you get a very long password, which we call a “passphrase”. It also makes a password that is easy to remember because it is just words and because it is often quite an amusingly absurd combination. There is no need to do any special characters, upper and lower case, or numbers – just the words. Easy!
You can roll 5 ordinary 6-sided dice, or 1 die 5 times, and put the numbers together to make a 5 digit number like 43146. Looking that number up on the list, we have the word “munch”. You do that again as many times as words you want, and then you squish your words together.
This must mean passphrases are incredibly strong, right? After all they will be very long, maybe even longer than my 32 character passwords from my password manager.
Not exactly. Remember when we first looked at the meaning of complexity, and the idea that if there is a shorter way to write something, then it is only as complex as the shorter version?
Let’s take the canonical “correcthorsebatterystaple” passphrase. It has 25 lower case English characters, so that means it is working on a domain of size 26 to the power of 25, right?
C = 26
W = 25
D = CW = 236,773,830,007,967,588,876,795,164,938,469,376
TinkerSec time = 6.8 million times the age of the universe
Nice and strong.
Unfortunately, if we know this password is in fact a passphrase, then we can write it in a shorter way. Our passphrase is just 4 words, with each word having “my word list” number of choices. A passphrase is somehow very similar to writing a very short password using Chinese characters. This means we need to calculate the information entropy or complexity of our passphrase differently.
For example, the EFF list has 7776 words (5 6-sided dice gives 6 to the power of 5 choices = 7776). You can use a longer list – common dictionaries have 100,000 or more words. Still, let’s assume correcthorsebatterystaple was made using diceware on the EFF list. In that case, our padlock has 7776 choices and 4 wheels:
C = 7776
W = 4
D = CW = 3,656,158,440,062,976
TinkerSec time = almost 13 hours
That’s a huge shortcut!
Definitely not ideal. Still we can make this much stronger by adding some more words – if for example we make our password from 6 words out of the EFF list, then our passphrase is suddenly more than strong enough:
C = 7776
W = 6
D = CW = 221,073,919,720,733,357,899,776
TinkerSec time = 87,351 years
Similar if we had a good way to randomly select words (remember if the human is doing the selection, it will be very far from random) from a real dictionary of 100,000 words and chose 5 words, then we would also have something strong enough:
C = 100,000
W = 5
D = CW = 10,000,000,000,000,000,000,000,000
TinkerSec time = almost 4 million years
While both these are not as strong as using a password manager, it’s strong enough for the very few cases where we need a human-made and human-remembered password. And in all likelihood it will be stronger than any complex password that a human makes and tries to remember.
Just remember to use at least 5 words in your passphrase, and, of course!, for all other passwords, still just use your password manager.
I first thought of doing this article because I was wondering if I was somehow breaking operational security (OpSec) by telling people that most of my passwords are 32 characters long.
After all, by telling people my passwords are 32 characters, they know that they are not 20 or 31 or 10 characters long, so the baddies can skip checking all those passwords when doing a domain search to brute force any password of mine they might have found in a stolen database.
So should I really be worrying about this? The short answer is no.
Here’s the maths for why. What happens to the size of the search domain when we add another “wheel” to our padlock? It means we have W+1 wheels – 1 more than the W wheels we had before. Let’s try some algebra and see what insights we can get:
CW+1 = C * CW
We can split the C into 2 parts like this:
CW+1 = 1 * CW + (C-1) * CW
This means that if we have at least 2 choices per character (so that C-1 is at least 1), then:
CW+1 ≥ 2 * CW
And in fact, the more choices possible per character, the bigger the difference adding one more character makes.
Concretely for my exact case of 32 character passwords with usual upper, lower, numbers, and symbols, the domain of possible guesses the baddies need to make is 72 times the size of all possible 31 character or shorter passwords.
In other words, by telling everyone my passwords are 32 characters long, I am saving the baddies 1 in 72 guesses. Given the size of the total domain, this is not a problem. If the baddies knew my passwords are only 12 characters, it would be more of a problem.
Also I could be lying – maybe I always manually update my password manager to create a 35 character password. OpSec 101 is to lie to the internet about your individual security practices and private information. At least when you are not just shutting up – most of the time you should be just shutting up, as your lies will also not be random, just like the passwords you try to make yourself.
Hope you enjoyed that dive into information theory and password complexity. Now’s your chance to have fun imagining interesting questions about passwords and working out the answers with these equations.
Also, no matter how well you think you understand this, only use these equations for fun – your passwords should only ever come from your password manager!
Leave a comment