From: "David F. Ogren" <ogren@cris.com>
Date: Tue, 9 Jul 1996 16:54:33 +0800
To: cypherpunks@toad.com
Subject: A case for 2560 bit keys
Message-ID: <199607090309.XAA00077@darius.cris.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

To: cypherpunks@toad.com
Date: Mon Jul 08 23:06:11 1996

Here is a few thoughts on RSA key sizes.  There is nothing new or 
revolutionary herein, but I think it does provide a good case for using 
large RSA keysizes.

Traditionally, we examine the threat model and determine the approximate 
ability of the attacker to factor secret keys.  Then a keylength is 
selected that exceeds the attackers ability to factor in a reasonable 
amount of time.

For example, if we assume that the NSA can factor any number with the speed 
of the special number sieve, and has 10^9 mips of computing power 
(doubling every 1.5 years) we can make the following estimations:_1_

Using these assumptions, the NSA could crack a 1024 bit key in ~11 days, a 
1536 bit key in 10 years and a 2048 bit key in 26 years.  _2_  Note that 
this would require the full resources of the NSA, however.  Thus, even the 
mighty resources of the NSA could only crack 42 1024 bit keys in 1996 
(including Moore's law). _3_, _4_

Similarly, a large corporation with 10^7 mips in computing power (and the 
same super-efficient factoring algorithm) could crack a 1024 bit key in 2 
years, a 1536 bit key in 20 years, and a 2048 bit key in 36 years.

My interpretation of these results: 1024 bit is probably safe for most 
reasonable threat models.  Only individuals with extremely high threat 
models should be concerned about 1024 bit keys in 1996.  Even those with 
extremely high threat models should be satisfied with 1536 bit keys.

Despite the above, there are convincing arguments for longer RSA keys.  
Instead of asking "Why should we have longer keys?", perhaps we should be 
asking "Why _shouldn't_ we have longer keys?"

In a hybrid cryptosystem such as PGP, very little of the computational 
process is consumed by RSA encryption.  Only a tiny fraction of the message 
is RSA encrypted (the session key), and thus the time-critical operation is 
the symmetric crypto system (IDEA for PGP).

As an experiment generate a 2047 bit PGP key and a 512 bit PGP key.  
Encrypt a file (preferably of a reasonable size) using both keys.  
Depending on the computer you are using, the time difference between the 
two keys will be a matter of few seconds or even a fraction of a second.

And so we have to ask ourselves, why _not_ use a 2047+ bit key.  It has 
greater longevity and greater security.  Why not be overcautious when 
the cost is so small?

It seems foolish that we use RSA keys that are less secure than our IDEA 
session keys.  Our RSA keys are much more valuable than our session keys.  
I will use my RSA key to encode hundreds of messages.  Each session key I 
will use only once.  An attacker who learns one of my IDEA session keys can 
decrypt only that message.  An attacker who learns my RSA key can decrypt 
any of my messages, past or present.  (He can also impersonate my 
signature, but that's another discussion entirely.)

If I send one message weekly that my attacker is interested in, and change 
my RSA key every two years, my RSA key is at least 104 times more valuable 
than any individual key.  Does it not make sense that the RSA key should 
ideally be 104 times more difficult to crack?

If increasing the RSA keylength was overly cumbersome to the process 
then designing the RSA keylength to meet minimum acceptable standards could 
be understood.  But since increased RSA keylengths are cheap in terms of 
computing power, would it not be better to pick RSA keylengths that are 
more secure than the session keys?

And thus, 2560 bit keys are not unreasonable.  They are not significantly 
slower to use (most of PGP's time is spent IDEA encrypting), and yet are 
effectively invulnerable. By "invulnerable" I mean that any attacker 
capable of cracking your RSA key would have an easier time hacking your 
individual IDEA session keys, and would never have any need to hack the RSA 
key itself.  And if you have threat models this severe you are a) 
hopelessly paranoid, b) SOL.

Footnotes:

_1_ These approximations of factoring difficulties and the computing 
resources are taken directly from Applied Cryptography by Bruce Schneier, 
page 161.

_2_ Taking into account Moore's law, the amount of processing power spent 
during a period of time is the integral of Power * 2^(t/1.5)dt (from 0 to 
x) = Power * 1.5 / (ln 2) 2 ^(t/1.5) (also evaluated from 0 to x).  Which 
is approximately equal to Power * 2.164 * (2^(x/1.5) - 1).  Thus in three 
years a corporation starting with 10^7 mips could produce 10^7 * 2.164 * 
(2^(3/1.5)-1) = 6.492 * 10^7 mips-years.

_3_ Any attempt to determine the computing power and cryptanalysis power of 
the NSA should be taken with a grain of salt.  There are several very 
critical and arbitrary assumptions made in order to obtain these numbers.

_4_ Additionally, any attempt to discern the future of cryptanalysis should 
also be taken with a grain of salt.  Who can tell what computers will like 
be in ten years?


- --
David F. Ogren                |
ogren@concentric.net          | "A man without religion is like a fish
PGP Key ID: 0x6458EB29        |  without a bicycle"
- ------------------------------|----------------------------------------
Don't know what PGP is?       | Need my public key?  It's available
Send a message to me with the | by server or by sending me a message
subject GETPGPINFO            | with the subject GETPGPKEY
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMeHMpOSLhCBkWOspAQH4gwf+NiP184ve2W06ClO92uEfjbaHpn3l9zAz
1ckt8PE8kMxkq8etcq/NM/IZ3QuTIBbeOr4ey6dIptQafmarb7sSMAx0KGgPALp8
v6a77as2RUCaJYjjviYlXh/0OIt+c7c+w9HbVZCmgpru/VQjT7++6eAa1f4K+225
K12wEX2TXou4s8+qYVUAT3B0iesuq/Z2iBzO942+v3u7rkCHLMghYlLIXR+SP43l
E15IQRez5nHkMb7VB9kL8ku/aDlXfKjURDQji8LBm+V+3i/9tcR/9+4EjKAqo1nB
qnXCFBKrzWRev4bbI9tbVnTc83VWeJRXGZxlpXhzc40kov7GbrT9Bg==
=B0h0
-----END PGP SIGNATURE-----