How does a cryptographically secure random number generator work?

Question

I understand how standard random number generators work. But when working with cryptography, random numbers really need to be random.

I know there are tools that read cosmic white noise to help create secure hashes, but this is not the case on your standard PC.

How does a cryptographically secure random number generator get its values ​​without repeating patterns?

Answer 1

A cryptographically secure random number generator, as you could use to generate encryption keys, works by collecting entropy - that is, unpredictable input - from a source that other people cannot observe.

For example, / dev / random (4) on Linux collects information about changes in hardware interrupt times from sources such as hard drives that return data, keystrokes, and incoming network packets. This approach is safe provided that the kernel does not overestimate how much entropy it has collected. A few years ago, estimates of entropy from various sources were reduced, which made them much more conservative. Here's an explanation of how Linux rates entropy .

None of this is particularly high bandwidth. / dev / random (4) is probably safe, but it maintains this security by refusing to give out data as soon as it cannot be sure that this data is safely random. If you want, for example, to generate a lot of cryptographic keys and nonces, then you probably want to turn to equipment random number generators.

Often, hardware RNGs are designed to sample from the difference between two generators that operate at close to the same speed, but whose speeds vary slightly depending on thermal noise. If I remember correctly, the random number generator that is used for the UK premium bond lottery, ERNIE, works this way.

Alternative schemes include sampling the noise on the CCD (see lavaRND ), radioactive decay (see hotbits ), or atmospheric noise (see random.org or just plug in an AM radio station somewhere besides the station into your sound card). Or you can directly ask a computer user to hit the keyboard like a crazy chimpanzee for a minute, no matter what your boat is floating.

I apologize for the lack of embedded links, but apparently I have to record most of my life on this website before I am allowed to post more.

EDIT: take this. Since some people were kind enough in this bag of bones to flip it up and down, I apparently allowed the rest of the links to be placed for now. Thank you, good people! ^ _ ^

EDIT: as andras pointed out, I only thought of some of the most common entropy collection schemes. Thomas Pornin 's Answer and Johannes Rössel's Answer , both do good assignments, explaining how one can walk along the mangrove aggregate of entropy in order to transmit the bit again.

Answer 2

For cryptographic purposes, it is necessary that the stream be "computationally indistinguishable from uniformly random bits." “Computationally” means that it should not be truly random, just to make it appear to someone without access to God, his own computer.

In practice, this means that the system must first assemble a sequence of n truly random bits. n must be large enough to prevent an exhaustive search, i.e. it is impractical to use all 2 ^ n-combinations of n bits. This is achieved in relation to today's technology if n is greater than 90 or so, but cryptographers just love the powers of the two, so it’s customary to use n = 128.

These n random bits are obtained by collecting "physical events" which should be unpredictable as far as physics is concerned. Usually time is used: the processor has a cycle counter that is updated several billion times per second, and some events occur with an inevitable amount of jitter (incoming network packets, mouse movements, keystrokes ...). The system encodes these events and then “compresses” them using a cryptographically secure hash function such as SHA-256 (the output is then truncated to get our n bits). It is important here that the coding of physical events has sufficient entropy: roughly speaking, the events mentioned could together take at least 2 ^ n combinations. A hash function, by its definition, should concentrate well on the concentration of this entropy in an n-bit string.

Once we have n bits, we use PRNG (pseudo random number generator) to extract as many bits as possible. It is said that PRNG is cryptographically secure if, assuming that it works on a rather narrow unknown n-bit key, its output is computationally indistinguishable from uniformly random bits. In the 90s, the RC4 was a popular choice, which is very easy to implement and pretty fast. However, it turned out that he has measurable prejudices, i.e. He was not as indistinguishable as he had originally desired. The eSTREAM project was to collect new projects for PRNG (actually stream ciphers, since most stream ciphers consist of PRNG, whose output is XORed to encrypt the data), document them and promote the analysis with cryptographs. The eSTREAM portfolio contains seven PRNG projects that were considered quite safe (i.e., they resisted the analysis, and cryptographers, as a rule, well understood why they resisted). Among them, four are "software optimized." The good news is that although these new PRNGs seem much more secure than RC4, they are also noticeably faster (we are talking about hundreds of megabytes per second, here). Three of them are “free for any use” and source code is provided.

From a design point of view, PRNG reuses many block cipher elements. The same concepts of avalanche and diffusion of bits into a wide internal state are used. Alternatively, a decent PRNG can be built from a block cipher: just use the n-bit sequence as the key in the block cipher and encode the sequential counter values ​​(expressed as a m-bit sequence if the block cipher uses m-bits). This creates a pseudo-random bitstream, which is computationally indistinguishable from random, as long as the block cipher is safe and the resulting stream is no more than m * 2 ^ (m / 2) bits (with m = 128, this means about 300 billion gigabytes, which is enough for most purposes). This use is known as counter mode (CTR) .

Typically, a block cipher in CTR mode does not work as fast as a dedicated stream cipher (the point of stream encryption is that, losing the flexibility of the block cipher, higher performance is expected). However, if you have one of the latest Intel processors with AES-NI instructions (which are basically hardware AES implementations integrated into the CPU), then AES with CTR mode will give you unrivaled speed (several gigabytes per second).

Answer 3

First of all, a cryptographically secure PRNG point should not generate completely unpredictable sequences. As you have noticed, the absence of something that generates large volumes of (more or less) true randomness ¹ makes it impossible.

So, you are resorting to something that is difficult to predict. “Hard” here means that it lasts a long time, and at that time all that was needed would be obsolete anyway. There are a number of mathematical algorithms that play a role in this - you can get an idea if you take some famous CSPRNGs and see how they work.

The most common options for building such a PRNG are:

• Using stream encryption that already outputs a (supposedly secure) pseudo-random bitstream.
• Using Block Encryption in Counter Mode

Also, hash functions on the counter are sometimes used. Wikipedia is more about that .

The general requirements are that it is not possible to determine the initial initialization vector from the generator bit stream and that the next bit cannot be easily predicted.

Regarding initialization, most CSPRNGs use various sources available in the system, ranging from really random things like line noise, interrupts or other events in the system, to other things like specific memory locations, and c. The initialization vector is preferably truly random and does not depend on a mathematical algorithm. This initialization has been disrupted for some time when deploying OpenSSL to Debian, which has led to serious security issues.

---

¹ Who also has their own problems, and you need to be careful in eliminating bias, because things like thermal noise have different characteristics depending on the temperature - you almost always have bias and the need to eliminate it. And this is not a trivial task in itself.

Answer 4

For a random number generator to be considered cryptographically secure , it must be protected from attack by an adversary who knows the algorithm and the (large) number of previously generated bits. This means that someone with this information cannot restore any hidden internal state of the generator and give predictions about which subsequent discharges will be obtained with an accuracy of more than 50%.

Ordinary pseudo-random number generators are generally not cryptographically secure, since restoring the internal state from previously output bits is a common trivial one (often the entire internal state is only the last N bits created directly). Any random number generator without good statistical properties is also not cryptographically protected, since its output is at least predictable, not even knowing the internal state.

So, with regard to how they work, any good cryptosystem can be used as a cryptographically secure random number generator - use a cryptosystem to encrypt the output of a "normal" random number generator. Since the adversary cannot restore the normal text output of the normal random number generator, he cannot attack it directly. This is a somewhat circular definition that asks the question of how you force the cryptosystem to protect it, which is another problem.

Answer 5

Each generator will use its own seeding strategy, but here is a bit from the Windows API documentation on CryptGenRandom

With Microsoft CSP, CryptGenRandom uses the same random number generator used by other security components. This allows processes to contribute to the system-wide seed. CryptoAPI stores an intermediate random seed with each user. To form seeds for a random number generator, the calling application delivers bits that it can have, for example, data input from a keyboard or keyboard, which then, in combination with stored seeds and various system data and the user, data such as a process identifier and a stream identifier, system clock, system time, system counter, memory status, free disk clusters, hashed user environment block. This result is used for a pseudo random number generator (PRNG).

In Windows Vista Service Pack 1 (SP1) and later, a PRNG implementation based on the AES anti-prescription regimen specified in NIST is used in special publication 800-90. In Windows Vista, the repository of Windows Server 2003 and Windows XP, PRNG, is specified in Federal Information Processing Standard (FIPS) 186-2. If the application has access to a good random source, it can fill the pbBuffer buffer with some random data before calling CryptGenRandom. The CSP then uses this data to further randomize its internal seed. It is allowed to omit the pbBuffer buffer initialization step before calling CryptGenRandom.