# Practical Attack on RSA

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.

• Key size is of little relevance when considering side channel attacks. Some kinds of side channel attacks can be prevented by constant time implementations, for some you need to shield the hardware. – CodesInChaos Jan 20 '15 at 12:32
• Check this for practical brute force attacks versus key size. $\;$ Practical attacks often are independent of key size; like, abusing a certification authority, or hacking into a computer that can use a secure device that holds the key. – fgrieu Jan 20 '15 at 13:06
• A practical attack is rarely against the cryptographic algorithm; it's much more often against a poor usage or implementation. – cpast Jan 20 '15 at 17:10
• @CodesInChaos That is true. I shouldn't mention that in my question. – Nayef Jan 21 '15 at 7:56
• @fgrieu as per the answer mentioned, the attack took two years to factor 756 or so RSA key. However, this was done 5 years ago! the computation power we have today is more powerful. – Nayef Jan 21 '15 at 7:58

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

• the bernstein paper on batch NFS doesn't seem to imply anything. Rather that we should look into this more. But asymptotic results don't help – David 天宇 Wong Nov 30 '15 at 12:29

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.

• keylength does NOT "try to estimate for how many years a given keylength may last you". Rather, it is about estimating what key length is appropriate so that one can be next to certain that at some prescribed date, brute-forcing a public key will fail (or, equivalently, about selecting a key length that conforms to prescribed standards with that aim). The former is about a best guess, the second is all about being conservative. $\;$ A decision maker has use of the former when evaluating a non-critical legacy system, and of the later for a new system. – fgrieu Jan 21 '15 at 9:04
• @fgrieu: I tend to believe you. But I don't understand you here. I think it's both a best guess AND conservative. "Use this length (plus a handful of extra bits for paranoia) and you should be okay. Unless some dramatic breakthrough happens." Right? – StackzOfZtuff Jan 21 '15 at 9:30
• My point is that "such key length will be vulnerable at about that time" (as in "estimate for how many years a given keylength may last you", what this is about) is very different from "use that key length and you should be okay" (a safe recommendation, what keylength is about). – fgrieu Jan 21 '15 at 9:50
• Okay. Your point is "Will go bad after date X" is not the same as saying "Is safe until date X". Right? – StackzOfZtuff Jan 21 '15 at 10:04
• Yes, much like for yogurt. – fgrieu Jan 21 '15 at 12:19