What are some good references for the implementation weaknesses in RSA

Question

I'm pretty sure I understand textbook RSA.

• Choose p and q, large primes, and compute n=pq.
• Choose e such that $gcd(\phi(n),e)=1.$
• Publish n and e.
• Compute d such that $de=1$ (mod $\phi(n)$).
• To encrypt a message M, compute E=M^e (mod n).
• To decrypt, compute D=E^d (mod n), which will equal M.

There are obvious things we need to do to make this not obviously insecure, such as choose p and q large enough, but not too close together. It also helps if the ratio between p and q is not a simple rational like 2/3 or 4/7. We also need the private exponent d to be similarly large.

But there are less obvious precautions needed. A simple example is that we need to pad M, but there are others.

What is a good reference to understand the other attacks on (implementations of) RSA, and how RSA can be hardened against them?

Thanks.

Answer 1

It depends on what you are using RSA for and how deep of an understanding you would like.

A sort of general overview of RSA and potential attacks against textbook RSA is presented in the Handbook of Applied Cryptography, specifically chapter 8. (Note that the entire text is free online.) Chapters 11 and 12 also are useful to read, as they focus on specific instances of RSA. This will give you a good, brief understanding of the generics of RSA, but I wouldn't go implementing the algorithm straight out of the HAC.

Instead, if you'd like to know a good standard for implementing RSA in specific instances, I'd recommend one of the many standards on the subject (PKCS, FIPS, ISO, ...). On Wikipedia, you can find this List of PKCS. You might be interested in PKCS#1. Note that the actual RSA Labs maintains a PKCS list of its own, where you can find PDFs of the various PKCS (usually: that or .ps files). I find PDFs infinitely more pleasing to read than RFCs, so that might pique your interest.

Further, the NIST maintains a Current FIPS list. So, for example, if you were interested in using RSA for signatures, you might look at FIPS 186-3.

PKCS and FIPS aren't big on theory, however, so if you are looking for a good theoretical understanding, the HAC is probably your best bet. You might also want to look up actual published attacks in the literature. For example, searching rsa padding returns many useful results, e.g. Why textbook ElGamal and RSA are insecure by Boneh, Joux, and Nguyen. That isn't so much a reference for secure implementation, but it certainly highlights the possible attacks on the textbook implementation.

Also, you probably want to look at other known-good implementations like GPG and OpenSSL.

Answer 2

I see three kinds of weaknesses here. The need for padding is not an implementation weakness but an algorithmic weakness. RSA is not an encryption algorithm nor a signature algorithm; RSA-OAEP and RSA-PSS are. It's easy to avoid algorithmic weaknesses: stick to approved algorithms, i.e. OAEP and PSS from PKCS#1 v2. If required for interoperability, you can safely use the PKCS#1 v1.5 schemes in many scenarios, but carefully check the known weaknesses in these schemes against the specifics of your protocol first (what gets RSA'ed, how many messages with the same key, etc.).

A potential source of weaknesses is key generation — things like “use a proper random generator”, “don't pick a small $d$”, etc. This is intermediate between implementation and algorithm: it's up to the key generation algorithm, but two different implementations can use different algorithms without breaking interoperability, so there is considerable variation there.

Unfortunately, there isn't a universally-followed standard RSA key generation algorithm like there is for DSA. Reid cited the Handbook of Applied Cryptography which provides a good checklist of do's and don't's (§8.2.2–8.2.3). NIST specifies RSA key generation in FIPS 186-3 §B.3 (they're for integer factorization cryptography (IFC), which in practice means RSA). NIST also publishes generic recommendations for key generation in SP 800-133. I also recommend reading Cryptography Engineering by Bruce Schneier et al.

A different source of weaknesses comes from the implementation itself. An adversary may be able to observe secret data and extract all or part of the key or message from that. Such attacks are generically known as side channel attacks. Timing is a common one: if the adversary knows how much time an RSA operation took, he might know how many bits were 0 or 1 in the key or in some intermediate result. If the adversary can observe how CPU load, cache use, power consumption or radio emissions vary over time, he may be able to “read” the key from such side channels.

Hardening against side channels generally involves a compromise with performance. For example, blinding involves doing extra operations to encode and decode the data before and after the RSA operation, so that a side channel would only reveal information about values that incorporate a random element and from which the actual data cannot be retrieved.

Closely related to side channel attacks are fault attacks, where the adversary is able not just to observe but even to partially affect the execution of the cryptographic implementation. Fault attacks are mostly relevant to devices that must resist physical attacks such as smart cards. Hardening against fault attacks again involves a compromise with performance, for example performing the same mathematical operation in two different manners and checking that the results match.

Answer 3

As @Reid mentioned, the HAC is a good starting point. I'd also use Google Scholar to search for papers containing RSA attacks, then follow papers that have many references.

Asking about implementation attacks is an overly broad question. There have been a lot of attacks on systems that depend on RSA that have been successful, but most of those weren't attacks on RSA itself.