# What security authorities and standards reject $e=3$ in RSA, when, and with what rationale?

In RSA, some security authorities and/or standards allow the public exponent $e=3$, others require or recommend $e>2^{16}$ (or perhaps some other minimum). I gathered the following:

• PKCS#1 allows $e=3$ for both RSA digital signature and encryption (but see 3. below).
• ISO/IEC 9796-2 allows $e=3$ (in the context of RSA digital signature).
• FIPS 186-3 section B.3.1 requires $e>2^{16}$ (in the context of RSA digital signature); no rationale is given.
• ANSSI's RGS 1.0 annex B1 (French official recommendations), section 2.2.1.1, requires $e>2^{16}$ for encryption, and recommends it for every application of RSA. The rationale mentions existing attacks on RSA encryption schemes with very small exponents, but they are left unspecified.

I'm asking the status with other standards and authorities, and any justification to the ban of low public exponent they give, or otherwise exists, including in the context of attacks on implementations (e.g. side-channel attacks).

Ultimately, I want to understand the conditions to use RSA with $e=3$ safely, and inasmuch as possible without clash with official security recommendations, or at least their rationale. That's because I am considering using $e=3$ for some RSA digital signature scheme, and for authentication based on RSA encryption of a random challenge. In such applications, $e=2^{16}+1$ would make the verifier's job like eight times slower than $e=3$.

My list of reasons not to use low public exponent, in particular $e=3$, has grown to:

1. RSA without padding is vulnerable to a non-modular $e^{th}$ root attack, for some bound on the size of input which is a concern for low $e$ only.
2. RSA encryption is vulnerable when sending the same message to $e$ recipients using the same padding for each recipient. For this (and a gentle introduction to the attack in 3. below) see Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, section 4. Note: a nice comment by @CodesInChaos explain how the recipient's public key could be used rather than randomness to fix the multiple-recipients vulnerability; however some randomness is still required for semantic security, as in any public-key encryption scheme.
3. With less than about $n/e^2$ bits of random padding (where $n$ is the bit length of the public modulus N), RSA encryption is vulnerable; see Don Coppersmith's Small solutions to polynomial equations, and low exponent RSA vulnerabilities. This bound has been extended in practical use cases by Coron, Joye, Naccache and Paillier in New Attacks on PKCS#1 v1.5 Encryption, assuming that a suitable section of the plaintext is all-zero. PKCS#1v2.2 now warns to guard against these attacks when using RSAES-PKCS1-V1_5 in combination with low public exponent, and recommends not using this scheme to encipher arbitrary plaintext (which, contrary to random keys, could exhibit the characteristic enabling the new attack, which remains threatening to some lesser degree for any public exponent).
4. Some questionable RSA signature padding schemes are worse with low exponents. An example is the INCITS/ISO/IEC 9796:1991 digital signature standard (also in section 11.3.5 of the Handbook of Applied Cryptography), that was withdrawn following attacks: the padding scheme turned out to be slightly worse for $e=3$ than for $e=2^{16}+1$ (forgery from the signature of a single chosen messages for $e=3$, versus a grand three chosen messages for $e=2^{16}+1$).
5. (latest update) A general class of attacks based on factorization of poorly padded messages, introduced by Desmedt and Odlyzko in A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, is perhaps (I have not made my mind) slightly easier for low public exponent $e$, in particular when applied to chosen-message attacks on some ad-hoc signature schemes, like ISO/IEC 9796-2 scheme 1, as in this attack (because the limiting step is picking a non-trivial linear combination of sparse vectors summing to zero, with elements of the vectors in $\mathbb Z_e$).
6. (update) Some attacks on implementations based on partial information about the private key (e.g. obtained by approximate extraction of DRAM content by cold-boot attack) have reported cost growing with $e$; e.g. Heninger and Shacham's Reconstructing RSA Private Keys from Random Key Bits, and perhaps Constantinos Patsakis's RSA private key reconstruction from random bits using SAT solvers.

With the exception of attack on implementations, I have so far located no attack enabled by low RSA public exponent:

• in an encryption scheme raising an essentially random element in $\mathbb Z_N$ to the public exponent, as in naked RSA with the message random and about the size of the public modulus; RSAES-PKCS1-V1_5 when enciphering random plaintext of any size; and RSAES-PSS with any plaintext;
• in a signature scheme with an otherwise fully unbroken padding, including those randomized following the principle of full domain hash (giving a strong argument of equivalence to the underlying RSA problem with $e=3$), such as RSASSA-PSS of PKCS#1v2, and ISO/IEC 9796-2 schemes 2 and 3 (introduced in the 2002 edition, unmodified in the 2010 edition; scheme 1, also known as ISO/IEC 9796-2:1997, does not have such proof).
-
You don't need random padding to avoid the $e$ recipients vulnerability. You could make the padding depend on the recipient's public key e.g. hash(e||n). –  CodesInChaos May 25 '13 at 17:42
I would guess that the differences in the standards you posted is simply a matter of how conservative about security the standards committees are. Like you, I haven't found any fatal attack against RSA with $e=3$ assuming proper padding, but I suspect the standards that require $e>2^{16}$ are nervous about all of the potential traps an implementer could fall into with $e=3$. –  Reid May 25 '13 at 18:26
Honestly, I think everything below the horizontal rule would make a great self-answer to this question. –  Reid May 27 '13 at 2:03
@Reid: I'll think about making the second part a separate answer/community wiki. But it is not a satisfactory answer, at least yet. I am afraid that I do not have a complete list of relevant attacks, and more generally reasons to avoid very low public exponents. In particular I did not touch hardness of the RSA problem for random argument w.r.t. low public exponent; and implementation attacks. And there are other standards and official recommendations. –  fgrieu May 27 '13 at 4:36
one thing I can think of is that because $gcd((p-1)(q-1),e)$ needs to be 1 then if $e=3$ then $(p-1)(q-1) \mod 3\neq 0$ and thus $q \mod 3 \neq 1$ and $p \mod 3 \neq 1$ –  ratchet freak May 27 '13 at 13:07

The advice to avoid $e=3$ comes down primarily to superstition, historical inertia, and general caution, rather than anything with a solid technical basis.

Historically, some of the early schemes that used $e=3$ were subject to attack. At the time, many folks drew the conclusion that this means $e=3$ is insecure. However, we now know that that conclusion was faulty. We now know that the real problem was failure to use a secure padding scheme.

As long as you use a secure padding scheme, using $e=3$ is perfectly safe. So, use any well-regarded provably-secure padding scheme, and $e=3$ is fine.

In fact, there's no real reason why you need to use $e=3$, either. If you want to squeeze out every last bit of possible performance out of the verification operation, there are perfectly safe variations on RSA that effectively use $e=2$. You have to make some slight tweaks to the scheme (to account for the fact that $\gcd(e,\varphi(n))\ne 1$), but it's been worked out how to do that. If you want to make verification as fast as humanly possible, Dan Bernstein has several papers that show how to do this, by using a variety of tricks: one trick is to use $e=2$; another trick is to check the verification condition (namely, $s^2=H(m)$) modulo a small secret prime. See his papers for more details.

-
Nice to see this voiced in no uncertain terms! That makes me even more willing to trust "full domain" padding schemes with $e=3$ (despite my current lack of understanding of the debate on theoretical hardness of the RSA problem for $e=3$ vs random $e$). But there's also the issue of implementations attacks. Perhaps $e=3$ makes side channel leakage in encryption more of a concern? –  fgrieu May 28 '13 at 10:27
On using $e=2$: I love Rabin schemes for their performance. But there's a very real practical issue: current lack of support in commercial security-evaluated devices (Smart Cards, HSMs) of even standardized schemes (ISO/IEC 9796-2 with $e=2$). Also the common description of this is one mistake/fault/weakness away from total disaster (messing up the Jacobi evaluation reveals the secret key, so does an attack on padding); and Jacobi evaluation (required for semantic security of encryption AFAIK, and also a concern when signing secret material) has its channel leakage hardly explored. –  fgrieu May 28 '13 at 10:32
@fgrieu Personally, when I see a string of partial attacks on e=3, that leads me to worry about future development of more general attacks. Why not reduce the risk now at minimal cost by using a larger exponent? –  Antimony May 29 '13 at 6:18
@Antinomy: the "partial attacks on e=3" we have (at least the ones not related to implementation weaknesses) are best (IMHO) described as attacks on ad-hoc padding schemes, that happen to be slightly facilitated by $e=3$. But padding schemes with a security argument (or "proof") have one that holds for $e=3$, so why reject $e=3$ with such schemes when $e=3$ has other serious advantages, like being 8 times faster on the public-key side? –  fgrieu May 29 '13 at 6:22

Rather than making an overly long question even longer, I post this as an answer.

As part of the update process of the French security recommendations linked in the question, I suggested (June 2013) a waiver for the requirement/recommendation that $e>2^{16}$ when using a padding scheme with a security proof. It was kindly refused (within 6 weeks), with rationale. The updated rules and recommendations V2.03 (in French) forming Annex B1 of the general security referential RGS V2 (in French), as approved (in French) June 2014, is identical in this regard [a noticeable change though: 2048-bit RSA is deemed good to 2030 rather than 2020 in the previous edition].

Here is the rationale, paraphrased and condensed to $2\over5$ (originally in French, attributed to the cryptographic laboratory of ANSSI / SDE / ST / LCR):

1. On argument can me made that no attack effective against RSA with $e=3$ and a padding scheme with security proof is currently known. However, it is generally useful to keep some safety margin w.r.t. the state of the art in cryptanalytic attacks, as such margin could minimize the impact of new cryptanalytic advances, should they occur.
2. While the "classic" security proof of RSA-OAEP works assuming the hardness of the RSA problem for random plaintext, independent of the magnitude of $e$, recent articles [KOS10, LOS13] suggest a proof of RSA-OAEP in the standard model based on the "Phi-Hidding" hypothesis. That proof requires a large enough $e$ and gives no assurance for low $e$. Therefore, form the standpoint of provable security, large $e$ arguably gives increased security insurance.
3. Security proof of RSA-OAEP is not an absolute insurance of security, for there can be attacks outside a proof's framework. Examples of unaccounted parameters are errors in data formatting, use of a poor RNG or hash function (the "classic" security proof of RSA-OAEP uses a random oracle model).
4. A review of the rich existing literature suggest low exponents are more vulnerable. For example, many attacks on RSA PKCS#1 v1.5 [CFPR96, CNJP00, BCNTV10] apply for small $e$ only.
5. The recommendation makes a satisfactory distinction between encryption (where $e<2^{16}+1$ is prohibited) and signature (where such $e$ is only discouraged), because:
• More attacks exploiting low $e$ have been proposed against encryption schemes than against signature schemes; that may be because attacks against encryption in general are easier to perform and harder to prevent.
• Gradual weakening could prove much more a problem for an encryption scheme than for a signature scheme. That's because a successful attack (e.g. against RSA-OAEP) would compromise long-term confidentiality of past messages; while in the case of signature, there are many application for which a relatively short validity of signatures is acceptable (e.g. access control); or, it might be acceptable to increase the validity of a signature made with an obsolete mechanism by having an authority re-issue a signature before the attack becomes realistic.

Comment: I very much appreciate the balanced arguments in this rationale. In point 3, I interpret errors in data formatting [en Français: erreurs de formatage des données] to include fault injection, which indeed is an area where $e=3$ could facilitate attacks against a scheme (signature or encryption) with provable security and randomized message representative. My opinion remains that beyond fault injection and side-channels (timing, power analysis and friends), emergence of such attack is highly implausible.