[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: <FRousseau@chrysalis-its.com>, <ietf-smime@imc.org>, <ietf-tls@lists.certicom.com>, <ipsec@lists.tislabs.com>*Subject*: Re: New Time and Space Based Key Size Equivalents for RSA andDiffie-Hellman*From*: "Bob Jueneman" <bjueneman@novell.com>*Date*: Thu, 14 Dec 2000 10:54:34 -0700*Cc*: <ietf-pkix@imc.org>*Sender*: owner-ipsec@lists.tislabs.com

Francois,

I haven't followed the latest thinking on breaking algorithms
such as RSA, so I'll take your word for the fact that the Number Field Sieve is
currently the most efficient algorithm. But isn't it at least possible
that there might be other methods that although less efficient than the
NFS on a single machine, might be more well-suited to a distributed
attack? Likewise, would other algorithms be less constrained by a 64-bit
addressing limitation?

Interesting point, though, in any case.

Regards,

Bob

Robert R. Jueneman

Security Architect

Novell, Inc.

>>> <FRousseau@chrysalis-its.com> 12/13/00 10:36PM >>>

I am sorry for the multiple postings, but I thought this particular subject, although probably quite controversial, might be of interest to the many peoples following these mailing lists, especially because of the upcoming adoption of the AES algorithm by many IETF protocols.

As symmetric keys grow, they can be attacked by more processors without a change in processor technology since the memory requirements for breaking symmetric keys remain trivial. However, for the Number Field Sieve (NFS) algorithm, which is currently the most efficient method to break RSA keys, this is not true. Based on this premise, the "time and space" based RSA key size equivalents previously published in the RSA Labs Bulletin #13 of April 2000 by Robert Silverman (http://www.rsalabs.com/bulletins/) have recently been extended to cover all the AES symmetric key sizes in the latest draft of ANSI X9.44, which will eventually become the ANSI standard for RSA key transport:

Time and Space

Symmetric
Equivalent

Key Size
RSA Key Size

(in bits)
(in bits)

64
450

128
1620

192
2500

256
4200

These "time and space" based key sizes equivalents assume that both time and memory are binding constraints in order to break RSA keys. This same draft also indicates that beyond RSA key sizes of 768 bits one can no longer effectively utilize 32-bit processors with the NFS algorithm because the required memory exceeds what can be addressed in 32 bits; one is forced to use 64-bit machines. Beyond RSA key sizes of about 2500 bits, the memory requirements for the NFS algorithm exceed what can be addressed even on 64 bit machines.

For your information, here are also the estimated "time" only based RSA key size equivalents for solving the NFS problem from the same ANSI draft:

Time Only

Symmetric
Equivalent

Key Size
RSA Key Size

(in bits)
(in bits)

64
512

128
2550

192
6700

256
13500

Note that either of these sets of RSA key size equivalents could be used with Diffie-Hellman for solving the value of "p" since the NFS algorithm is also the most efficient method to break Diffie-Hellman algorithm today. Note also that these time only equivalents numbers are slightly smaller than those from ANSI X9.42 for Diffie-Hellman (i.e. 2550 vs 3072 for 128 bits, 6700 vs 7680 for 192 bits and 13500 vs 15360 for 256 bits) and the numbers in Hilarie Orman's Internet Draft (i.e. draft-orman-public-key-lengths-01.txt).

Shouldn't IETF standards mention these new "time and space" based key size equivalents in addition to existing "time" only based key size equivalents, and possibly even suggest that "time and space" based key size equivalents be used for RSA and Diffie-Hellman? Why mandate larger equivalent key sizes when smaller equivalent key sizes can probably suffice?

Food for thought!

Cheers,

Francois

___________________________________

Francois
Rousseau

Director of Standards and Conformance

Chrysalis-ITS

1688 Woodward
Drive

Ottawa, Ontario, CANADA, K2C 3R7

frousseau@chrysalis-its.com Tel. (613)
723-5076 ext. 419

http://www.chrysalis-its.com
Fax. (613) 723-5078

- Prev by Date:
**Re: Other IKE implementations with GSSAPI support?** - Next by Date:
**mobile IPv6 and IPsec ESP tunnels** - Prev by thread:
**New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman** - Next by thread:
**mobile IPv6 and IPsec ESP tunnels** - Index(es):