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.

Warning: Never ever generate cryptographic keys on a system you do not control, where you cannot guarantee nobody is monitoring your key creation and even possibly extracting a copy of it, e.g. 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.[1] [2] [3]

Arguments

D. J. Bernstein, The cr.yp.to blog, "2014.02.05: Entropy Attacks!", version of 2014-02-05:

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.