[gnupg-devel] Re: True RNG and GnuPG / libgcrypt

Nelson H. F. Beebe beebe at math.utah.edu
Thu Oct 3 01:30:28 CEST 2013

Matthias-Christian Ott <ott at mirix.org> responds on Wed, 02 Oct 2013
21:54:12 +0200 to an earlier question about possible direct-access
to random-number-producing devices:

>> ...
>> If you want to use the output of the random number generator directly
>> you should somehow know how much true randomness per bit of output it
>> yields. Feeding the output of the random number generator into
>> /dev/random has the advantage that it gets mixed with other sources of
>> randomness and that there is a single implementation that can be
>> peer-reviewed.
>> ...

That is definitely good advice.  

However, it is important to remember a distinction between the
/dev/urandom and /dev/random device interfaces available on some
flavors of Unix:

	Both produce random streams of bits, but /dev/urandom
	generally continues to produce output for every read, whereas
	/dev/random may block until the interface believes that enough
	additional entropy has been collected to produce more random

That means that reading /dev/random makes you susceptible to
denial-of-service attacks that could be as simple as this:

	dd ibs=10240 count=1 < /dev/urandom > /dev/null

I just tried that on one of my GNU/Linux servers and had the process
hang for tens of seconds; changing it to read from /dev/urandom
instead produced 10KB of data in 2 msec.  I then increased the count
from 1 to 10240, and pulled from /dev/urandom 100MB of random data in
6 to 20 seconds on a half-dozen different servers.

If you have a single-user single-process machine, you might be immune
to such attacks, but change either, or both, qualifiers "single-" to
"multi-", and you could be a victim, even if the other consumer(s) of
random bits from /dev/random are just trying to get data for their own
use, rather than intentionally trying to deny YOU access to the

If you are concerned about possible bias from a random-number
generating device, here is an old technique that can fix it:

	Assume that the device is biased, but that the bias is
	CONSTANT.  Then, it produces a 0-bit with probability p, and a
	1-bit with probability 1 - p.  Take two successive bits, and
	look at the four possible outcomes:

		0 0	prob. = p * p = p^2
		0 1	prob. = p(1 - p)
		1 0	prob. = (1 - p)p = p(1 - p)
		1 1	prob. = (1 - p)^2

	The cases 0 0 and 1 1 have different probabilities (unless p =
	1/2, but that is not possible because we said the generator is
	biased), so discard pairs of identical bits.

	The cases 0 1 and 1 0 have equal probability, so choose the
	second bit of each input pair where the two bits differ, and
	otherwise read a second pair of bits and retry.  Assemble the
	chosen bits into an output stream.  That stream contains 0 and
	1 bits, each with equal probability.

If p is near 1/2, then you consume about 8 bits for every 2 bits
output, so your efficiency is only 0.25, and you have additional
software overhead of working at the bit-level with shifting and
counting, instead of at the higher level of random bytes and words.
As p tends to either 0 or 1, the efficiency tends to 0.

Of course, there could still be a problem, if the generator perversely
gets stuck in a mode where it produces, perhaps only for certain time
intervals, long sequences of alternating bits: 0 1 0 1 0 1 ....: your
resampling according to the above algorithm then produces either 0 0 0
0 ... or 1 1 1 1 ..., sequences that are probably not what you

Issues like that are why random-number device drivers try to mix
things up further, by arranging for multiple input sources, periodic
remixing of those sources, hashing or other digital-signature
algorithms, and so on.

For more on that general problem, see the extensive bibliography of
more than 3500 publications on generating, testing, and sampling of
pseudorandom numbers at


The two URLs look almost identical in a browser, but the second has
live hyperlinks, and the first is needed by BibTeX and associated
bibliographic software.

- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -

More information about the Gnupg-devel mailing list