Formula to calculate password cracking time in years, taking into account Moore's law and known adversary guessing power

Question

We know that the biggest human rights violators in human history are capable of one trillion password guesses per second as of approximately January 2013.

• Assume that the 1 trillion guesses per second is not a dictionary attack, but a brute force search of all possible permutations of the available characters in the password.

• Assume this rate of password guessing is the same speed regardless of their computing equipment. Assume they have special equipment e.g. GPUs/ASICs capable of performing the industry standard Password Based Key Derivation Function (PBKDF2-SHA2 with large number of iterations) for each password guess and they can still guess 1 trillion password combinations per second. Therefore their actual hardware will not factor into the equation, just the 1 trillion guesses per second they can perform.

• Discard the assumption of weak passwords and assume the password is very strong and made up of uniformly and randomly selected characters available on a standard US keyboard layout including special characters (95 possible characters total).

• We also know from Moore's law that transistor count on an integrated circuit doubles every two years, which loosely translates to doubling of computing power every two years. So in January 2015 they will be able to guess 2 trillion passwords per second. In January 2017 they can guess 4 trillion per second and so on. Assume this trend will continue regardless of speculation that this law may come to an end and it needs to be factored into the formula.

• To successfully guess a password, it often only requires 2^n-1 attempts. That needs to be factored into the equation. Please also factor this into the formula.

What I would like is a reusable formula which takes into account the known adversary power of 1 trillion guesses per second as of January 2013 and its future power with regards to Moore's law. I would like to dynamically enter in the total number of password characters and the current date. The formula will return a calculation of how many years this password will be secure from brute force search from that current date.

Apologies if this is the incorrect StackExchange forum, but I think it is in the right place as I am after a correct mathematical formula which I can then turn into a software function. Feel free to move it if that is more appropriate.

Answer 1

Let $t_0$ be the current time in years from January 2013, and $n$ be the number of bits in the password. If $y$ is the number of attempts since the NSA started trying to hack your password, then we have the equation

$$\frac{dy}{dt}=10^{12}\cdot60\cdot60\cdot24\cdot365\cdot 2^{t/2}=:k\,2^{t/2}.$$

The big number $k$ is for converting the $10^{12}$ attacks-per-second figure into years, and the derivative is because this is measuring the accumulation of attacks done.

Now, we want to find the number of attacks that occur between now and some future time $t_0+t$, which we obtain by integrating this:

$$y(t_0+t)=\int_{t_0}^{t_0+t}k\,2^{x/2}\,dx=\left.\frac{2k}{\log 2}2^{x/2}\right|_{t_0}^{t_0+t}=\frac{2k}{\log 2}2^{t_0/2}(2^{t/2}-1).$$

Now, we are interested in finding when this number of attacks exceeds the maximum that our password can tolerate, which is roughly $2^n$ (I'm ignoring the $-1$ because the difference is negligible compared to other approximations of the model):

$$y(t_0+t)=2^n\implies2^{t/2}+1=\frac{2^n\log 2}{2k\,2^{t_0/2}}\implies t=2\log_2\left[\frac{2^n\log 2}{2k\,2^{t_0/2}}-1\right].$$

And there is your formula, given inputs $t_0$ and $n$, and the constant $k$. (Edit: I notice I have not factored in the information about keyboard layouts into this analysis, since the "$2^n-1$ attempts" part is already enough to answer the question. If the passwords are not bit strings but instead strings of characters from an alphabet of $95$ symbols, replace $2^n$ with ${95}^n$; nothing else is affected.)

Discussion: Looking at the form of the formula, we can get a feel for the implications of Moore's law in action. The denominator involves factors $k$ and $t_0$ that you can't do much about (we can't choose the era we live in), but $n$ is of course under our control, so it helps to isolate that part. Note that we can rewrite the equation as $t=2\log_2(2^{n+a}-1)$, where $a=\log_2\frac{\log 2}{2k\,2^{t_0/2}}$ is a constant; thus the overall speed of computing can be offset simply by adding a constant amount to your password length.

For large $n$, the $-1$ factor becomes negligible, and we get $t\sim 2\log_2(2^{n+a})=2(n+a)$. Thus the time to break the password goes up by about 2 years for every extra bit in the password. If we are working from a $95$-symbol alphabet, this changes to $t\sim 2\log_2(95^{n+a'})\approx13.1(n+a')$, so that each extra US keyboard character adds 13 years to the password strength.

Answer 2

While the mathematics of this problem are well covered by Mario Carneiro, the reality in the OP is rather distorted. Ignoring the problems with Moore's law as it is. The main issue you will run into very soon is the energy consumed.

To further simplify the problem we ignore the fact that energy costs money and just focus on the actual limits of how much energy we can produce. And then to make it easier on myself we crib Bruce Schneier's work from Applied Cryptography as reposted here so I don't have to do all the calculations myself.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than $kT$, where $T$ is the absolute temperature of the system and $k$ is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that $k =1.38 \cdot 10^{-16} \mathrm{erg}/{^\circ}\mathrm{Kelvin}$, and that the ambient temperature of the universe is $3.2{^\circ}\mathrm K$, an ideal computer running at $3.2{^\circ}\mathrm K$ would consume $4.4 \cdot 10^{-16}$ ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about $1.21 \cdot 10^{41}$ ergs. This is enough to power about $2.7 \cdot 10^{56}$ single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to $2^{192}$. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.

But that’s just one star, and a measly one at that. A typical supernova releases something like $10^{51}$ ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

Now to look at a more realistic example (and do at least a little work) let us look at the output of the world as given by wikipedia for 2008 World energy supply. That gives us a base supply of 143,851 terawatt hours which is $5.178636 × 10^{27}$ ergs. Lets round up and call it $10^{28}$ ergs. Take the bit setting energy and round it down to $10^{-16}$ ergs per bit. That gives us $10^{44}$ bit flips. That's about enough to run a 144 bit counter through its paces. Notice that we are using ALL of the worlds energy for a year and making super unrealistic assumptions (like being able to run a computer at the ambient temperature of the universe).

Altogether, already below 128 bits of entropy it's orders of magnitudes easier and cheaper to bribe or beat the key or password out of someone than to try and crack it. More over this assessment will not change in the near future unless some world changing physics happen.