Difference between revisions of "Random number generation"

From ArchWiki
Jump to: navigation, search
(move text unchanged)
(update link(s) (avoid redirect))
(13 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
:A random number generator (RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random.
 
:A random number generator (RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random.
  
Generation of random data is crucial for several applications like making cryptographic keys (e.g. for [[Disk Encryption]]), [[Securely wipe disk|securely wiping disks]], running encrypted [[Software Access Point]]s.
+
Generation of random data is crucial for several applications like making cryptographic keys (e.g. for [[Disk Encryption]]), [[Securely wipe disk|securely wiping disks]], running encrypted [[Software access point]]s.
 
+
Apart from the applications discussed above there are others that depend on enough entropy being available, e.g. using the system as a wifi access point with encryption.  
+
  
 
== Kernel built-in RNG ==
 
== Kernel built-in RNG ==
The kernel build in RNG's [[random|/dev/{,u}random]] are highly recommended for producing reliable random data providing the same security level that is used for the creation of cryptographic keys. The random number generator gathers environmental noise from device drivers and other sources into an entropy pool.
+
The Linux kernel's built-in RNGs [[wikipedia:/dev/random|/dev/{u}random]] are highly commended for producing reliable random data providing the same security level that is used for the creation of cryptographic keys. The random number generator gathers environmental noise from device drivers and other sources into an entropy pool.
  
The {{ic|man random}} command will misdirect to the library function manpage [http://man7.org/linux/man-pages/man3/random.3.html random(3)]
+
Note that the {{ic|man random}} command will misdirect to the library function manpage [http://man7.org/linux/man-pages/man3/random.3.html random(3)]
while for information about the /dev/random device files you should run {{ic|man 4 random}} to read [http://man7.org/linux/man-pages/man4/random.4.html random(4)].
+
while for information about the {{ic|/dev/random}} device files you should run {{ic|man 4 random}} to read [http://man7.org/linux/man-pages/man4/random.4.html random(4)].
  
 
=== /dev/random ===
 
=== /dev/random ===
; /dev/random: uses an entropy pool of 4096 bits (512 Bytes) to generate random data and stops when the pool is exhausted until it get's (slowly) refilled. /dev/random is absolutely not designed for wiping entire HDD's, but rather to generate cryptographic keys (e.g. SSL/SSH).  
+
{{ic|/dev/random}} uses an entropy pool of 4096 bits (512 Bytes) to generate random data and stops when the pool is exhausted until it gets (slowly) refilled. {{ic|/dev/random}} is designed for generating cryptographic keys (e.g. SSL, SSH, dm-crypt's LUKS), but it is impractical to use for wiping current HDD capacities: what makes disk wiping take so long is waiting for the system to [[Wikipedia:Hardware_random_number_generator#Using_observed_events|gather enough true entropy]]. In an entropy-starved situation (e.g. a remote server) this might never end. While doing search operations on large directories or moving the mouse in X can slowly refill the entropy pool, it's designated pool size alone will be indication enough of the inadequacy for wiping a disk.  
  
The Kernel built-in RNG [[Wikipedia:/dev/random|/dev/random]] provides you the same quality random data you would use for keygeneration, but can be nearly impractical to use at least for wiping current HDD capacitys.
+
You can always compare {{ic|/proc/sys/kernel/random/entropy_avail}} against {{ic|/proc/sys/kernel/random/poolsize}} to keep an eye on the system's entropy pool.
What makes disk wiping take so long with is to wait for it to [[Wikipedia:Hardware_random_number_generator#Using_observed_events|gather enough true entropy]].
+
In an entropy starved situation (e.g. remote server) this might never end while doing search operations on large directories or moving the mouse in X can slowly refill the entropy pool.
+
  
You can always compare {{ic|/proc/sys/kernel/random/entropy_avail}} against {{ic|/proc/sys/kernel/random/poolsize}} to keep an eye on your entropy pool.
+
While Linux kernel 2.4 did have writable {{ic|/proc}} entries for controlling the entropy pool size, in newer kernels only {{ic|read_wakeup_threshold}} and {{ic|write_wakeup_threshold}} are writable. The pool size is now hardcoded in kernel line 275 of {{ic|/drivers/char/random.c}}:
 
+
One can compare the actual available entropy {{ic|/proc/sys/kernel/random/entropy_avail}} against {{ic|/proc/sys/kernel/random/poolsize}} to keep an eye on the entropy pool. More information on the kernel RNG is available via {{ic|man 4 random}}.
+
 
+
The Kernels poolsize is {{ic|4096}} bit. (512 Byte)
+
 
+
While Linux kernel 2.4 did have writable {{ic|/proc}}-entries for controlling the entropy-poolsize in newer kernels only {{ic|read_wakeup_threshold}} and {{ic|write_wakeup_threshold}} are writable.
+
 
+
The pool size is now hardcoded in kernel line 275 of {{ic|/drivers/char/random.c}}
+
  
 
{{bc|/*
 
{{bc|/*
 
  * Configuration information
 
  * Configuration information
 
  */
 
  */
'''#define INPUT_POOL_WORDS 128'''
+
#define '''INPUT_POOL_WORDS 128'''
#define OUTPUT_POOL_WORDS '''32'''
+
#define '''OUTPUT_POOL_WORDS 32'''
#define SEC_XFER_SIZE 512
+
...}}
#[...]}}
+
  
where poolsize is {{ic|<nowiki>4096 = INPUT * OUTPUT</nowiki>}}
+
The kernel's pool size is given by {{ic|INPUT_POOL_WORDS * OUTPUT_POOL_WORDS}} which makes, as already stated, 4096 bits.
 +
{{Warning|Do not use even {{ic|/dev/random}} to generate ''critical'' cryptographic keys on a system you do not [http://everything2.com/title/Compromising+%252Fdev%252Frandom control]. If in doubt, for example in shared server environments, rather choose to create the keys on another system and transfer them.}}
  
 
=== /dev/urandom ===
 
=== /dev/urandom ===
; /dev/urandom: reuses existing entropy pool data while the pool is replenished and although '''not''' suited for the most crucial cryptographic purposes, for example the generation of longterm keys, its quality should be sufficient for a paranoid disk wipe, [[#Preparations for block device encryption|preparing for block device encryption]], wiping LUKS keyslots, wiping single files and many other purposes.
+
In contrast to {{ic|/dev/random}}, {{ic|/dev/urandom}} reuses existing entropy pool data while the pool is replenished: the output will contain less entropy than the corresponding read from {{ic|/dev/random}}, but its quality should be sufficient for a paranoid disk wipe, [[Securely wipe disk#Preparations for block device encryption|preparing for block device encryption]], wiping LUKS keyslots, wiping single files and many other purposes. Nevertheless it might still take a long time to bottle-feed the neverending surge of large drives with data.
 
+
{{ic|/dev/random}} uses the kernel entropy pool and will halt overwriting until more input entropy once this pool has been exhausted. This can make it impractical for overwriting large hard disks.
+
 
+
{{ic|/dev/urandom}} in contrast will reuse entropy when low on it so you won't get stuck. Nevertheless it might still take a long time to bottle-feed the neverending surge of large drives with data.
+
  
The output may contain less entropy than the corresponding read from /dev/random. However it is still intended as a pseudorandom number generator suitable for most cryptographic purposes,
+
{{Warning|{{ic|/dev/urandom}} is '''not''' recommended for the generation of long-term cryptographic keys.}}
{{Warning|/dev/'''u'''random is not recommended for the generation of long-term cryptographic keys.}}
+
  
 
== Faster alternatives ==
 
== Faster alternatives ==
A Good Compromise between Performance and Security might be the use of a [[Wikipedia:Pseudorandom_number_generator|pseudorandom number generator]] (like [[Frandom]]).
+
A more practical compromise between performance and security is the use of a [[Wikipedia:Pseudorandom_number_generator|pseudorandom number generator]]. In Arch Linux repositories for example:
 +
* [[Haveged]]
 +
* [[Frandom]]
  
For much better performance to refill the entropy pool, one can consider using a pseudorandom number generator instead of the kernel, e.g. [[Frandom]].
+
There are also [[Wikipedia:Cryptographically_secure_pseudorandom_number_generator|cryptographically secure pseudorandom number generator]]s like [[Wikipedia:Yarrow_algorithm|Yarrow]] (FreeBSD/OS-X) or [[Wikipedia:Fortuna_(PRNG)|Fortuna]] (the intended successor of Yarrow).
  
There are also [[Wikipedia:Cryptographically_secure_pseudorandom_number_generator|cryptographically secure pseudorandom number generator]]s
+
== See also ==
like [[Wikipedia:Yarrow_algorithm|Yarrow]] (FreeBSD/OS-X) or [[Wikipedia:Fortuna_(PRNG)|Fortuna]] (the intended successor of Yarrow).
+
* [http://www.ietf.org/rfc/rfc4086.txt  RFC4086 - Randomness Requirements for Security] (Section 7.1.2 for /dev/random)
 +
* [http://lkml.indiana.edu/hypermail/linux/kernel/1302.1/00479.html Linux Kernel ML] - discussion on patching /dev/random for higher throughput (February 2013)
 +
* [http://eprint.iacr.org/2013/338 A challenge on /dev/random robustness] (June 2013)  
 +
* [http://www.random.org/randomness/ Randomness] - A popular science article explaining different RNGs

Revision as of 12:11, 15 February 2014

From wikipedia:Random number generation:

A random number generator (RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random.

Generation of random data is crucial for several applications like making cryptographic keys (e.g. for Disk Encryption), securely wiping disks, running encrypted Software access points.

Kernel built-in RNG

The Linux kernel's built-in RNGs /dev/{u}random are highly commended for producing reliable random data providing the same security level that is used for the creation of cryptographic keys. The random number generator gathers environmental noise from device drivers and other sources into an entropy pool.

Note that the man random command will misdirect to the library function manpage random(3) while for information about the /dev/random device files you should run man 4 random to read random(4).

/dev/random

/dev/random uses an entropy pool of 4096 bits (512 Bytes) to generate random data and stops when the pool is exhausted until it gets (slowly) refilled. /dev/random is designed for generating cryptographic keys (e.g. SSL, SSH, dm-crypt's LUKS), but it is impractical to use for wiping current HDD capacities: what makes disk wiping take so long is waiting for the system to gather enough true entropy. In an entropy-starved situation (e.g. a remote server) this might never end. While doing search operations on large directories or moving the mouse in X can slowly refill the entropy pool, it's designated pool size alone will be indication enough of the inadequacy for wiping a disk.

You can always compare /proc/sys/kernel/random/entropy_avail against /proc/sys/kernel/random/poolsize to keep an eye on the system's entropy pool.

While Linux kernel 2.4 did have writable /proc entries for controlling the entropy pool size, in newer kernels only read_wakeup_threshold and write_wakeup_threshold are writable. The pool size is now hardcoded in kernel line 275 of /drivers/char/random.c:

/*
 * Configuration information
 */
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
...

The kernel's pool size is given by INPUT_POOL_WORDS * OUTPUT_POOL_WORDS which makes, as already stated, 4096 bits.

Warning: Do not use even /dev/random to generate critical cryptographic keys on a system you do not control. If in doubt, for example in shared server environments, rather choose to create the keys on another system and transfer them.

/dev/urandom

In contrast to /dev/random, /dev/urandom reuses existing entropy pool data while the pool is replenished: the output will contain less entropy than the corresponding read from /dev/random, but its quality should be sufficient for a paranoid disk wipe, preparing for block device encryption, wiping LUKS keyslots, wiping single files and many other purposes. Nevertheless it might still take a long time to bottle-feed the neverending surge of large drives with data.

Warning: /dev/urandom is not recommended for the generation of long-term cryptographic keys.

Faster alternatives

A more practical compromise between performance and security is the use of a pseudorandom number generator. In Arch Linux repositories for example:

There are also cryptographically secure pseudorandom number generators like Yarrow (FreeBSD/OS-X) or Fortuna (the intended successor of Yarrow).

See also