OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Fwd: New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman
From: Alex Alten (Altenhome.com)
Date: Thu Dec 14 2000 - 23:26:53 CST

I thought this might be of interest to the coderpunks community, it arrived
on several other security lists. The only thing that puzzles me is that
I would have thought a time-only RSA key could have been shorter than a
corresponding time-and-space RSA key (assuming that the time to crack is
equivalent to a key's strength).

- Alex

-----Original Message-----
From: FRousseauchrysalis-its.com [mailto:FRousseauchrysalis-its.com]
Sent: Wednesday, December 13, 2000 9:37 PM
To: IETF Transport Layer Security WG
Cc: ietf-pkiximc.org
Subject: [ietf-tls] New Time and Space Based Key Size Equivalents for RSA
and Diffie- Hellman

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
frousseauchrysalis-its.com Tel. (613) 723-5076 ext. 419
http://www.chrysalis-its.com Fax. (613) 723-5078 

--

Alex Alten

AltenHome.Com