8
$\begingroup$

It seems to be common practice (at least in some communities) to tack on the phrase "with current computing power" when estimating the absurdly long time it would take to, for example, brute-force an ECDSA private key or find an SHA256 collision, but am I wrong in thinking that these calculations should account for the ever-increasing power of the "average" computer?

In short, when making an educated guess of time-to-crack via brute force, is there a some kind of easy "fudge factor" to include that accounts for likely technological improvements a la Moore's Law (et al)?

$\endgroup$

2 Answers 2

7
$\begingroup$

Moore's law has several variants. Gordon Moore himself first put it as a double of transistor density every year (i.e. you could put twice as many transistors on a given wafer surface, and production cost increases linearly with the wafer surface). In 1975, Moore altered his law to a double every two years. However, putting more transistors in a given surface also entails making them smaller and closer to each other, and this allows for clocking them at higher rates, too. So the "classical" version of Moore's law is "double performance every 18 months".

Performance depends on the kind of task you are trying to perform. For a general purpose computer, having more transistors does not makes things really better beyond a given point -- if you want to add "real-life" values which fit in 32 bits, then having 64-bit registers will not give you a boost. At some point, "many transistors" turns into "several cores", which helps a lot if (and only if) the task at hand is amenable to parallelism.

For symmetric cryptography, we usually worry about exhaustive search. The cost-effective attacker will use FPGA or ASIC. Parallelism is a given, so the attacker benefits from advances in both transistor density and clock rates. However, for the truly massive attack jobs, energy consumption (and its offspring heat dissipation) becomes a bottleneck, and higher clock rates do not help for that. So you can consider Moore's law to amount to about "1 bit per year" (a 100-bit key is as robust now as a 120-bit key will be in 20 years).

For elliptic curves, the most efficient attack is discrete logarithm using the "generic" algorithms, which work in $O(\sqrt{N})$ for a curve of size $N$. This means that a 256-bit curve fares about as well as a 128-bit symmetric key. Moore's law, then, yields "2 bits per year" of computing power to the attacker.

For integer factorization and classical discrete logarithm (i.e. RSA, DSA, Diffie-Hellman, ElGamal... but not the EC variants thereof), things are more complex. The best known algorithms are subexponential (that's the General Number Field Sieve); but their implementation requires large amounts of fast RAM. RAM size increases with transistor density as per Moore's law, but RAM latency does not get better as fast as that. In fact, base RAM latency is more or less stalled in recent computers. Therefore, it is difficult to give even a rough estimate of Moore's law effect on RSA security.

To account for Moore's law, several individuals and organizations have published estimates of key strength, as "recommendations" for minimal key length, now and in the next few decades. These recommendations vary quite widely from each other; there is a nice summary (with online calculators) on this site. The recommendations always use worst case estimates: they do not want to predict the actual attack cost, they aim at presenting key sizes which are "large enough" to thwart attacks. Therefore, each figure is a mixture of attack cost estimates, and a more or less generous amount of paranoia. For instance, NIST recommends not using 1024-bit RSA keys since last year, and yet the current RSA-breaking record is 768 bits, are it is known right now (2012) that existing academic resources are far from being sufficient to attack a 1024-bit RSA key.

As a very crude but effective estimate: 112-bit symmetric keys, 224-bit elliptic curves, and 2048-bit RSA/DSA/DH keys, ought to be enough for the next two decades (at least).

$\endgroup$
2
$\begingroup$

There was a blog post on the same issue in 2009. Yes, it is right that RSA based on 1024 bit $N$ might be insecure after few years and it is not that cryptographer and practioneers are not aware of and NIST regularly updates its recommendations. The earlier recommendations were to use 512 bits prime and as we all know it does not take a lot of effort by nowadays computer to break it, even by brute force. The same applies for Diffie-Hellman problem. The size of key increases as the computation power increases. Of course, we always have the heuristics that AES has been not broken in past 13-14 years of its existence and hence must be secure.

Now the above was a practioneers point of view. I will follow up with a theoretician point of view of the above issues.

From the theoretical point of view, we always get the security guarantee in two formats: concrete security and asymptotic security. Unfortunately, there is no middle path that uses the best of both the world. In concrete security analysis, you say that suppose you give a computer $t$ time (you can see it as MIPS or whatever measure you use to measure the computational power), then it will succeed in breaking the scheme by probability at most $\epsilon$. Here you run in the trouble of having no knowledge of what to do when the parameters are different than what you analyzed.

From the asymptotic point of view, you measure the security of the cryptosystem by analyzing the security as the security parameter increases. This method does have all the drawback of asymptotic analysis and it might be true that you can't have a secure system if you use a small input size.

Now lets try give a convincing answer to your question. Yes, people do answer the security in terms of Moore's law and the answer is usually of the form: with increase in computing power, you also have an ease of memory. So just increase the key size! Okay, that's not convincing and I would love to see a more convincing argument.

$\endgroup$
2
  • $\begingroup$ The reason not to use way larger keys already now is certainly not limited memory on average computers (you can have lots of 4096 bit keys in RAM on a computer from 1990), but that processing time goes up, too (and usually more than linear). (And maybe limited memory on smart card and similar processors.) $\endgroup$ Commented Feb 4, 2012 at 21:09
  • $\begingroup$ Thanks for correcting me. I know these stuffs from theoretical point of view and to be honest, don't have much idea about practice. $\endgroup$
    – Jalaj
    Commented Feb 4, 2012 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.