Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]

[Lucky Green]

Enzo wrote:
> Further to Lucky's comments: in the last few days I have 
> discussed keysize issues with a few people on a couple of 
> mailing lists, and I have encountered a hostility to large 
> keysizes of which, frankly, I don't understand the reasons. 
> On the client side at least, performance is not an
> issue: PGP 7.0.3 with my new 4096-bit PGP key appears to be 
> as snappy as it was with 1024-bit keys, and the table at 
> http://www.mccune.cc/PGPpage2.htm#Speed looks > quite 
> reassuring.
> 
> In particular, none of the naysayers explained me clearly why 
> it should be reasonable to use 256-bit ciphers like AES with 
> 1024-bit PK keypairs.

Allow me to shed at least some light on the strange phenomenon that you
experienced for I have experienced the same phenomenon and was able to
glean at least a few of the reasons why application authors and
maintainers have proven so reluctant to increase RSA key sizes or
mandate minimum key sizes in their applications.

1) Very, very few applications, and no cryptographic libraries that I am
aware of, that currently employ RSA perform any kind of sanity check on
the size of the keys. The current release version of various programs
that I looked at will happily accept a 4-bit RSA client key that anyone
could factor in their head. VeriSign not too long ago signed a 384-bit
SSL server key that may readers of this list could break with the old
computers in their home. Such certificate signing practices, or their
lack thereof, are nothing short of irresponsible.

I have not tested the following hypothesis and am not willing to spend
the required $125 on the experiment, but I would not be in the least
surprised if many public CA's would readily sign a certificate for a
4-bit RSA key. C.f. the "being caught with one's pants down" observation
in my previous post. If somebody want to perform this experiment, better
do it quick, since the CA vendors read this mailing list. :-)

There are some positive examples: as a result of my original post, the
next release version of OpenSSH will enforce a 768-bit minimum size on
the key. I have not been following the discussion that lead to the
determination of this figure and therefore  don't know on which
cryptological results the OpenSSH designers based that number.

However, I note that even those experts that I am aware of which assert
that 1024-bit keys are sufficient for the type of long-term use SSH
client keys are frequently employed for do not appear to claim that
768-bit keys should be considered secure today.

Unfortunately, the OpenSSH designers have chosen to not expose the
minimum key size requirement via the sshd configuration file, though at
least there now there will be a known spot in the source that can easily
be patched to a value the server operator might consider to be more in
line with current key size recommendations. I thank the OpenSSH team for
at least providing an easy hook to make the desired changes in the
source, though of course I would like to see both a larger default and a
corresponding option in the config file. Still, hats off to the OpenSSH
team for moving implementing sanity checks that few other vendors have
bothered to implement.

Some other deployed applications either use libraries that can't go
higher than 1024-bits or have the key sizes and structures hard coded
all over the source, making a chance expensive and uneconomical absent
severe customer pressure on the vendor. A much cheaper solution than
rewriting good chunks of the core crypto processing code (or worse,
having to upgrade hardware that is limited to 1024-bits) is putting out
a press release stating why the customer doesn't need keys larger than
1024-bits, which some claim is one of the many reason why there is so
much resistance to moving to larger keys. I am not quite ready to
subscribe to such cynical a view point, but I heard that view point
voiced by several crypto old-timers in private conversations more than
once.

2) One frequently voiced argument against increasing key sizes is the
resultant decrease in performance. Yes, it is absolutely true that
increasing the size of an RSA key leads to a decrease in performance.
However, larger keys decrease performance less than naive experiments
may seem to indicate. For many applications, generating a 2048-bit key
and comparing the performance with that of a 1024-bit key will lead to
numbers that differ widely, much more so than can be attributed to the
larger key size. 

The reason for this phenomenon is that RSA algorithm performance is
highly dependent on optimizations that are both key size and processor
specific. The same optimization strategy that will give you blazingly
fast performance with a 1024-bit key will absolute kill performance with
a 4096-bit key, for which a different optimization strategy is needed.
Similarly, optimizations are highly processor specific. An optimization
designed specifically for a Pentium III processor will run slower on a
Pentium IV than your basic Pentium optimized code would.

Some applications offer the correct optimizations for each key size.
Others just optimize for 1024-bit keys, thus leading to abysmal
performance with some larger keys.

Example: PGP appears to offer excellent performance optimizations across
all key sizes. The performance difference between a 1024-bit RSA key and
a 4096-bit key can't be much more than a second. (I didn't directly time
this, but I can hear when the outgoing mail from my laptop hits the mail
spool on my SMTP server; the increase in lag is insignificant from a
user perspective).

OpenSSH with 4096-bit keys on both ends on a 450 and 333 MHz machine
respectively is noticeably slower than with 1024-bit keys, perhaps by a
couple of seconds, but still well within user tolerance. I suspect
additional optimizations are possible which would decrease the lag
further.

PuTTY SSH, on a 750MHz CPU with a 4096-bit key on both sides simply
crawls. I am looking at some 12+ seconds before I see the shell prompt
from the same 333MHz server used in the example above. Apparently,
optimizations for larger keys are missing from this program.

In summary, I would like to see more applications that are currently
utilizing RSA to enforce sanity checks on the keys with reasonable
defaults, offer the administrator a choice to change these defaults via
a configuration option that doesn't require patching the source, and see
more applications that use RSA processing code to utilize key
size-specific optimizations, which would significantly decrease the
currently experienced performance differences with many of those
applications.

--Lucky


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com