7 ms·

It has probability 0 of running forever

konschubert 5y ago
But a nonzero possibility of running longer than x for any x>0 ;) In practice, it doesn't matter, I agree.
wizzwizz4 5y ago
Assuming a perfect RNG, but PRNGs don't have infinite state. So it's either impossible, or has a finite probability, with a finite probability for each of those cases, for an overall finite (non-zero) subjective probability of it running forever (in ideal program-space; obviously it will never run forever in real life).
- tialaramex 5y ago
  No, you don't need a perfect RNG. You need anything that's not completely horrible. Remember, we're not trying to read a whole password from the device, just one matching byte at a time. So, even if our password character set is a single character (pass will let you do that, but obviously you should not use such passwords in real life) we're talking about statistically 1 out of 256 bytes matches or else our PRNG is useless. You correctly observe that the PRNG has finite state, but its state isn't so tiny that it only emits a handful of the 256 possible bytes before getting back to where it started, nobody would use such a busted algorithm. RC4 is considered broken and unusable because the keystream is biased and thus distinguishable from random - to the extent that if you read a few million bytes from it you can detect the bias, but you're asking us to imagine that the random device has a PRNG many orders of magnitude worse in order for this to have any effect at all.
  - wizzwizz4 5y ago
    > You correctly observe that the PRNG has finite state, but its state isn't so tiny that it only emits a handful of the 256 possible bytes before getting back to where it started, nobody would use such a busted algorithm. If the PRNG always loops through all possible states, then sure. But if there's a possibility, however small, of it getting stuck in a small loop, very rarely?
    - tialaramex 5y ago
      > But if there's a possibility, however small, of it getting stuck in a small loop, very rarely? We already went around this particular "small loop" so I'm guessing you aren't learning anything from repeating it. That would be a lousy design for a PRNG, so, nobody does that.
- GoblinSlayer 5y ago
  /dev/urandom isn't pure mathematics, it consumes hardware entropy.

But a nonzero possibility of running longer than x for any x>0 ;) In practice, it doesn't matter, I agree.

Assuming a perfect RNG, but PRNGs don't have infinite state. So it's either impossible, or has a finite probability, with a finite probability for each of those cases, for an overall finite (non-zero) subjective probability of it running forever (in ideal program-space; obviously it will never run forever in real life).

tialaramex 5y ago
No, you don't need a perfect RNG. You need anything that's not completely horrible. Remember, we're not trying to read a whole password from the device, just one matching byte at a time. So, even if our password character set is a single character (pass will let you do that, but obviously you should not use such passwords in real life) we're talking about statistically 1 out of 256 bytes matches or else our PRNG is useless. You correctly observe that the PRNG has finite state, but its state isn't so tiny that it only emits a handful of the 256 possible bytes before getting back to where it started, nobody would use such a busted algorithm. RC4 is considered broken and unusable because the keystream is biased and thus distinguishable from random - to the extent that if you read a few million bytes from it you can detect the bias, but you're asking us to imagine that the random device has a PRNG many orders of magnitude worse in order for this to have any effect at all.
- wizzwizz4 5y ago
  > You correctly observe that the PRNG has finite state, but its state isn't so tiny that it only emits a handful of the 256 possible bytes before getting back to where it started, nobody would use such a busted algorithm. If the PRNG always loops through all possible states, then sure. But if there's a possibility, however small, of it getting stuck in a small loop, very rarely?
  - tialaramex 5y ago
    > But if there's a possibility, however small, of it getting stuck in a small loop, very rarely? We already went around this particular "small loop" so I'm guessing you aren't learning anything from repeating it. That would be a lousy design for a PRNG, so, nobody does that.
GoblinSlayer 5y ago
/dev/urandom isn't pure mathematics, it consumes hardware entropy.