how slow are 4Kbit RSA keys? [was: Re: multiple keys vs multiple identities]

[Daniel Kahn Gillmor]

On 09/24/2010 09:54 AM, David Shaw wrote:
> On Sep 24, 2010, at 8:15 AM, Vjaceslavs Klimovs wrote:
>> Is it good idea to create 4096 bit keys when creating new key pair? I
>> read through archives on this mailing list, and it seems there is no
>> real disadvantages of doing so.
> 
> It won't work with the current generation of OpenPGP smartcards.  It also 
> will be dreadfully slow if you (or someone you are communicating with) ever
> uses the key on a small machine (think smart phone).  If you are usually on
> a "full power" computer, then they generally have the CPU to spare for this
> sort of thing, and you'll rarely if ever notice a difference.

i'm curious to see some quantitative data about what "dreadfully slow"
means.

For starters, i tried verifying an SHA512-sum signature on a reasonable
size message (the text of a previous message in this thread), made with
a 4096-bit key.  The message itself is 1819 bytes, with --clearsign
attached it is 2696 bytes total.

I tested on two fairly low-powered machines:

a) ASUS eeePC900
   900Mhz intel celeron M CPU
   1GB DDR2 400MHz RAM

b) Linksys NSLU2 (de-underclocked)
   266Mhz ARM CPU (no FPU)
   32MB of RAM

Both are running reasonably up-to-date versions of debian squeeze, with
gpg 1.4.10.  The file i was verifying was already in the fs cache, so
disk contention wasn't an issue.  I verified the message from a
GNUPGHOME whose pubring contains a single key (my own) and no secret
keys, like this:

 mkdir -m 0700 testhome
 GNUPGHOME=testhome gpg --keyserver keys.gnupg.org --recv D21739E9
 cat > /dev/null < testfile
 time GNUPGHOME=testhome gpg --verify < testfile

on machine (a), the results were:

real	0m0.027s
user	0m0.020s
sys	0m0.004s

on machine (b) the results were:

real	0m0.154s
user	0m0.130s
sys	0m0.020s

I'd be curious to hear other people's results.

fwiw, 154ms doesn't seem "dreadfully slow" to me, given that my rtt ping
times to gnupg.org have a mean of 117ms.  and i don't know that many
smartphones are significantly underpowered compared to the NSLU2.

What *does* change the speed of such an operation is having a large
keyring.  If i import 866 keys from /usr/share/debian-keyring.gpg, then
remove my key from the keyring and re-append it to the end, verifying
the same file on machine (a) takes:

real    0m0.384s
user    0m0.307s
sys     0m0.075s

(more than 14x slower than the same hardware with one key in the public
keyring).  I didn't try this on machine (b) because of how long the
866-key import took on (a) (see the other thread from today).

My conclusion from the above data points is that if we're concerned
about computational inefficiencies, 4096-bit RSA keys are not
particularly bad offenders.

Are there other interpretations of the above results?  does anyone else
want to post comparable data points on different hardware?  How powerful
is a typical smartphone anyway?  What kind of a cutoff are people
willing to accept in terms of CPU cycles per signature validated?  or am
i measuring the wrong thing entirely?

	--dkg

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 900 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20100924/b374d193/attachment.pgp>