Luc Gommans/ blog

Napkin math for password cracking

Written on 2019-08-14

Note that "words" and "characters" are interchangeable. If you have a dictionary of 10 000 words and pick 5 words for a passphrase, or a set of 10 possible characters (e.g. 0 through 9) and pick 15 characters for a password, the calculations remain the same. Any FAQ entry for passphrases can be applied to passwords and vice versa.

You should be able to copy any calculations directly into this calculator (apt install apcalc).

How long will it take to crack my password?

Assuming no protection (so no bcrypt/scrypt/argon2): assume a trillion attempts per second for a motivated attacker in 2019. This setup would cost a few thousand to buy (source) or a few dollars per hour to rent at a VPS provider. If you are super paranoid, multiply by 2 for every 18 months that the password should remain secure for, though this is an overestimation (computing power won't increase that fast).

Computing the strength of a given password depends entirely on the way you generated it. If you looked at nearby objects (tree, bench, bicycle) and made a passphrase with that, all bets are off. If you took your dog's name and old phone number... you get the picture. I'm going to assume a completely random generation method, so you used a computer or a set of dice or deck of cards or something. The math to generate the number of possible values is:

possibilities ^ length

So if you used 5 digits, then there are 10 possible values in each position (zero through nine), thus 10^5 = ten thousand. How long does it take to crack that? Well, divide ten thousand by a trillion. That many seconds.

If you used 5 words from a dictionary, and the dictionary had one thousand words, then it is 1000^5 = one quadrillion possible passwords. How long does that take to crack? Divide a quadrillion by a trillion, so a thousand seconds.

How many bits of entropy is this?

Let's take ten digits (10^5) as example again. The answer is: log(10^5)/log(2) = 16.6 bits of entropy.

How many words do I need for a given dictionary size and strength?

What we need to solve is log(possibilities^length)/log(2)=bits so that we can calculate length. Since "b^y = x is the same as y = log_b(x)" and the base of the logarithm function that the calculator that I use uses is 10, the answer is log(10^(bits*log(2)))/log(possibilities) = length.

If you have a calculator with a different log function, for example if it uses e as base, then you would need to do log(e^(bits*log(2)))/log(possibilities) = length.

Let's say we want 128 bits of strength and have a dictionary of 10k words, then the answer is log(10^(128*log(2)))/log(10e3) = 9.6 words. Note that you need to round the answer up (9.1 "words" would also have turned into 10), otherwise you are underprotected.

How large should my dictionary be for a given passphrase length and strength?

What we need to solve is log(possibilities^length)/log(2)=bits so that we can calculate possibilities. Again assuming a base of 10 for our logarithm function, the answer is (10^(bits*log(2)))^(1/length) = possibilities.

Let's say we want 128 bits of strength and pick 8 words, then the answer is that we need (10^(128*log(2)))^(1/8) = 65 536 words in our dictionary.

How long does it take to crack with these password requirements?

TODO. See this for now: https://lgms.nl/p/pwd-combinations.html