[ATsch]

The idea of "randomness" being "used up", and then "running out of randomness", somehow.

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.

[a1369209993]

There is actually a sense in which you can "use up" or "run out" of randomness; it's just almost the exact opposite of how unix-style /dev/random design thinks about it.

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.

[throw0101a]

> 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.

Not entirely.

/dev/random and arc4random(4) under OpenBSD originally used the output of RC4, which has a finite state size:

* https://en.wikipedia.org/wiki/RC4

Rekeying / mixing up the state semi-regularly would reset things. It's the occasional shuffling that really helps with forward security, especially if a system has been compromised at the kernel level.

[tptacek]

No, Arc4random didn't reveal its internal RC4 state as it ran, in the same sense that actually encrypting with RC4 doesn't deplete RC4's internal state.

[throw0101a]

> No, Arc4random didn't reveal its internal RC4 state as it ran ...

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.

[cperciva]

Many implementations didn't do enough mixing before generating output, though.

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

[ben_bai]

That's why OpenBSD cut away the start of the RC4 stream (don't remember how many bytes) to make backtracking harder.

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.

[cperciva]

why OpenBSD cut away the start of the RC4 stream (don't remember how many bytes) to make backtracking harder

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.

[tptacek]

That's obviously true, but in the most unhelpful way possible, where you introduce a complex additional topic without explaining how it doesn't validate the previous commenter's misapprehension about how "state" works in this context.

[cperciva]

I wasn't entirely sure if the previous commenter was confused or merely saying things in a confusing way. The fact is that with a small entropy pool and a leaky mechanism like RC4, you absolutely can run out of entropy.