3 ms·

Quarrel? Here, let me clarify. A PRNG has state with a certain amount of potential entropy, call this X. Uniformly shuffling a deck of cards requires a certa

Quarrel? Here, let me clarify. A PRNG has state with a certain amount of potential entropy, call this X. Uniformly shuffling a deck of cards requires a certain amount of entropy, Y. If X > Y then theoretically you can generate all possible shufflings with your PRNG, assuming it's seeded properly. If X < Y, then you can't. The key difference is that your PRNG could be cryptographically secure even though X < Y. It turns out that Y ≈ 226 bits, and so it's plausible that your cryptographically secure RNG would have X = 128 bits, for example, even though I'd typically expect a larger number. People often conflate entropy with security. A random number source could have high amounts of entropy and be insecure, while a random number source with less entropy could be very secure. Or let me put it this way: entropy is necessary but not sufficient for security.

schoen 11y ago
I agree with your argument on a pigeonhole-principle level (if you only observe fewer than 128 bits of state and then shuffle cards in a deterministic way based on a summary of your observations, you can't get all possible shuffles out), and I think that's a nice observation. 52! is surprisingly huge, and determinism is deterministic. :-) The issue is just about what /dev/urandom and /dev/random do.
- dietrichepp 11y ago
  There's a lot of misinformation and cargo cult crypto programming, but the basic summary is that /dev/random information-theoretic security is unnecessary for most applications, but necessary for being able to know that you can produce every possible permutation of a deck of cards. http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
  - tptacek 11y ago
    /dev/random and /dev/urandom are the same CSPRNG construction; /dev/random just provides some extra (almost always counterproductive) checks on the rate at which it's rekeyed. It is not the case that using /dev/random somehow gets you an information-theoretic security level that /dev/urandom doesn't.
    - dietrichepp 11y ago
      Yes, they both use the same PRNG construction, that's in the article I linked to. But the blocking behavior of /dev/random does give it information-theoretic security, because an attacker with unlimited computational power can't predict its output, assuming they don't know the outputs of the entropy sources you are using, assuming that your entropy estimates are accurate or conservative. And we use /dev/urandom because information-theoretic security in our RNG does not improve actual system security.
      - Tomte 11y ago
        No, it doesn't, because all the mixing and mangling of your precious entropy inside drivers/char/random.c is not information-theoretically secure.
        dietrichepp 11y ago
        Right, I give up. What I should have said is, "/dev/random is a misguided attempt at information-theoretic security." Everything in its design makes it clear that its goal is information-theoretic security. I was thinking, "Oh, the mixing is good enough for practical use." But that's not what information-theoretic means. I was thinking, "Oh, assuming the entropy estimation works." But we know it doesn't. It was a stupid argument. But then again, /dev/random is stupid. Nobody gives a damn about information-theoretic security, and we don't have it anyway.
im2w1l 11y ago
It only takes 226 bits of entropy if all shuffles should be equally likely. If one shuffle has probability sufficiently close to 1, and the rest are equally likely, you could make do with less than a bit of entropy.
- dietrichepp 11y ago
  Right, that's what "uniformly" means. Discrete uniform distribution = all shuffles are equally likely.

schoen 11y ago

I agree with your argument on a pigeonhole-principle level (if you only observe fewer than 128 bits of state and then shuffle cards in a deterministic way based on a summary of your observations, you can't get all possible shuffles out), and I think that's a nice observation. 52! is surprisingly huge, and determinism is deterministic. :-) The issue is just about what /dev/urandom and /dev/random do.

dietrichepp 11y ago
There's a lot of misinformation and cargo cult crypto programming, but the basic summary is that /dev/random information-theoretic security is unnecessary for most applications, but necessary for being able to know that you can produce every possible permutation of a deck of cards. http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
- tptacek 11y ago
  /dev/random and /dev/urandom are the same CSPRNG construction; /dev/random just provides some extra (almost always counterproductive) checks on the rate at which it's rekeyed. It is not the case that using /dev/random somehow gets you an information-theoretic security level that /dev/urandom doesn't.
  - dietrichepp 11y ago
    Yes, they both use the same PRNG construction, that's in the article I linked to. But the blocking behavior of /dev/random does give it information-theoretic security, because an attacker with unlimited computational power can't predict its output, assuming they don't know the outputs of the entropy sources you are using, assuming that your entropy estimates are accurate or conservative. And we use /dev/urandom because information-theoretic security in our RNG does not improve actual system security.
    - Tomte 11y ago
      No, it doesn't, because all the mixing and mangling of your precious entropy inside drivers/char/random.c is not information-theoretically secure.
      - dietrichepp 11y ago
        Right, I give up. What I should have said is, "/dev/random is a misguided attempt at information-theoretic security." Everything in its design makes it clear that its goal is information-theoretic security. I was thinking, "Oh, the mixing is good enough for practical use." But that's not what information-theoretic means. I was thinking, "Oh, assuming the entropy estimation works." But we know it doesn't. It was a stupid argument. But then again, /dev/random is stupid. Nobody gives a damn about information-theoretic security, and we don't have it anyway.

im2w1l 11y ago

It only takes 226 bits of entropy if all shuffles should be equally likely. If one shuffle has probability sufficiently close to 1, and the rest are equally likely, you could make do with less than a bit of entropy.

dietrichepp 11y ago
Right, that's what "uniformly" means. Discrete uniform distribution = all shuffles are equally likely.