User:Dinghy/RNG-p1
Based off Random number generation 410093
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). To create a secured environment (e.g. a connection), these applications need to share a secret that is only known to those applications or users that may access the secured environment. To make sure only those allowed parties can take hold of this secret, (1) it must but kept in an intrusion-protected environment and (2) it must be unique, so that no one could theoretically generate it during trials. The only way to guarantee uniqueness is to create secrets based on perfectly random data. In the real (non-mathematical) world, perfect randomness does not exist. Therefore, each and any consideration relating to cryptographic strength is based on the assumption of sufficient randomness.
Kernel built-in RNG
The Linux kernel's built-in RNGs /dev/{u}random are highly commended for producing reliable random data providing a sufficient security level for the creation of cryptographic keys. The random number generator gathers environmental noise from device drivers and other sources into a pool. The more randomness it acquires, the higher will be the so-called entropy of data it can output.
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 refilled. /dev/random
is designed for generating cryptographic keys (e.g. SSL, SSH, dm-crypt and LUKS master keys), but it is impractical to use for e.g. wiping current HDD capacities. The difference resides in the amount of data that needs to be generated for the procedure. Disk wiping (or any other form of using great amounts of data) by writing /dev/random
output is will usually take too much time to be useful, because the system will constantly be waiting to gather more entropy. In an entropy-starved situation this might never end. An entropy-starved situation could be e.g. a remote server, where every system runs imperturbably the same processes in the same environment, i.e. a situation that shows little randomness, even to the human perception. 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.
/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.[1] [2] [3]
See also
See also
- RFC4086 - Randomness Requirements for Security (Section 7.1.2 for /dev/random)
- Linux Kernel ML - discussion on patching /dev/random for higher throughput (February 2013)
- A challenge on /dev/random robustness (June 2013)
- An analysis of low entropy state behaviour of /dev/random, Yarrow, Fortuna and new model approach (March 2014)
- Randomness - A popular science article explaining different RNGs
- ENT - A simple program for testing random sequences (entropy, Chi square test, Monte Carlo, correlation, etc.)
- DIY HRNG - One example of a low-cost, DIY Arduino HRNG
- Myths about /dev/urandom by Thomas Hühn
Arguments
This is exactly the opposite of what people tend to do today, namely adding new entropy all the time. The reason that new entropy is a problem is that each addition of entropy is a new opportunity for a malicious entropy source to control "random" outputs—breaking DSA, leaking secret keys, etc. The conventional wisdom says that hash outputs can't be controlled; the conventional wisdom is simply wrong.
Is there any serious argument that adding new entropy all the time is a good thing? The Linux /dev/urandom manual page claims that without new entropy the user is "theoretically vulnerable to a cryptographic attack", but (as I've mentioned in various venues) this is a ludicrous argument—how can anyone simultaneously believe that
- we can't figure out how to deterministically expand one 256-bit secret into an endless stream of unpredictable keys (this is what we need from urandom), but
- we can figure out how to use a single key to safely encrypt many messages (this is what we need from SSL, PGP, etc.)?
There are also people asserting that it's important for RNGs to provide "prediction resistance" against attackers who, once upon a time, saw the entire RNG state. But if the attacker sees the RNG state that was used to generate your long-term SSL keys, long-term PGP keys, etc., then what exactly are we gaining by coming up with unpredictable random numbers in the future? I'm reminded of a Mark Twain quote:
Behold, the fool saith, "Put not all thine eggs in the one basket"—which is but a manner of saying, "Scatter your money and your attention;" but the wise man saith, "Put all your eggs in the one basket and—WATCH THAT BASKET."
We obviously need systems that can maintain confidentiality of our long-term keys. If we have such systems, how is the attacker supposed to ever see the RNG state in the first place? Maybe "prediction resistance" can be given a theoretical definition for an isolated RNG system, but I don't see how it makes any sense for a complete cryptographic system.