3 ms·
> 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 e
by throw0101a 7y ago
> 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 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 7y agoNo, 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.
- cperciva 7y agoMany 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.
- tptacek 7y agoThat'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 7y agoI 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.
- ben_bai 7y agoThat'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 7y agowhy 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.
- throw0101a 7y ago> 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.