Practical Attack on RSA

Question

Currently I am designing an RSA based application, and I am thinking of how long should the key be in order to be secure against attacks. I know that RSA 4096 bit key can be recovered using Sound Pattern attack yet it is not practical. Brute Force is impossible unless if a quantum computer is available with the claimed computation power. How long shall the RSA key be in order to be secure against practical attacks?

Update: There exist many techniques which are much faster than brute force attack. Actually we can assume that no one can break RSA cryptosystem with brute force attack. number field sieve was used by Aoki and others in Factorization of a 768-bit RSA modulus to factor 768 bit RSA key. In addition, they predict that RSA 1024 will be factorised by 2019.

Also, if a bad random number generator is used two parties might have the same keys! as described in Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

What is your recommendation? Is there any new advancement in factorization? so the key size should always be longer than the factorable key length. Can I use Microsoft RSA Implementation?

Thank you.

Answer 1

Q: How long shall the RSA key be in order to be secure against practical attacks?

A: Impractically large. This does not imply that RSA is unsafe against practical attacks; only that some of these attacks must be prevented by ways other than increasing the key size.

That's because key size is not a parameter with a major impact on the efficiency of many attacks against RSA, with the exception of factorization of the public modulus. For example, in (Simple) Power Analysis of RSA (without CRT), the secret exponent $d$ is directly recovered from observation of the power trace of one execution of the private-key function, thus any increase in public modulus length making attack impractical also makes usage impractical.

For less severe signal leakage (like in the sound pattern attack linked to in the question), the attack may require a number of executions of the private-key function growing with the key size (all things being equal), perhaps linearly or per some other slow-growing function; but again increasing the key size will make the system impractical before it gets safe.

Q: Is there any new advancement in factorization?

A: Publicly, no experimental progress. The state of the academic art remains close to that when factorizing RSA-768 in late 2009. However there has been claims of breakthrough by the NSA which could be explained by factoring 1024-bit RSA moduli; quoting that Wired article quoting an unnamed former senior intelligence official

“They made a big breakthrough” (..) “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

One of the few notable theoretical progress that I'm aware of is: Daniel J. Bernstein and Tanja Lange, Batch NFS, in proceedings of SAC 2014, free on ePrint in revised version.

Independently of NSA breakthrough claims, because both technical and theoretical progress has not stopped, it would be prudent to assume that 1024-bit RSA is vulnerable to factorization these days, if even a small fraction of the funding of the NSA is poured into trying that; see this answer.

Q: What is your recommendation?

A: With respect to public modulus size: French authorities recently vetted 2048-bit RSA good enough for civilian use up to year 2030 at least (rather than year 2020 formerly), and ask for 3072-bit RSA afterwards. When there is incentive (like: efficiency, compatibility, availability, or cost) not to use something wider, or/and good reason to fear side-channel or fault attacks attacks (e.g. in a Smart Card), I find 2048-bit a reasonable choice for many systems.

A: With respect to choice of implementation: know precisely what you trust and why, or delegate that to competent parties that you have reasons to trust. That's what Common Criteria security certification aims at. Microsoft RSA Implementation is not something well defined enough that advice can be given about it.

Answer 2

Use Keylength.com
There are several metrics that try to estimate for how many years a given keylength may last you.

The length calculator at Keylength.com (http://www.keylength.com/en/compare/ ) uses eight such heuristics to give you a general idea which size you should choose.

You can go both directions. You can either enter a year and receive a recommended keylength, or you can input a keylength and receive a year as output.

For RSA, the "Factoring Modulus" column in the output is the one you want.