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,000ish 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
Here
a 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 per month.
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
