RSA is the most important public key signature and encryption algorithm. If you use a webpage with HTTPS it likely uses RSA.
What's this e?An RSA public key contains two numbers: A large number called the modulus (usually called N) and an exponent (usually called e).
e can be quite small, 3 is the smallest possible value. A very common (and better) value is 65537.
Why is e=3 a problem?There are various attacks on faulty RSA implementations that only work with e=3. The most important one is the so-called Bleichenbacher attack.
It was first presented at the Crypto 2006 conference. It exploits a common error in the parsing of RSA signatures. Both NSS and OpenSSL were found to be vulnerable.
In 2014 a variant of this attack called BERserk was found. It affected NSS, CyaSSL and also some unreleased OpenSSL code.
There is also a problem when using small exponents with something called Textbook-RSA. However, this is not a practical problem, because Textbook-RSA should never be used at all.
So this is only a problem with buggy implementations?Yes. However, as variations of this bug have been found five times it seems wise to avoid the whole attack altogether by avoiding very small exponents, especially e=3.
Shouldn't we fix the signature parsing instead?Of course. Fixing the signature verification routines needs to be done (and all known instances of this bug have been fixed).
Avoiding small exponents is an additional safety precaution.
So if my website's certificate doesn't use e=3 I'm fine?Unfortunately not.
The problem is that browsers ship a list of trusted root certificates from certificate authorities (CAs). Every CA can create a certificate for every website (unless you use some kind of key pinning).
Avoiding e=3 only helps if there is no CA that uses e=3. There are still a couple of them (see next question).
How widespread is e=3?The Debian ca-certificate package (which contains mostly the same CAs as many browsers) has six Certificate Authorities with e=3 (Camerfirma Chambers of Commerce Root, Camerfirma Global Chambersign Root, Digital Signature Trust Co. Global CA 1, Digital Signature Trust Co. Global CA 3, Go Daddy Class 2 CA, Starfield Class 2 CA). These are the biggest problem.
The latest data from the HTTPS Ecosystem Scan (2014-02-05) contains 21 valid CAs and Sub-CAs with e=3 (1713 with e=65537).
It contains 1826 Mozilla-accepte valid certificates with e=3 (7489351 with e=65537) and 223087 total certificates with e=3 (41344878 with e=65537).
Given those numbers valid certificates with e=3 are quite rare. The biggest problem are the CA certificates with e=3.
Can we do any better?We could. The root of the whole problem is an old encryption standard called PKCS #1 1.5 which defines how RSA signatures and encryption should take place. There is a better standard called PKCS #1 2.1 which introduces new RSA padding modes called PSS and OAEP.
Unfortunately although PKCS #1 2.1 was published 2002 it is still rarely used at all. Even modern crypto standards still stick with PKCS #1 1.5 (more about this in my diploma thesis).