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 [EMAIL PROTECTED]