It seems to be common practice (at least in some communities) to tack on the phr

Question

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)?

Explanation / Answer

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 ?. 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.