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

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.

Answer 3

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 4

First I apologize that I don't have a real answer to your question, but my hunch is yes. And I've been working to derive a similar formula from a fairly specific scenario, but I believe if I can prove my hypothesis, it could be generalized more to actually answer your question fully.

I've received similar resistance from folks concerned with the "practical significance" of results from a strict and unrealistic hypothetical scenario. The concerns of infinite resources is valid, but Rock's law can indeed be factored in mathematically for a more accurate analysis of the problem. Still, I think it's unsafe from a defender's perspective to place strict limits on the resources available to any the attacker of actual concern in the first place for a number of practical reasons to include the realistic assumption that by her very nature, an attacker may at any point in time have access to any number of stolen credit cards, for example.

I used the what I was taught to be a more accurate assumption that processing power doubles every 18 months.

In other words, if at time 0 processing power is P(O), in 18 months, the processing power available is P(0)*2^1.5. (It is worth noting that after 3 years, the processing power has therefore exactly quadrupled).

I'm still struggling to prove the observations I made with a spreadsheet mathematically but I'm pretty confident in my formulas. I found the almost too obvious to trust results that no mater what the initial processing speed is, and regardless of how many years it takes to get to this point, after you have cracked 1/4 of the total password space, you will crack the remaining 3/4 in no more than three years! Since processing power quadruples in 3 years, this seems plausible, but the natural doubt is in determining the initial processing power as it seems that would significantly impact the observations.

I've tried playing with keyspace and initial inputs, but haven't been able to break my spreadsheet yet.

I computed that on an annual basis, the processing power increases by 2^(2/3) to develop a discrete recurrence relationship.

Scenario wise, this means that the attacker upgrades annually to the current processing power without loss of time. Yes it's unrealistic from an absolute perspective, but I'm working under the assumption that the relative significance of transfer time will trend toward 0 as processing power and key space increases. And would bet dollars to donuts this could be proven mathematically.

So the relationship becomes

Given some constant P(0), P(1) = P(0)*2^(2/3). P(2) = P(1) * 2^(2/3) = P(0) * 2^(2/3) * 2^(2/3).

We can see soon that P(i) = P(0) * 2^(2i/3).

So we have defined P(i) as the number of password cracked in year i using the processing power available at the beginning of year i.

In other words, P(n) = P(0)*2((2*0)/3) + P(0)*2((2*1)/3) + P(0)*2((2*2)/3) + ... P(0)2((2(n-1))/3) + P(0)*2((2*n)/3).

Or P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3) + 2^(2n/3))

Now we can look at the relationship between password space and time taken to crack additional space.

We were given that a 128 bit keyspace can be cracked in 100 years, and determined that adding two more bits (for a total of 130 bits) quadrupled the key space.

So regardless of the original process speed or keys cracked in one year, we know that after 100 years we have cracked the full 128 bit space and that that space is 1/4 of the new password space. So after 100 years we have cracked 1/4 of the total space, and we want to know how many more years before we crack the remaining 3/4.

Lets start at n years to crack the full space which we can express as:

P(n) = P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3) + 2^(2n/3)) = 100% of the space.

And the year before (n-1) we have cracked a total of

P(n-1) = P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3))

What fraction of the total key space have we cracked by year n-1?

P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3))

P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3) + 2^(2n/3))

And

P(n-3)

P(n)

=

P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-3)/3))

P(0)(1 + 2^(2/3) + 2^(4/3) + ... + 2^((n-1)/3) + 2^(2n/3))

And here's where my arithmetic and induction and mathematical foundations continues to fail me, and I get stymied with a formal proof, but my observations suggest this should simplify to 1/4 for significantly sized n.

My interest is in determining a mathematical proof to explain the somewhat intuitive but nonetheless surprising conclusions.

Mine is a question to help determine the maximum additional security a fixed expansion of password space actually adds in terms of the time it takes for a cracker to fully compute all possible pawned hashes in a given space.

We have to accept a lot of less-than realistic assumptions for the different variables to develop a strict mathematically provable relationship from which to then determine if our assumptions about the added benefit of additional characters in a password length are realistic to begin with.

I was given a test problem: if a cracker can compute the every hash in a key space defined from a 128 character binary alphabet, how long will it take her to crack a 130 bit binary key space?

The "correct" answer was 400 years. I argued that the question was poorly defined since taking Moore's law into account we know that even though the key space has quadrupled (2 additional bits creates 4 times as many options assuming all options are valid passwords) the time taken to crack it will be less than four times as long.

"Significantly" less is indeed accurate, but after failing to define how much less through a formal proof, I used a spreadsheet to generate hard data to help guide my approach to the proof.