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

[Nelson H. F. Beebe]

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
	bits.

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
device.

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
expected.

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

	http://www.math.utah.edu/pub/tex/bib/prng.bib
	http://www.math.utah.edu/pub/tex/bib/prng.html

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/ -
-------------------------------------------------------------------------------