RSA 4096 ridiculous? (was RSA 1024 ridiculous)

[Henry Hertz Hobbit]

"Janusz A. Urbanowicz" <alex at bofh.net.pl> wrote:

On Sun, Jun 17, 2007 at 01:02:58PM -0500, Andrew Berg wrote:
> >
> > Atom Smasher wrote:
>> > > gpg does support RSA-2048/SHA-256 (or even RSA-4096/SHA-512)
>> > > which  is what i've been using for a while now. i'll sign
>> > > this email with RSA-2048/SHA-256 (my default on this key)
>> > > just to show what it looks like. it's a big signature block,
>> > > but not ridiculous and on a reasonably powerful computer
>> > > it's hardly a noticeable delay to work with such keys.
> > Try signing/encrypting files that are tens, hundreds, or thousands
> > of megabytes in size. Sure, your average machine can sign/encrypt
> > messages that don't even fill a cluster without breaking a sweat,
> > but if the sensitive data is large, RSA-4096 isn't a good choice
> > unless a gov't agency wants that data.
>
> Erm... when you use OpenPGP, or really any other modern crypto
> protocol, you don't put actual plaintext through RSA, RSA operates
> only on a hash or random session key for symmetric cipher.y

Let's put some actual sizes and times on this in a real world
situation.  BTW, I am in total agreement that 1024 bit keys will
be useful for at least a few more years whether they are DSA or
RSA.  It is more likely a crack will come from bad pass-phrases
or key loggers stealing good pass-phrases and stolen secret keys
than from shorter key sizes.

Responding most specifically to Andrew's objections, what is wrong
with 4096 bit RSA keys?  If they are so awful, then why does GnuPG
allow us to generate them? The default for RSA keys in both GnuPG
and PGP is 2048 bits anyway.  I created a temporary 4096 bit RSA
key and compared it to my present 1024 bit DSA key for detached
signing of moderately sized files which in addition to signed
email messages is all I need it for anyway. I have no need to sign
huge files.  On other hand, I occasionally need to encrypt huge
files, and even though I use something like TWOFISH or AES-256 for
the symmetric cipher, it takes me less time to encrypt the file
than it took me to tar it. It also takes me much less time to
encrypt the tarred file than it takes to do the final bzip2 of the
encrypted file.  But the real killer is the uploading of my file
to an Internet file storage server. That seems to take forever!
Download speed is significantly faster. But other than the slightly
longer time it took to create the RSA key, I didn't notice it took
any longer to sign the files and here are the actual sizes. I copied
the *.sig files to the extension names indicating which key was used
to sign it, but cp'd that to  $FILENAME.sig for the verifications:

109238  hosts.min
    65  hosts.min.1024D
   536  hosts.min.4096R

535610  hosts
    65  hosts.1024D
   536  hosts.4096R

 35435  proxy.txt
    65  proxy.txt.1024D
   536  proxy.txt.4096R

Here are the preferences on that RSA key:

Command> showpref
[ultimate] (1). Bogus User <bogususer at bogussite.com>
     Cipher: TWOFISH, AES256, AES192, AES, CAST5, 3DES
     Digest: SHA512, SHA384, SHA256, SHA1
     Compression: ZLIB, BZIP2, ZIP, Uncompressed
     Features: MDC, Keyserver no-modify

It took me infinitely longer to type the pass-phrase for the signing
than it took to actually create the sigs which seemed to be almost
instantaneous. Timing the signing is sort of ridiculous unless I used
keys without pass-phrases.  Here is the difference in the times of
verifying the file with both sigs (and I don't have a super fast
machine - the CPU is over three years old):

# 1024 BIT DSA KEY

$ time gpg --verify hosts.sig
gpg: Good signature from "Henry Hertz Hobbit <hhhobbit at securemecca.net>"
real    0m0.041s
user    0m0.037s
sys     0m0.003s

$ time gpg --verify proxy.txt.sig
gpg: Good signature from "Henry Hertz Hobbit <hhhobbit at securemecca.net>"
real    0m0.012s
user    0m0.008s
sys     0m0.004s

# 4096 BIT RSA KEY

$ time gpg --verify hosts.sig
gpg: Good signature from "Bogus User <bogususer at bogussite.com>"
real    0m0.042s
user    0m0.036s
sys     0m0.003s

$ time gpg --verify proxy.txt.sig
gpg: Good signature from "Bogus User <bogususer at bogussite.com>"
real    0m0.014s
user    0m0.007s
sys     0m0.006s

>From a user perspective, the time difference for verifying is
the same for both keys and in this case it is almost instantaneous.
The shortest file used in these test is longer than most email
messages unless you have lots of attachments. Although the signature
file is bigger for the 4096 bit RSA key (~ 8.25 times the size of
the 1024 bit DSA key) it is constant in size and 536 bytes isn't
unreasonable even if the message is only a few lines.  After all,
it verified the message, didn't it?  536 bytes to do that is a
small price to pay.  It is nice to do it with less, but that
size becomes more reasonable the bigger the message or file
becomes.

So the only relevant question as I see it is, can the Crypto Card
and other users handle my 4096 bit RSA sigs?  If they can't then
I will have some problems, won't I?  Correct me if I am wrong, but I
don't think I will have any problems with Crypto Card users in
using my SIGS. Interoperability is the key to usability here. You
people can tinker-toy with bigger key sizes than 4096, but I am
NOT going to modify the code to accommodate you.  The reason why
is I assume the people writing the code have picked those limits
for legitimate reasons.  I may be wrong on that but I am not going
to second guess them. In this case though, it doesn't appear the
limits were set because of inordinately larger times.  Less than
a tenth of second?  Whoop-de-doo!  Since they have given me the
option of using 4096 bit RSA keys, unless it poses usability
problems for other people, why can't I use them?  More to the
point, why shouldn't I use them?  Maybe it will allow me to keep
the keys just that little bit longer (assuming nobody compromises
them).

HHH