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

Question

 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-4 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. Attacks on RSA decryption implementations thru side channels in padding check, including Bleichenbacher's attack on RSAES-PKCS1-v1_5, are practical for very low $e$ like $e=3$, and seem adequately mitigated for $e=65537$. Implementations vulnerable to that were the norm when today's RSA key generation standards have been written.
3. 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 4. 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.
4. 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).
5. 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$).
6. A more general class of attacks based on the 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 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$).
7. (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 the 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 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).

Answer 1

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.

Answer 2

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. An 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-Hiding" hypothesis. That proof requires a large enough $e$ and gives no assurance for low $e$. Therefore, from 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.

[KOS10] Eike Kiltz, Adam O’Neill, Adam Smith: Instantiability of RSA-OAEP under Chosen-Plaintext Attack, in proceedings of Crypto 2010 (full article).

[LOS13] Mark Lewko, Adam O’Neill, Adam Smith: Regularity of Lossy RSA on Subdomains and Its Applications, in proceedings of EuroCrypt 2013.

[CFPR96] Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reiter: Low-Exponent RSA with Related Messages, in proceedings of EuroCrypt 1996.

[CNJP00] Jean-Sébastien Coron, Marc Joye, David Naccache, Pascal Paillier: New Attacks on PKCS#1 v1.5 Encryption, in proceedings of EuroCrypt 2000.

[BCNTV10] Aurélie Bauer, Jean-Sébastien Coron, David Naccache, Mehdi Tibouchi, Damien Vergnaud: On the Broadcast and Validity-Checking Security of PKCS#1 v1.5 Encryption, in proceedings of ACNS 2010 (full article).

---

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.