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
