The ideal password - proven with maths
Tags: security, math, computerscience
Published: 2023-09-10 12:50:24

I've recently moved all my passwords from lastpass to Bitwarden (other password managers are available), which is a good app as you can sync across multiple devices without upgrading to premium (though their premium features are worthwhile too - no, I'm not sponsored by them…). At the same time I've updated all my logins that relied on duplicate passwords, where I've been lazy and put in a standard, easy-to-remember thing.

(Side tip: has your account ever been hacked? check [haveibeenpwned.com](https://haveibeenpwned.com/) to find out. Yes, I have been pwned :( )

Another philosophy which has fallen by the wayside is the idea of frequently changing passwords. This seems like a good idea in theory but in practice means that people often write their passwords down because they can't remember them all, which is also a bad idea for what's probably obvious reasons. Adding 2-factor/multifactor authentication where available is of course also worthwhile.

A difficult-to-hack password is one of a certain minimum length, and/or uses a large character set - both of these make brute forcing harder. But a good password (for humans) is also one that's easy to remember. This can be visualised thus (behold my incredible MSPaint skills):


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/shkp53ytt4qlcphhuzvq.png)

Password managers are great as they can randomly generate passwords for you - this way they only need to satisfy the first criteria. Changing them now and then, as necessary might still be worthwhile. But of course, you still need a login to the password manager itself. This is even more critical, as if this gets hacked, someone has _all_ your logins! (MFA absolutely essential here!)

For this password, I recommend using a website (such as [this](https://randomwordgenerator.com/)) to generate something that is both easy to remember and difficult to brute-force, purely based on the length. Set it to generate four random words and then string them together in any way you like. You can write this down for a short while until it's locked in your brain, but destroy it as soon as it's memorised. Dictionary words can sometimes be a bad idea for passwords, but as long as there's enough of them (and they're not easy to guess by anyone who knows enough about you), it's secure enough, thanks to the following maths...

The English language contains about a million words, but let's reduce it to the [170,000 in common use](https://englishlive.ef.com/blog/language-lab/many-words-english-language/), just to keep our assumptions low. Brute-forcing a single dictionary word - let's say all in lower caps to keep it straightforward - would therefore take my computer (just an ordinary laptop, not a particularly fancy rig) - 30 seconds in the worst case scenario, using a not-particularly-good algorithm:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yob4a1eerkjmuacg0fp3.png)

Ah, but what if we randomised uppercase and lowercase characters? Sure, that makes it harder. Now we need to check each word, and randomly assign an uppercase or lowercase character to each letter of each word, for every attempt. It makes sense to capitalise the first letter first (or early on at least) as that's how most people do it, so you're more likely to get the correct answer faster. Then you need to work through the word in a comprehensive fashion to obtain every possible permutation. Since each character here has two states (uppercase or lowercase) this effectively makes it a binary problem, which is something computer scientists are very familiar with. You can create a binary string of the same length of the word, and use that to generate the selection of uppercase/lowercase alternatives, incrementing the binary by 1 each attempt. So for an eight-letter word (let's say "computer"), the binary 0000 0000 is initially produced, putting all characters lowercase. It then gets increased by 1, producing 0000 0001 ("Computer"). 0000 0010 produces "cOmputer". Then 0000 0011 => "COmputer". And so on. For an eight letter word, this means 2^8, or 256 attempts. The 'average' word in the English language is  [4.7 letters](https://wolfgarbe.medium.com/the-average-word-length-in-english-language-is-4-7-35750344870f) - let's round that to 5 - so 2^5 = 64 attempts. 64 × 170 000 = 10 800 000 attempts to brute force. Let's give that a try:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6aoqcegjsmrjt9p74q3h.png)

My PC ran this in 52ms. That's a single run on a single word, so running that 170,000 times might take just over two and a half hours (no, I didn't try this!). That's not too long for an even slightly determined attacker. Again, that's only in the worst case scenario (from the hacker's perspective!) that the required result is the very last combination checked. And we _can_ increase the complexity of the problem by introducing numbers and special characters, but we can _also _ increase the efficiency of the brute force algorithm. My quick-and-dirty approach to this involves triple-nested loops, giving a complexity of O(n^3), which is pretty bad. I might have a go at creating a better one at some point, just for the attempt. (You could also, for example, sort it by words most commonly used in passwords, and include words you think the person is most likely to use based on any personal information you can glean… hackers are sneaky.)

You might notice one thing; that the longer the word is, the harder it is (more work required) to hack. If you take the original method - a single lowercase word - and make it longer - with _multiple_ words - you're exploring the set of all such possible word combinations, instead of the set of all possible substitutions for each letter of a single word. This is an _enormous_ set. For two words, this produces 170,000 ^ 2 possibilities (assuming duplicates), which is 28.9 billion. For 3 words: 170,000 ^ 3 = 4,913,000,000,000,000; that's 4.9 quadrillion, or 4.9 × 10^15 in scientific notation. For _4_ words, the number is (rounding) 8.4 × 10^20. 

That’s a Very Big Number indeed. The number of grains of sand on _all_ the beaches and deserts on Earth is about [1.7 × 10^18](https://eu.oklahoman.com/story/lifestyle/2019/02/05/more-stars-than-grains-of-sand-on-earth-you-bet/60474645007/), and there are conservatively about 1 * 10^22 stars in the observable universe, so it's somewhere between those two Very Big Numbers. My attempt above took 30 seconds to try 170,000 words, so a dictionary attack that could create four-word combinations at a similar rate (and this is an apples-to-oranges comparison, granted, but it gives you an idea) would take 4.7 billion years to run all the possibilities. (Check my maths - I'm not an expert: 170 000 / 30 = 5,667; (8.4 × 10^20) / 5667 = 1.5 × 10^17 seconds; divide that by 3.154 × 10^7 to get 4.7Bn.)

It's easy to remember, hard to guess, and good luck brute forcing it.