More fundamentally, an important conceptual part of crypto is that you can use a random key of a very small, fixed size, like 16 bytes, to generate an infinite amount of output, such that knowing any part of the output doesn't help you guess at any other part of the output nor the input key. If true, this is an amazingly powerful property because you can securely exchange (or derive) a short key once and then you can send as much encrypted data back and forth as you want. If you needed to re-seed the input with as many bits as you take from the output, disk encryption wouldn't be sound (you'd need a key or passphrase as long as your disk), SSL would be way more expensive (and couldn't be forward-secure) if it even worked at all, Kerberos wouldn't work, Signal wouldn't work, etc.

The claim of /dev/random and this wacky government standard is that in fact disk encryption, SSL, etc. are flawed designs, good enough for securing a single communication but suboptimal because they encrypt more bits of data than the size of the random key, and so when generating random keys, you really ought to use "true random numbers" so that breaking one SSL connection doesn't help you break another. Whether it's a pen-and-paper cipher like Vigenère or a fancy modern algorithm like AES, anything with a fixed-size key can be cryptanalyzed and you shouldn't provide too much output with it, for your secure stuff you must use a one-time pad. The claim of the cryptography community is that, no, in fact, there's nothing flawed about this approach and stretching fixed-size keys is the very miracle of cryptography. We know how to do it securely for any worthwhile definition of "securely" (including definitions where quantum computers are relevant) and we should, because key-based encryption has changed our world for the better.

Isn't that the theory behind every stream cipher? (And stream ciphers are generally just 'simplified' one-time pads.)

That's what OpenBSD's arc4random(4) start as: the output of RC4.

The Kernel starts an ChaCha20 stream cipher with this supplied entropy while constantly mixing in timing entropy from devices.

This chipherstream supplies the Kernel with random data and once userland is up this is good enought and also used for /dev/random and /dev/urandom, which on OpenBSB is the same device(non blocking).

Now the fun part: When a userland process gets created it has a randomdata ELF segment that the Kernel fills and which is used as entropy for a new ChaCha20 stream, just for the application should it decide to call arc4random or use random data in any other way (like calling malloc or free, which on OpenBSD make heavy use of random data).

Interestingly, Linux provides 128 bits of random data on exec through the ELF auxiliary vector mechanism. (https://lwn.net/Articles/519085/) Between the disappearance of the sysctl(2) syscall and the addition of getrandom(2), it was the only way to acquire strong seed entropy without opening a file resource.

EDIT: Which makes me curious how Linux filled AT_RANDOM for init(1) and other early boot time processes. But not curious enough to comb through old code...

It uses get_random_bytes(), which is documented as "equivalent to a read from /dev/urandom."

https://github.com/torvalds/linux/blob/v5.4/fs/binfmt_elf.c#...

This is news to me. When did they add this (neat) functionality?

https://github.com/openbsd/src/blob/master/libexec/ld.so/SPE...

https://www.openbsd.org/innovations.html

No other OS has this.

(Unfortunately, glibc uses this data directly as stack and pointer protector cookies, instead of deriving something from it, which means it feels a little risky to use this to initialize a userspace PRNG. I guess you shouldn't be leaking cookies....)

Linux added this in v2.6.29 (2009) in https://github.com/torvalds/linux/commit/f06295b4 , and glibc in 2009 added support for using it if available to set up cookies (it previously read from /dev/urandom). That said, I don't really think the "we're the only OS" game is a game worth playing - if it's a security improvement, it's best if everyone has it, regardless of OS!

> The original version of this random number generator used the RC4 (also known as ARC4) algorithm. In OpenBSD 5.5 it was replaced with the ChaCha20 cipher, and it may be replaced again in the future as cryptographic techniques advance. A good mnemonic is “A Replacement Call for Random”.

So let's look at how a hypothetical CSPRNG might work. We get our random numbers by repeatedly hashing a pool of bytes, and then feeding the result, and various somewhat random events, back into the pool. Since our hash does not leak any information about the input (if it did, we'd have much bigger problems), this means attackers must guess, bit for bit, what the value of the internal pool of entropy is.

This is essentially how randomness works on Linux (they just use a stream cipher instead for performance)

This clarifies a few things:

1. even if you assume intels randomness instructions are compromised, it still is not an issue to stirr them into the pool. Attackers need to guess every single source of randomness.

2. "Running out of randomness" is nonsensical. If you couldn't guess the exact pool before, you can't suddenly start guessing the pool after pulling out 200 exabytes of randomness either.

Basically, you[0] should think of /dev/random as having a front buffer and a back buffer. The back buffer has a certain amount of entropy in it, but you can't take part of that entropy out; the only thing you can do with it is add entropy or empty the entire back buffer into the front buffer. The front buffer doesn't have a entropy amount per se, what it has is a security rating[1]; when you empty the back buffer into it, its security rating increases up to (not plus) the number of bits in the back buffer (this is not additive; a 256-bit front buffer combined with a 256-bit back buffer produces a front buffer with 256 bits, not 512) and the back buffer goes to zero. If you keep dumping the back buffer into front buffer whenever it reaches 64 bits, you'll never have a RNG that's more than 64-bit secure.

Reading from /dev/random doesn't deplete the front buffer (because CSPRNG) or the back buffer (because it doesn't interact with the back buffer). A memory-read attack on the other hand basically sets both buffers to zero - you have to start all over again.

So you can "use up" randomness by constantly wasting it to refresh a insufficiently-strong front buffer. And you can "run out" if someone is able to read your buffers (or brute force a weak buffer in, say, 2^64 CSPRNG invocations).

0: As a designer. As a user, you should treat /dev/random (like any cryptographic primitive) as something that will look perfectly secure from the outside even if it's hopelessly broken, and investigate the details of the specific implementation you're using accordingly.

1: Just like a cryptographic algorithm; the lowest rating involved determines how secure your system is. A 512-bit RNG with a 64-bit cypher is only 64-bit secure, and a 512-bit cypher fed by a 64-bit RNG is also only 64-bit secure.

Yes, I know. Where did I say anything about revealing? My comment was about 'running out', which is (IIRC) a limitation of some random number generators because of how they handle internal state. Now, that state may have many, many bits, but it is still finite. An analogy I've seen is like having a (paper) codebook.

Of course, if a system is compromised, and the attacker can read kernel memory, they can probably then recreate the stream--which is why (e.g.) OpenBSD stirred things up every so often.

Also, when you look at cache side channel attacks -- RC4 definitely publishes its internal state.

But the point is mood b.c. the stream cipher used switched from RC4 to ChaCha20 like 5 years ago. And there is no side channel attack on ChaCha20, yet.

Yes, everybody does that. But how many bytes you drop matters; over the years the recommendations have gone from 256 bytes to 512 bytes to 768 bytes to 1536 bytes to 3072 bytes as attacks have gotten better.