Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
RANDOM(4)	       BSD/i386	Kernel Interfaces Manual	     RANDOM(4)

     random, urandom --	random number devices

     This device gathers environmental noise from device drivers, etc.,	and
     returns good random numbers, suitable for cryptographic use.  Besides the
     obvious cryptographic uses, these numbers are also	good for seeding TCP
     sequence numbers, and other places	where it is desirable to have numbers
     which are not only	random,	but hard to predict by an attacker.

   Theory of operation
     Computers are very	predictable devices.  Hence it is extremely hard to
     produce truly random numbers on a computer	-- as opposed to pseudo-random
     numbers, which can	easily generated by using a algorithm.	Unfortunately,
     it	is very	easy for attackers to guess the	sequence of pseudo-random num-
     ber generators, and for some applications this is not acceptable.	So in-
     stead, we must try	to gather "environmental noise"	from the computer's
     environment, which	must be	hard for outside attackers to observe, and use
     that to generate random numbers.  In a Unix environment, this is best
     done from inside the kernel.

     Sources of	randomness from	the environment	include	inter-keyboard tim-
     ings, inter-interrupt timings from	some interrupts, and other events
     which are both (a)	non-deterministic and (b) hard for an outside observer
     to	measure.  Randomness from these	sources	are added to an	"entropy
     pool", which is periodically mixed	using the MD5 compression function in
     CBC mode.	As random bytes	are mixed into the entropy pool, the routines
     keep an estimate of how many bits of randomness have been stored into the
     random number generator's internal	state.

     When random bytes are desired, they are obtained by taking	the MD5	hash
     of	a counter plus the contents of the "entropy pool".  The	reason for the
     MD5 hash is so that we can	avoid exposing the internal state of random
     number generator.	Although the MD5 hash does protect the pool, each ran-
     dom byte which is generated from the pool reveals some information	which
     was derived from the internal state, and thus increases the amount	of in-
     formation an outside attacker has available to try	to make	some guesses
     about the random number generator's internal state.  For this reason, the
     routine decreases its internal estimate of	how many bits of "true random-
     ness" are contained in the	entropy	pool as	it outputs random numbers.

     If	this estimate goes to zero, the	routine	can still generate random num-
     bers; however it may now be possible for an attacker to analyze the out-
     put of the	random number generator, and the MD5 algorithm,	and thus have
     some success in guessing the output of the	routine.  Phil Karn (who de-
     vised this	mechanism of using MD5 plus a counter to extract random	num-
     bers from an entropy pool)	calls this "practical randomness", since in
     the worse case this is equivalent to hashing MD5 with a counter and an
     undisclosed secret.  If MD5 is a strong cryptographic hash, this should
     be	fairly resistant to attack.

   Exported interfaces -- output
     There are three exported interfaces; the first is one designed to be used
     from within the kernel:

     void get_random_bytes(void	*buf, int nbytes);

     This interface will return	the requested number of	random bytes, and
     place it in the requested buffer.

     The two other interfaces are two character	devices	/dev/random and
     /dev/urandom. /dev/random is suitable for use when	very high quality ran-
     domness is	desired	(for example, for key generation.), as it will only
     return a maximum of the number of bits of randomness (as estimated	by the
     random number generator) contained	in the entropy pool.

     The /dev/urandom device does not have this	limit, and will	return as many
     bytes as are requested.  As more and more random bytes are	requested
     without giving time for the entropy pool to recharge, this	will result in
     lower quality random numbers.  For	many applications, however, this is

   Exported interfaces -- input
     The two current exported interfaces for gathering environmental noise
     from the devices are:

     void add_keyboard_randomness(unsigned char	scancode);
     void add_interrupt_randomness(int irq);

     The first function	uses the inter-keypress	timing,	as well	as the scan-
     code as random inputs into	the "entropy pool".

     The second	function uses the inter-interrupt timing as random inputs to
     the entropy pool.	Note that not all interrupts are good sources of ran-
     domness!  For example, the	timer interrupts is not	a good choice, because
     the periodicity of	the interrupts is too regular, and hence predictable
     to	an attacker.  Disk interrupts are a better measure, since the timing
     of	the disk interrupts are	more unpredictable.  The routines try to esti-
     mate how many bits	of randomness a	particular interrupt channel offers,
     by	keeping	track of the first and second order deltas in the interrupt

     The original core code was	written	by Theodore Ts'o, and was intended for
     the Linux platform. This was ported to FreeBSD by Mark Murray, who	also
     wrote the rndcontrol utility.

     Ideas for constructing this random	number generator were derived from the
     Pretty Good Privacy's random number generator, and	from private discus-
     sions with	Phil Karn.  This design	has been further modified by myself,
     so	any flaws are solely my	responsibility,	and should not be attributed
     to	the authors of PGP or to Phil.

     The code for MD5 transform	was taken from Colin Plumb's implementation,
     which has been placed in the public domain.  The MD5 cryptographic	check-
     sum was devised by	Ronald Rivest, and is documented in RFC	1321, "The MD5
     Message Digest Algorithm".

     Further background	information on this topic may be obtained from RFC
     1750, "Randomness Recommendations for Security", by Donald	Eastlake,
     Steve Crocker, and	Jeff Schiller.



     The random, urandom files appeared	in FreeBSD 2.1.5.

BSD			       October 21, 1995				   BSD


Want to link to this manual page? Use this URL:

home | help