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

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