Home | Blog | Software | Reviews and Features | Forum | Help | Donate | About us
topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • December 03, 2016, 05:52:40 PM
  • Proudly celebrating 10 years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: Password Brute Forcing and Geometric Series  (Read 964 times)

Eóin

  • Charter Member
  • Joined in 2006
  • ***
  • Posts: 1,401
    • View Profile
    • Donate to Member
Password Brute Forcing and Geometric Series
« on: January 05, 2011, 08:01:03 AM »
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

47470196f9edbc3b7bb81e853a3487ff.png

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 :Thmbsup:
  • 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  :-[

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,029
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Password Brute Forcing and Geometric Series
« Reply #1 on: January 05, 2011, 09:58:44 AM »
Moore's law is probably going to fail a lot before 30 years from now, and we definitely don't see an x-fold software speedup from an x-fold increase in transistor count... So the mathy stuff is going to be pretty far off. Still, it's an interesting thought experiment, and while we're likely to hit a cap on the CPU gHz there's other factors as well - massive parallelism, massive distribution, GPGPU, algorithm improvements...
- carpe noctem

Eóin

  • Charter Member
  • Joined in 2006
  • ***
  • Posts: 1,401
    • View Profile
    • Donate to Member
Re: Password Brute Forcing and Geometric Series
« Reply #2 on: January 05, 2011, 10:14:57 AM »
A though experiment is all it was ment to be :D