Create page for edit
New page
Based off [https://wiki.archlinux.org/index.php?title=Random_number_generation&oldid=410093 Random number generation 410093]
[[Category:Encryption]]
[[ja:乱数生成]]
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 wipe disk|securely wiping disks]], running encrypted [[Software access point]]s.
== Kernel built-in RNG ==
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.
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 {{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 ===
{{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.
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.
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}}:
{{bc|/*
* Configuration information
*/
#define '''INPUT_POOL_WORDS 128'''
#define '''OUTPUT_POOL_WORDS 32'''
...}}
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. The cryptographer D. J. Bernstein illustrates the control problem with a [http://blog.cr.yp.to/20140205-entropy.html Mark Twain quotation].}}
=== /dev/urandom ===
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.[http://www.2uo.de/myths-about-urandom/] [http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/] [https://www.mail-archive.com/cryptography@randombit.net/msg04748.html]
{{Warning|{{ic|/dev/urandom}} is '''not''' recommended for the generation of long-term cryptographic keys.}}
== Faster alternatives ==
For applications other than the generation of long-term cryptographic keys, a 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]]
* [[rng-tools]]
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).
== See also ==
* [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://eprint.iacr.org/2014/167 An analysis of low entropy state] behaviour of /dev/random, Yarrow, Fortuna and new model approach (March 2014)
* [http://www.random.org/randomness/ Randomness] - A popular science article explaining different RNGs
* [http://www.fourmilab.ch/random/ ENT] - A simple program for testing random sequences (entropy, Chi square test, Monte Carlo, correlation, etc.)
* [http://www.codeproject.com/Articles/795845/Arduino-Hardware-Random-Sequence-Generator-with-Ja DIY HRNG] - One example of a low-cost, DIY Arduino HRNG