How can we factor Moore's law into password cracking estimates?

Question

How would we go about factoring Moore's law into exceedingly long password cracking estimates?

Let's say we've got a 12 character password containing mixed-case alpha characters and numbers, i.e. a-z, A-Z and 0-9. The keyspace for such a password is roughly 3.2x10²¹.

Now, let's say I can currently compute hashes at a rate of 3.0x10⁹ (three billion) per second on a modern GPU. At that rate, using the same hardware, I could search the entire keyspace in 33,824 years.

However, if I can migrate across to newer hardware as it comes out, this figure is likely to be significantly less.

Assuming the following:

• Transistor counts double every 2 years.
• Hash computation speed is directly proportionate to transistor count.
• Hash computation speed is not bound by other constrains (e.g. memory bandwidth)
• There is no upper limit on transistor count.
• We can transition to new hardware immediately.
• We're looking for an absolute lower bound on the total cracking time.

How would we go about computing the length of time it would take to crack the hash? Is there a mathematical formula that expresses the geometric progression?

Answer 1

It will be significantly less. I would just set up a recurrence relation for this like so:

A(n) = A(n-1) - C * 2 ^ (N-1) and A(0) = size of keyspace, say 62^12

lets set C = 3.0*10^12 for hashes computed the first year and assume computing power doubles every year.

Plugging this into wolfram alpha yields this function solution for the recurrence relation:

recurrence relation...

f(x) ~= 3.22627x10^21 - 3.0x10^12 * 2^x

Solve f(x) = 0 for x:

x = lg (3.22627x10^21 / 3.0x10^12) where lg is log base 2

x ~= 30.00226 years

Cracked in 30 years, but that's a lot of silicon, no wasted work, and you would need a method to seemlessly integrate new hardware into the running program without stopping it.

---

Explanation:

So we have the original key space size: 62^12 and a hypothetical machine capable of incorporating Moore's Law, somehow.

My original math was off a bit. For some reason I did 3.0 x 10^9 * 1000 = 3.0 x 10^12 for calculations in a year, but it should be 3.0 x 10^9 * 3600 (seconds / hour) * 24 (hours / day) * 365 ( days / year). Anyways, that's our initial speed, which according to Moore's law will double every year. I'm going to keep the original mistake for consistency in explanation.

So in the first year, we perform 3.0x10^12 hashes of the 1.0x62^12 maximum hashes needed (assuming worst case scenario). In the second year, Moore's law applies and now we do 6.0x10^12 hashes in the second year, which gives us cumulatively 9.0x10^12 hashes calculated so far. The hashes we have left to do are found via subtraction from the whole number of hashes. We'll run the program until there are no more hashes to find.

A(N) = A(N-1) - C * 2^(N-1)

A(N) is the number of hashes remaining after this year

A(N-1) was the number of hashes previously remaining before this year

C is the initial speed

N is the number of the year (first, second, third, etc).

So every year the speed doubles, which is the 2^(N-1) part of the equation. C is the initial speed for the first year, so we have C * 2 ^ 0 = C * 1 = C. In the second year, the speed has doubled once, so we have 2 * C. In the third year, speed has the doubled from initial twice, so we have 2 * 2 * C = 2^2 * C = 2^(N-1) * C since N is 3. This forms a recurrence relation for the number of hashes left to compute.

Using a combinatorics book, you can transform a recurrence relation into a generating function. Or wolfram alpha can do it for you, if you're like me and remember generating functions can be found but have forgotten how to find them since that math class seven years ago.

Anyways, you get a function of x where x is still the year being iterated. f(x) is how many hashes are left to compute. We're done when there are 0 left. So we solve f(x) for x when f(x) = 0. The last part is algebra.

I might be off base here, but it makes sense to me :)

Answer 2

Assuming computing power of the attacker can be expressed exponentially over time:

p = a·e^bt

where t is time (t = 0 when the attacker starts trying passwords), a and b are two constants, and p is a measure of power expressed in "password tries per time unit", then the size of the space of passwords explored by the attacker over time period T is:

Moore's law more or less means that the exponential-based formula is a valid model -- within some limits. An optimistic expression of Moore's law is that, over the course of three years, transistor density has quadrupled and clocking frequency has doubled at constant budget: for the same cost, we have four times as many transistors and we can run the circuit twice faster. This would mean that b = 0.693 inverse years (logarithm of 2: power doubles every year; we express time t in years) and a is the number of passwords that the attacker can try right now with his yearly budget (say, a = 3×10¹⁷ passwords/year if the attacker begins at 10 billions per second, as would be the case for a simple salted MD5 hash and a few thousands of dollars of budget).

The calculation above assumes the following properties, which are not very realistic:

• The attacker has a renewable yearly budget, allowing him to perform regular hardware updates.
• Conversion from old to new hardware costs nothing, which is akin to declaring that software grows on tree and you just have to walk below the branches with a basket.
• The attacker can follow Moore's law. Password cracking is highly parallel, but this will still need to play with FPGA. Consumer products like CPU or GPU have other constraints which prevent them from obtaining the full power of Moore's law (in particular, memory latency does not scale as well).
• Moore's law holds. Gordon Moore himself, back in 1997, gave it about 20 more years before falling apart, i.e. until about year 2017 -- which is only four years away. Moore's law operates on the gradual application of a stock of optimization ideas which have been expressed, at least theoretically, in the 1970s. That stock is fast running out... and, indeed, we can see that clocking frequency in circuits (even ASIC) has somewhat stalled below 10 GHz.
• We can ignore energy consumption. We now know that this is not true. Energy is now a major constraint on big computations (not only for feeding the machines, but also for cooling, because all that energy becomes heat). It is also the closest boundary on theoretical computing power.

Therefore, while you can use a formula like the one I showed above, the results you will get out of it will not be very practical. I would like to add that if the attacker is sufficiently intent on spending hardware on a yearly basis in order to crack your password, then that guy is indeed your arch enemy; it won't be long before he realizes that hiring two or three thugs to break your kneecaps is vastly cheaper and more effective.

Answer 3

I could do the math given your assumptions, but the result would have little practical relevance, because your assumptions are not valid and your problem statement is missing some important context. Doing the math here without questioning the assumption would be like one of those physics jokes that begins "assume a spherical cow..."

For example, it is not reasonable to expect transistor count to increase at an exponential rate indefinitely. Power consumption scales linearly with transistor count, so you're going to hit a brick wall sooner or later on that front. In general, power is one of the main limiting factors for CPUs these days. Projecting the effect of an exponential curve over 30 years is a bit silly, as it ignores the power wall.

Second, it is rare to have a password that needs to remain secure for 30 years. In most situations, rather than trying to pick a password that will remain secure for 30 years, it is better to simply change your passwords every so often.

Third, when we are talking about a 12-character mixed-case alphanumeric truly random password, password cracking is unlikely to be the weakest link in your system. There are almost certainly going to be easier ways an attacker can defeat security.

So while I'm perfectly capable of doing the mathematical calculation under your assumptions, I'm not going to do it. It would be an exercise in mathematical masturbation. Don't me wrong -- I enjoy mathematics for its own sake -- but in this case the results would be misleading.

In short, my answer is: you are asking the wrong question. A truly random 12-character password is more than enough for the foreseeable future. If your password is that strong, stop worrying about password cracking and spend your energy defending against other threats.