Lucky Green wrote:
>
> [Written originally in response to a post on Cryptography. --Lucky]
>
> 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.
OpenSSL allows you to specificy acceptable ciphersuites, and this does,
in fact, consitute a check on size both on the PK and the symmetric
cipher (and if it isn't working, I'd like to know!).
> 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. :-)
Actually, ISTR its impossible to generate a certificate request below
some size in the hundreds of bits (I forget exactly what, but there's
some bit of stuff that has to be asymmetrically crypted that is that
long).
> 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.
Coo. Do you have more details on what optimisations these might be,
because clearly the test:
if(keysize > 1024)
optimise_this_way();
else
optimise_that_way();
is exceedingly cheap. And one I'd be happy to add to OpenSSL.
> 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.
Numbers like "a couple of seconds" would kill HTTPS stone dead, of
course.
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
