3 ms·
> Given how scarce entropy sources tend to be, it always torqued me a bit that if I want to simulate a dice roll I had to grab a whole float worth of data from
by yorwba 6y ago
> Given how scarce entropy sources tend to be, it always torqued me a bit that if I want to simulate a dice roll I had to grab a whole float worth of data from the entropy source instead of something smaller.
Grabbing a float worth of data and reducing it to a dice roll is no different from getting the bits for the dice roll directly. Entropy doesn't decrease just by getting bits from an RNG, it decreases by an attacker learning what those bits are.
If you throw away bits without looking at them, an attacker doesn't get to look at them either, so entropy doesn't decrease. Otherwise, running an RNG in a loop would decrease entropy all the way to zero (meaning its values become fully predictable) no matter what you do with the output. But RNGs that are actually used have a finite state space they cycle through. Completing a full (long) cycle returns to the original state and how could entropy decrease between two identical states?
Entropy measures how hard it is for an external observer to predict the next random value. If you run an RNG for a full cycle and tell someone all the values, then they can perfectly predict the next cycle just by looking at their recording (entropy is zero). But if you don't let them know anything, they're none the wiser (entropy remains unchanged).
> we don’t generate 1-6 via division, we generate it by multiplying a random number between 0.0 and 1.0 times 6 and add a 1
You can do that, but you don't get each value with the same probability. E.g. if the floating point type can represent eight values between 0.0 and 1.0, you might think that's enough, since you only need six, but actually
>>> [1+int((i/8.)*6) for i in range(8)]
[1, 1, 2, 3, 4, 4, 5, 6]
1 and 4 end up twice as likely as other numbers.
Double precision floating point numbers have enough different possibilities for this effect not to matter much, but if you want to eliminate it completely, you need to detect it, reject the current value and generate a new one. That extra check may be implemented using a division, but can be optimized (thus "nearly divisionless").
- hinkley 6y ago“Entropy source” is a phrase that has a specific meaning. https://en.m.wikipedia.org/wiki/Entropy_(computing) https://en.m.wikipedia.org/wiki/Entropy_(computing) PRNGs, even CSPRNGs, are not an entropy source. They’re an algorithm used to deal with the lack of a high throughput entropy source. If someone is trying to do an analysis attack on /dev/random (and they aren’t nuts) then we are all in some serious trouble.
- yorwba 6y agoYes, PRNGs are not entropy sources and using a PRNG does not generate new entropy. But using a PRNG also doesn't reduce the entropy it already has. You only lose entropy by transmitting information, and the entropy lost is equal to the information transmitted. For example, if an adversary with perfect analytical ability learns the outcome of a simulated dice roll you performed using /dev/random, they gain log₂(6) bits of information and you lose the same amount of entropy, irrespective of how many bits you actually read from /dev/random.
- hinkley 6y agoYou have made assumptions that I did not, and you're talking past me (at length). I didn't say anything about sticking a PRNG between Lemire and the entropy source. If I'm generating an RSA key pair I'm going to pull kilobytes of data from the entropy source, not a PRNG, and that data volume will be a fixed multiple of some word size that means that every bit I take has a purpose. If I need a non-multiple of the word length worth of entropy from the entropy source, no standard library I know of handles that. C, Java, a few others always fetch 32 or 64 bits of data and then throw most of it away, even if the system call might allow finer increments. If I need 6 bits or 200 bits, I have to stick a CSPRNG in there or throw entropy away. If I do the latter (which people often do by default) I'm robbing bits/second of entropy from something that may really need it, like TLS or especially SSH. I've found myself in testing situations where it was faster to regenerate a VM/reflash a Pi microSD than wait for /dev/random to catch up, due to iterating on a writing a script that uses scp or keygen calls. I haven't seen a production issue in a while, and never that severe (eg, HTTPS throttling), but it's happened to somebody I'm sure.