gpg key generation on Tails live cd - why so quick?

Question

I just used gpg2 --gen-key to generate a 2048 bit RSA key pair on an OS running on a live cd (Tails). This happened much faster than I expected. When I have done this before on a regular machine it takes a bit of time, and I typically need to wait and briefly do something else. I think that is because it takes some time to generate the required amount of randomness.

Does a live cd have some unusual process such that the boot process generates more than normal randomness? Or is it possible that it is using /dev/urandom instead? As far as I was aware, gpg uses /dev/random which is why it can take some time to generate keys.

Answer 1

Entropy (“randomness”) is accumulated in the kernel. If the kernel has accumulated enough entropy before GPG starts, GPG benefits from it immediately.

Linux's handling of entropy is somewhat broken. Linux has two devices: /dev/random and /dev/urandom. /dev/random blocks for as long as it takes to accumulate sufficient entropy. /dev/urandom always returns data without blocking. In principle, this would be a good thing. The problem is that Linux's entropy calculation is extremely conservative: it assumes that entropy gets used up, which is only true in a highly theoretical sense. So /dev/random tends to block when it shouldn't.

On a normal system, you should just use /dev/urandom — though some software, including gpg, doesn't give you a choice. However, on a live CD, immediately after boot, there may be very little entropy, unless your computer has a hardware RNG (such as the RdRand instruction on recent Intel processors) and Linux supports it. So in this case you do need to use /dev/random and wait if necessary. User interaction (e.g. moving the mouse) will contribute to this entropy.

See also Adding "random number entropy" for GPG keys? and Can you explain the entropy estimate used in random.c

Again, you don't need to worry: GPG+Linux is very conservative when it comes to estimating entropy. If GPG generates a key quickly, either you've already interacted enough with the computer to provide enough entropy, or your computer has a supported hardware RNG.

Answer 2

I found the answer: Tails comes packaged with the random number generator 'haveged'. http://www.reddit.com/r/tails/comments/2oxr7n/how_does_tails_generate_gpg_keys_so_fast/

I have edited the question's title to reflect that this is particular to Tails.

Here is some discussion of whether the HAVEGED algorithm is any good: https://crypto.stackexchange.com/questions/8083/quality-of-randomness-on-a-linux-system-with-haveged

The conservative approach taken by gpg in using /dev/random may be overkill in many situations, compared with using /dev/urandom but from the specific point of view of a live CD environment used for gpg key generation without time constraints, using haveged seems unnecessary.

So it seems to me the simplest solution is to kill the haveged process in Tails, wait for /proc/sys/kernel/random/entropy_avail to deplete, and then let gpg just do what it normally does.

Answer 3

First, the difference between /dev/urandom and /dev/random is that /dev/random will block until there is enough entropy to generate a random number, whereas /dev/urandom doesn't block when entropy is exhausted. This also means that the generation on a /dev/urandom application can be less random than a number from /dev/random.

To your questions, the runtime for generating secrets varies based on the available entropy in the system and how lucky you are to get two primes quickly (without exhausting the entropy pool).

If you consistently get a keypair generated quickly on Tails, there is probably something wrong with the implementation.