Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

RSA 2048 keypair generation: via openssl 0.5s via gpg 30s, why the difference There are several programs which can gerate RSA public/private keypairs

GnuPG/OpenPGP for instance has a wizzard being envoked via

gpg --gen-key

OpenSSL can generate a keypair using theses command lines

openssl genrsa -out testkey.private 2048
openssl rsa -in testkey.private -pubout -out testkey.public

for the very same thing, that is generating a keypair RSA 2048 bit I can perceive -on the very same machine- very different times.

openssl generates a keypair in about 0.5s
gpg takes about 30 and even adverts "move mouse to generate randomness/ entropy"

Can the difference be explained? I know that gpg does some littel more then just the RSA key creation, yet I do specifically choose option (4)

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection?

Therefore really the only thing generated is a 2048bit RSA keypair. Yet the time difference is strinking 30 seconds?

To me it seems that either gpg is wasting needlessly time or OpenSSL is not waiting enough time and hence creates insecure keys.

My question is what could explain the difference?

Update

The RSA creating must take as an input some randomness. Hence to make certain that the speedy openssl is not simply the result of using some stored up randomness I batchrun it several time

time bash -c "for i in {1..50}; do  openssl genrsa -out /dev/null 2048 ;  done;"

which yields

real    0m16.577s
user    0m16.309s
sys 0m0.092s

which is that for 50 2048bits RSA keys (I assume need a lot of entropy/randomness) openssl still only needed 16 seconds. My assumption here would hence be the "answer" that openssl must be broken. After all I am distrustful my Linux (a 3.2.0-59 kernel) has become so great in generating randomness.

Maybe the difference is simply that openssl uses /dev/urandom and gpg uses /dev/random which if true could explain the time difference my problem is that I do not know how I would find out about this, to verify this.

update2

To test the source of openssl's random I used

strace -xe trace=file,read,write,close openssl genrsa -out testkey5.private 2048 2>&1 | grep random -A1

which yields

open("/dev/urandom", O_RDONLY|O_NOCTTY|O_NONBLOCK) = 4
read(4, "\x21\xd8\xaa\xf1\x2b\x5f\x4a\x89\x5d\x6c\x58\x82\xc1\x88\x21\x04\xfa\x5b\x18\x98\x8a\x34\x2b\xe3\xf3\xc0\xb1\xef\xfb\x44\x15\x09", 32) = 32

so it seems that 32 bytes from /dev/urandom (not the "better" /dev/random) is enough for th 2048bit RSA keypair in openssl. Therefore it is so fast!

Measurements

2048bit RSA keypair generation means

  • 32 bytes of only /dev/urandom (using openssl)
  • 300 bytes of dev/random (using openPGP GNU Privacy Guard)

this explains of course the time difference!

share|improve this question

2 Answers 2

GnuPG consumes several bytes from /dev/random for each random byte it actually uses. You can easily check that with this command:

start cmd:> strace -e trace=open,read gpg --armor --gen-random 2 16 2>&1 | tail
open("/etc/gcrypt/rngseed", O_RDONLY)   = -1 ENOENT (No such file or directory)
open("/dev/urandom", O_RDONLY)          = 3
read(3, "\\\224F\33p\314j\235\7\200F9\306V\3108", 16) = 16
open("/dev/random", O_RDONLY)           = 4
read(4, "/\311\342\377...265\213I"..., 300) = 128
read(4, "\325\3\2161+1...302@\202"..., 172) = 128
read(4, "\5[\372l\16?\...6iY\363z"..., 44) = 44
open("/home/hl/.gnupg/random_seed", O_WRONLY|O_CREAT, 0600) = 5
cCVg2XuvdjzYiV0RE1uzGQ==
+++ exited with 0 +++

In order to output 16 bytes of high-quality entropy GnuPG reads 300 bytes from /dev/random.

This is explained here: Random-Number Subsystem Architecture

Linux stores a maximum of 4096 bytes (see cat /proc/sys/kernel/random/poolsize) of entropy. If a process needs more than available (see cat /proc/sys/kernel/random/entropy_avail) then the CPU usage becomes more or less irrelevant as the feeding speed of the kernel's entropy pool becomes the relevant factor.

share|improve this answer
    
Impressive. Thank you for the insight. I think it pretty much enlightens with regard to the question! So it seems while openssl is satisfied with 32bytes of less quality /dev/urandom gpg even says "1 byte /dev/random is not good enough for 1 byte of random". Would this not mean that openssl keys are more prone to "too little randomness" compared to gpg's? –  humanityANDpeace Mar 16 at 15:46
1  
@humanityANDpeace Randomness is an endless discussion. Not long ago the "master user" of this site made the claim that /dev/urandom was good enough for crypto purposes. On the GnuPG mailinglist he would probably get laughed at for that. AFAIK it is impossible to prove that certain data is purely random. You can find non-randomness but only where you look for exactly that pattern. –  Hauke Laging Mar 16 at 15:52
    
yes I see:) Still the fact that gpg uses 300bytes of /dev/random while openssl uses only 32bytes of /dev/urandom seems to suggest potential security risk for the cautious user how wants a 2048bit RSA keypair. I would hence opt for gpg. 32bytes seems awefully little –  humanityANDpeace Mar 16 at 16:07
1  
@HaukeLaging The “master user” of this site got this advice from the “master user” of Information Security and Cryptography, with an explanation that makes sense (unlike Linux's entropy pool size computation, which doesn't). Is a rand from /dev/urandom secure for a login key? “The short answer is yes. The long answer is also yes.” –  Gilles Mar 16 at 18:14
1  
32 bytes read from a well seeded CSPRNG gives 256 bits of security (which is a damn lot). An RSA-2048 bit key only offers about 112 bits of security. The only dubious property of a /dev/urandom is that (on linux) it doesn't block before it's seeded directly after booting. Once it has been seeded it will remain secure forever. –  CodesInChaos Mar 16 at 20:54

Your suggestion that this difference is because openssl uses /dev/urandom and gpg uses /dev/random is correct.

You can watch the available entropy going down while generating keys with gpg using:

watch -n 1 cat /proc/sys/kernel/random/entropy_avail

I used a program for generating the description of the steps for setting up a OpenGPG smart card with gpg, so I had to run gpg multiple times until that all worked out as intended. After the initial runs I noticed that /dev/random would not have enough entropy and gpg would just stall waiting for new entropy to be accumulated.

I wrote a small program to provide extra non-random data, and when doing so gpg would not "halt" but generate the keys almost immediately: nice for testing the script to run correctly, but of course not something you should do while generating your real keys.

The program to speed up gpg (do not use in real situations):

# For testing purposes only 
# DO NOT USE THIS, tHIS DOES NOT PROVIDE ENTROPY TO /dev/random

import fcntl
import time
import struct

RNDADDENTROPY=0x40085203

while True:
    random = "3420348024823049823-984230942049832423l4j2l42j"
    t = struct.pack("ii32s", 8, 32, random)
    with open("/dev/random", mode='wb') as fp:
        # as fp has a method fileno(), you can pass it to ioctl
        res = fcntl.ioctl(fp, RNDADDENTROPY, t)
        time.sleep(0.001)

When I run this while watching entropy_avail I can see the available entropy go up to over 3800.

share|improve this answer
    
Thanks for the answer. I am still looking forward to test gpg, which unfortunatelly is less batchable and more interactive. .. Still. Are you sure the repeatet call of cat by itself does not already drain entropy? Do you have some evidence or source that tells gpg uses /dev/random that would perfectionate the answer? Lastly does that also mean that openssl generates lesser quality RSA-keypairs then gqg? –  humanityANDpeace Mar 16 at 15:42
    
@humanityANDpeace It is possible (though less obvious) to use GnuPG in batch mode. Search for Unattended key generation in the file /usr/share/doc/packages/gpg2/DETAILS (or whatever it may be in your distro). The /dev/random evidence is in my answer. –  Hauke Laging Mar 16 at 15:46
    
thanks! I will read through that –  humanityANDpeace Mar 16 at 15:47
    
@humanityANDpeace Hauke's answer is more to the spot, but I found several references to it while researching how to setup my OpenGPG card. Batching is non-trivial, but the python program I have used I have made available on bitbucket –  Anthon Mar 16 at 15:48
1  
Spawning a new process consumes entropy, therefore a better approach would be using the read shell builtin: while read -r < /proc/sys/kernel/random/entropy_avail; do clear; date; printf '\nAvailable entropy: %s bytes\n' "$REPLY"; sleep 1; done –  nyuszika7h Mar 16 at 22:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.