Subject: [Cfrg] e=3 a bad idea?

From: "Steven M. Bellovin" <[email-masked]>
Date: Tue, 19 Sep 2006 11:21:03 -0400

Is it worth having a short BCP suggesting that e=3 is in general a bad
idea?  I've seen several different attacks that all work against low
exponents, most recently Bleichenbacher's new attack on PKCS #1 v1.5.
(Two others are
http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf
and http://www.cs.ucdavis.edu/~franklin/pubs/low_rsa.ps ).  Yes, all of
these require other factors to be effective, but what's the next attack?

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Tue, 19 Sep 2006 13:02:25 -0700

Hi Steve,

a BCP recommending RSA exponents sounds like a great idea to me.  I  
share your concerns with e=3, though I'm not an expert in that area -  
for all I know that exponent may be regarded as acceptable under some  
circumstances.   If so, it would be valuable to document those  
conditions, so I'm in favor of a BCP regardless.

FWIW, there was a question about e=3 last year about whether or not  
that parameter choice was OK to recommend for use in RFC 4359 (http:// 
www1.ietf.org/mail-archive/web/cfrg/current/msg00597.html).  It was  
mentioned that it might be OK to use e=3 with OAEP, but IIRC there  
was no discussion on this point (either for or against).

David

--

p.s. - a couple more attacks, which won't work against PKCS#1 AFAIK  
but which support your suggestion:

Don Coppersmith: Small Solutions to Polynomial Equations, and Low  
Exponent RSA Vulnerabilities. J. Cryptology 10(4): 233-260 (1997)

and

http://citeseer.ist.psu.edu/coppersmith96lowexponent.html

On Sep 19, 2006, at 8:21 AM, Steven M. Bellovin wrote:

> http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/ 
> hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf

---

From: Wan-Teh Chang <[email-masked]>
Date: Wed, 20 Sep 2006 07:03:59 -0700

You may want to cite the following in the BCP.

The draft revision of the US Federal digital signature
standard, Draft FIPS 186-3, requires that the RSA public
exponent e be an odd positive integer >= 65,537.
See Appendix B.3.1 Criteria for IFC Key Pairs on p. 61:

   (b) The exponent e shall be an odd positive integer such that
           65,537 <= e < 2**(nlen - 2*security_strength)
       where nlen is the length of the modulus n in bits.

http://csrc.nist.gov/publications/drafts.html#fips186-3
http://csrc.nist.gov/publications/drafts/fips_186-3/Draft-FIPS-186-3%20_March2006.pdf

Wan-Teh

---

From: "Ben Laurie" <[email-masked]>
Date: Wed, 20 Sep 2006 16:31:29 +0200

> conditions, so I'm in favor of a BCP regardless.

e=3 is acceptable quite often - so long as you make no mistakes. The
issue really is that e=3 appears to allow a wide variety of errors to
be exploited that would not be exploitable with larger exponents.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 20 Sep 2006 10:34:39 -0400

> http://csrc.nist.gov/publications/drafts/fips_186-3/Draft-FIPS-186-3%20_March2006.pdf
Thank you -- *very* interesting.  (To save others the trouble,
"security_strength" appears to be the symmetric system attack work factor,
i.e., 128 for AES-128.)

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 20 Sep 2006 10:41:23 -0400

> be exploited that would not be exploitable with larger exponents.
Right -- and there seems to be an ever-growing list of mistakes...  That's
precisely my concern; e=3 seems to be a lot more fragile and a lot harder
to use properly  than, say, 65537.

---

From: Wan-Teh Chang <[email-masked]>
Date: Wed, 20 Sep 2006 18:48:36 -0700

> "security_strength" appears to be the symmetric system attack work factor,

I think your're right.  The security strengths of various
cryptographic algorithms can be found in Table 2 and Table 3
of NIST SP 800-57 Part 1, Section 5.6.1, on pages 63-64.

http://csrc.nist.gov/publications/nistpubs/#sp800-57
http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf

I'm curious as to where the Draft FIPS 186-3 requirement
     65,537 <= e < 2**(nlen - 2*security_strength)
comes from.  Does anyone know?

Wan-Teh

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 20 Sep 2006 22:37:07 -0400

> comes from.  Does anyone know?
I'd like an answer to that, too.  Note that the exponent of 2 goes up with
modulus size, but goes down as symmetric system strength increases.  Given
that the latter should, in theory, be correlated with the former, it seems
odd, to say the least.

---

From: Daniel Brown <[email-masked]>
Date: Thu, 21 Sep 2006 10:16:22 -0400

"Steven M. Bellovin" <[email-masked]> wrote on 09/20/2006 10:37:07 

> > >> You may want to cite the following in the BCP.

...

> > > "security_strength" appears to be the symmetric system attack work 
factor,

...

>       --Steven M. Bellovin, http://www.cs.columbia.edu/~smb

As I understand it, the lower bound is due to security concerns about low 
public exponent, while the upper bound is there mainly to prevent somebody 
from making the terrible mistake of using their private exponent d as a 
public exponent.  Somebody might naively do this as an effort to use the 
encrytion key as signing key, because RSA signing is sometimes described 
as encrypting with the private exponent.  Generally, a private exponent d 
will be almost uniformly distributed in the interval [1,n-1], especially 
if e is chosen before n.  Therefore the probability that a private 
exponent d meets the upper bound is about 2**(-2*security_strength).  This 
helps explain why security_strength appears with a negative sign in the 
exponent, if not the factor 2.  As a heads up, however, I've heard that 
there is a move afoot to place a fixed upper bound on the public exponent 
e, at least for encryption.

Aside: For some rather theoretical reasons, I've recommended in IACR 
eprint that the public exponent e be divisible by 3.  The rationale is 
that the smaller factor e has, the easier it is to relate the hardness of 
the problem of finding eth roots to the hardness of factoring.  (For 
example, if e is even, then the problems are equivalent.)  In particular, 
e = 3(2^16 + 1) is an apt choice, because finding eth roots is at least as 
hard as finding 3rd and (2^16+1)th roots, both of which of tried and true 
hard problems in practice.  Although the eprint has not been peer reviewed 
yet, I believe there will be a peer reviewed paper at Asiacrypt 2006 that 
refers to it. 

Dan Brown
(905) 501-3857
http://www.certicom.com