There's been lots of talk about secure passwords
recently. I was a bit bored and so decided to do a little math. The math relates to working out how long it would take the brute force a password while also taking into account Moore's Law. I first saw mention of this in a very early version of the 7-zip help file. It's no longer present in the new versions. Note this is just me musing, I'm not a cryptographer.
Let's simplify the math initially, so while Moore's Laws talks about transistor counts doubling every 18
months or so, we'll completely misrepresent it and claim that the number of passwords that the "technology of now" can brute force doubles every year. Next we'll also think of password lenghts in terms if bits so that we can can directly relate the increasing the length of the password by 1
bit to doubling the search space. For example in a lower-case alphanumeric password where each character comes from one of 36
possibilities, every additional character adds over five bits.
Ok, now onto the fun bit. So let's say that computers today can brute force about 1,000
passwords a year and that we have a password of 10
bits which gives a search space of also about 1,000
. Now lets say this is a rather important password and I want to ensure what it protects stays safe for 15
years. One thought would be to add 4
more bits which would increase the search space by 16
. But, the problem is over these 15
years the computers are improving. Indeed next year a computer would be able to brute force 2,000
ish passwords, the following year that could be 4,000
. Indeed by our simplified Moore's Law we see that in 4
years: 1,000 + 2,000 + 4,000 + 8,000 = 15,000
. So though we increased the search space by 16
, we really only added just over 4
years to the brute forcing effort, we've actually only seen a linear improvement.
This pattern is known as a geometric series, and to rob a Wikipedia graphic, there is a formula for calculating the sum
is the number of passwords that can be brute forced now and r
is the rate at which that increases.
So let's do a little test and ask how long would I need a password to be (in bits) today such that it'd stand up to 30
years brute forcing. We'll do the math in steps of months rather than years. To use somewhat real figures, I looked at CodingCrypto's page on Engineyard's Programming Contest
. One of the results they quote is that a Quad Core 2 @ 2.4Ghz could compute 47,603,960
SHA1 hashes/second, which becomes a rather mind boggling ~ 1.2339 x 10^14
Ok, so let's do the math
- If r over 18 months is 2, then r for one month is r = 2^(1/18) = 1.0393
- We want to survive 30 years brute forcing so n = 30*12. Therefore the geometric sum x = 2.6709e+007
- The value a we are taking to be 1.2339 x 10^14 passwords per month, giving the total, t = a*x = 3.2956e+021 over the next 30 years.
- So what size in bits would a password need to be to stand up to that? Well the length l = log(t)/log(2) = 71.4810, so at least 72 bits.
- Now what size lowercase alpha numeric password would we need? Well now we have l = log(t)/log(36) = 13.8263, or 14 characters.
All in all 14
lowercase alpha numeric characters isn't too long a password. But 30
years is a far cry from the thousands, if not millions, of years normally quoted for such password lenghts (and no, I don't have a citation to back up said quoted figures
Anyway, as I say, I'm just musing and maybe totally wrong. Also assuming Moore's Law to hold up over such timescales, or longer, is a bit fanciful