7

When I generate RSA key for ssh (both server-side and client-side):

dpkg-reconfigure openssh-server
ssh-keygen

the key generation is completed instantly. However, when I generate RSA key for gpg, the key generation takes several minutes and I have to generate entropy by typing on the keyboard or reading/writing to the disk:

gpg --key-gen

I am wondering what makes this difference, and whether the quality of the generated keys is the same (for the same key size). Has anybody anything to say about this?

as a side-note:

I remember vaguely, there was a Debian OpenSSH Vulnerability which affected the seeding of the random number generator. IIRC, the entropy for the key came from two sources:

1) using uninitialized memory
2) using the Process ID (PID)

This bug was caused by commenting out (1), leaving the PID as the only source of entropy. Consequently, the space of possible keys was only 2^16.

Is openssh really using only these two sources of entropy? No /dev/random ?

  • You might want to take a look at haveged, which speeds up GPG key creation. – Karol Babioch Mar 19 '15 at 14:13
3

The difference comes from the locking/nonlocking random beeing used (e.a. /dev/random and /dev/urandom) from the man-pages of ubuntu 14.04 (man random):

NAME:      random, urandom - kernel random number source devices

SYNOPSIS : #include <linux/random.h>
           int ioctl(fd, RNDrequest, param);

DESCRIPTION :
 The  character  special files /dev/random and /dev/urandom 
 (present since Linux 1.3.30) provide an interface to the kernel's random number    
 generator. 
 File /dev/random has major device number 1 and minor device number 8. 
 File /dev/urandom has major device number 1 and minor device number 9.

 The random number generator gathers environmental noise from device drivers and  
 other sources into an entropy pool.  The generator also keeps  an  estimate
 of the number of bits of noise in the entropy pool.  From this entropy pool random 
 numbers are created.

 When  read,  the  /dev/random device will only return random bytes within the 
 estimated number of bits of noise in the entropy pool.  /dev/random should be
 suitable for uses that need very high quality randomness such as one-time pad or 
 key generation.  When the entropy pool is empty,  reads  from  /dev/random
 will block until additional environmental noise is gathered.

 A  read  from  the  /dev/urandom  device will not block waiting for more entropy.  
 As a result, if there is not sufficient entropy in the entropy pool, the
 returned values are theoretically vulnerable to a cryptographic attack on the  
 algorithms used by the driver.  Knowledge of how to do this is not  available
 in  the  current  unclassified  literature,  but it is theoretically possible that 
 such an attack may exist.  If this is a concern in your application, use 
 /dev/random instead.

 Writing to /dev/random or /dev/urandom will update the entropy pool with the data 
 written, but this will not result in a higher entropy count.  This  means
 that it will impact the contents read from both files, but it will not make reads   
 from /dev/random faster.

Usage :
 If  you  are  unsure  about  whether you should use /dev/random or /dev/urandom,  
 then probably you want to use the latter.  As a general rule, /dev/urandom
 should be used for everything except long-lived GPG/SSL/SSH keys.

This means that openssh will use the /dev/urandom special file, and gpg --key-gen uses the /dev/random. the GPG will lock when entropy is 'drained' until enough entropy is added, resulting in proven entropy being used, urandom rehashes its entropy pool all the time. That means it does not run out of entropy like /dev/random does. and it does this to have a known 'real'-entropy level for the random numbers. and not rely upon the entropy of the /dev/urandom.

  • in that case, the answer to my question is "No, the quality of the generated keys is not the same". Do you agree ? – Michael Boies Mar 19 '15 at 12:56
  • its not that easy to conclude that. I used to think that that was the case, but recently I learned that the entropy and its poolsize are not that telling about how random it is. /dev/urandom is not of less quality of /dev/random unless in special edge-cases. (like within 1 minute post boot, and after more than [par example] 500 Mb have been read from the entropy pool within a minute for the last 10 minutes). its hard to say 1 is of less quality of the other. what I can say is that GPG has a known entropy for key generation and the other doesn't.(so its unknown) – LvB Mar 19 '15 at 13:02
  • OK, I see it's more complicated than I thought. But still, if /dev/random has known (high) entropy, and /dev/urandom has unknown entropy, than I would rather use /dev/random for long-time-key generation (even if that takes several minutes longer) – Michael Boies Mar 19 '15 at 13:21
  • because it is not proven that "low" entropy yields worse results. and also on servers the sources for entropy are quite limited. (no GUI or Keyboard/mouse input, no soundcard and often even no GPU). s the openssh keygen (widch is jused on servers a lot) can not rely upon the /dev/random for having enough bits available for sustained key generation. (SSL for HTTPS/SMTPS/POPS/IMAPS also needs entropy to work savely, as does the SSH-server. thats a lot of programs with many connection for almot no entropy input.) so several minutes could infact be several days for a strong keyset. – LvB Mar 19 '15 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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