Why can't Bleichenbacher's Attack work for RSA public exponents with values equal to 65537 and above? Does the fact that 65337 is a prime number have any relevance to it?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.
The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.
In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities recommend that for new applications, and $e\ge65537$ everywhere; see this for more.
Digression: Why 65537?
Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.
Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).
Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.
-
$\begingroup$ Trying different values for $e$ didn't produce any noticeable slowdown using the default Java RSA implementation, so it may be common to chose F4 but in real life the expected speedup may be non-existent. By now it is just a sensible default, I guess. $\endgroup$– Maarten Bodewes ♦Commented Sep 17, 2017 at 21:50
-
1$\begingroup$ Are you measuring the public-key operation or the private-key operation? The performance of the private-key operation is independent of the public exponent (unless you choose a small private exponent and derive the public one from that, but that's a bad idea). The performance of the public-key operation is $(\text{cost of $|n|$-bit squaring})\cdot\log_2 e + (\text{cost of $|n|$-bit multiply})\cdot\operatorname{Hamming-Weight}(e)$. It is usually quite easy to measure the difference in public-key operations between $e = 3$ and $e = 65537$: the latter is approximately fifteen times slower. $\endgroup$ Commented Sep 17, 2017 at 23:27
-
$\begingroup$ @fgrieu: Don't forget the much simpler, faster, safer schemes RSA-FDH and RSA-KEM! $\endgroup$ Commented Sep 17, 2017 at 23:41
-
$\begingroup$ @Squeamish Ossifrage: The difference in RSA public-key function timing between $e=65537$ and $e=3$ is usually by about a factor slightly below $(16+1)/(1+1)$ (that is like eight, not "fifteen"), often less for implementations using Montgomery arithmetic or DPA countermeasures (the later makes sense for encryption, and the former allows code reuse). I'm seeing RSA-FDH as a design principle for deterministic RSA signature schemes, prescribing to use a public hash into $\mathbb Z_N$. Is there a specification for RSA-FDH, in the sense that it allows implementations to inter-operate? $\endgroup$– fgrieu ♦Commented Sep 18, 2017 at 13:06
-
$\begingroup$ @fgrieu: 15 is just a couple off-by-one errors away from 8 in that formula, and as we all know, there are only two hard problems in computing: naming, cache invalidation, and off-by-one errors! As for RSA-FDH, I'm not aware of a standard, but, e.g., djb's Rabin–Williams instantiation uses a prescribed hash function, and you could trivially instantiate it with SHAKE256. $\endgroup$ Commented Sep 18, 2017 at 13:28