5 ms·

I agree. Sounds like a number theory halting problem. Generate sequences of numbers continually, ad infinitum, and determine if distribution rates are (?). Ho

by ambiate 13y ago

I agree. Sounds like a number theory halting problem. Generate sequences of numbers continually, ad infinitum, and determine if distribution rates are (?). How would one begin to fill in that question mark? A PRNG that spits out three million 'zeros' and a single 'four' is as reliable as a PRNG that spits out an even distribution of random numbers.

claudius 13y ago
Isn’t the problem with detecting bad randomness that you can’t be sure about your decision? That is, if you accept a certain probability of falsely identifying a RNG as biased, I don’t see why this should be a fundamentally difficult problem, at the very least for the generator with four million 0s and a single 1: The probability that a good RNG spits out less than a thousand 1s in four million queries is negligible compared to the probability that it returns between 1.5 and 2.5 million 1s. Of course, it will be harder to detect more sophisticatedly broken generators, but still, without requiring certainty, it should be possible to make some sensible claims?
- Someone 13y ago
  For background info, read the art of computer programming, chapter 3. For practical help, see http://www.stat.fsu.edu/pub/diehard/ http://www.stat.fsu.edu/pub/diehard/ (linked from http://en.wikipedia.org/wiki/Diehard_tests http://en.wikipedia.org/wiki/Diehard_tests)
AaronFriel 13y ago
PRNGs are ultimately machines, they produce data from an input, even if that input is obscured from whoever receives the output. Statistical tests for randomness are still very valid and very important for PRNGs, and your dismissal of them is premature. Three million zeroes is so wildly improbable that any PRNG that for a reasonable seed value would produce such a sequence would be intensely scrutinized to determine if other seeds exhibited such behavior. If Dual_EC_DRBG exhibited that behavior, the cryptographic community's reaction would be swift. The issue here is the entropy of such a sequence is extremely low, and while low entropy PRNGs do exist, and they are not considered good for cryptographic purposes. If algorithmic weaknesses led to long stable and highly compressible sequences, or rather, sequences with a very low entropy (as measured by say, Kolmogorov complexity) would be considered suspect. Determining Kolmogorov complexity is itself a difficult problem, it's the problem of finding the shortest program (in a theoretical computer science sense) that produces a given output. And the complexity of that sequence is trivial, which is a huge problem for PRNGs. If every other seed had an extraordinarily high complexity with lots of hidden state, then maybe it would be considered, but I suspect not.
adsr 13y ago
Couldn't you run the same test (say) a few thousand times, then look at the distribution of numbers? Statistically they should be distributed evenly and be equally likely to appear for large enough runs. Any number or group of numbers that are consistently over/under represented should point to a bias as far as I can tell.
- dbaupp 13y ago
  For large enough runs, 0, 1, 2, ..., max, 0, 1, ... etc exhibits that behaviour. Thus, a PRNG that fails your proposal is bad, but passing it doesn't meanthat the PRNG is good. A test suite like diehard (or the moderner version dieharder) runs tests for uniform distribution as well as a lot of others, but even then, a pass is only saying "any glaring nonrandomness can't be detected by this suite".
  - adsr 13y ago
    Thanks, that's true but my comment was mostly a response to the "three million zeroes and a single four" as a valid random sequence comment. I wasn't suggesting it as a generic method to test the quality of a PRNG.

by ambiate 13y ago

claudius 13y ago

Isn’t the problem with detecting bad randomness that you can’t be sure about your decision? That is, if you accept a certain probability of falsely identifying a RNG as biased, I don’t see why this should be a fundamentally difficult problem, at the very least for the generator with four million 0s and a single 1: The probability that a good RNG spits out less than a thousand 1s in four million queries is negligible compared to the probability that it returns between 1.5 and 2.5 million 1s. Of course, it will be harder to detect more sophisticatedly broken generators, but still, without requiring certainty, it should be possible to make some sensible claims?

Someone 13y ago
For background info, read the art of computer programming, chapter 3. For practical help, see http://www.stat.fsu.edu/pub/diehard/ http://www.stat.fsu.edu/pub/diehard/ (linked from http://en.wikipedia.org/wiki/Diehard_tests http://en.wikipedia.org/wiki/Diehard_tests)

AaronFriel 13y ago

PRNGs are ultimately machines, they produce data from an input, even if that input is obscured from whoever receives the output. Statistical tests for randomness are still very valid and very important for PRNGs, and your dismissal of them is premature. Three million zeroes is so wildly improbable that any PRNG that for a reasonable seed value would produce such a sequence would be intensely scrutinized to determine if other seeds exhibited such behavior. If Dual_EC_DRBG exhibited that behavior, the cryptographic community's reaction would be swift. The issue here is the entropy of such a sequence is extremely low, and while low entropy PRNGs do exist, and they are not considered good for cryptographic purposes. If algorithmic weaknesses led to long stable and highly compressible sequences, or rather, sequences with a very low entropy (as measured by say, Kolmogorov complexity) would be considered suspect. Determining Kolmogorov complexity is itself a difficult problem, it's the problem of finding the shortest program (in a theoretical computer science sense) that produces a given output. And the complexity of that sequence is trivial, which is a huge problem for PRNGs. If every other seed had an extraordinarily high complexity with lots of hidden state, then maybe it would be considered, but I suspect not.

adsr 13y ago

Couldn't you run the same test (say) a few thousand times, then look at the distribution of numbers? Statistically they should be distributed evenly and be equally likely to appear for large enough runs. Any number or group of numbers that are consistently over/under represented should point to a bias as far as I can tell.

dbaupp 13y ago
For large enough runs, 0, 1, 2, ..., max, 0, 1, ... etc exhibits that behaviour. Thus, a PRNG that fails your proposal is bad, but passing it doesn't meanthat the PRNG is good. A test suite like diehard (or the moderner version dieharder) runs tests for uniform distribution as well as a lot of others, but even then, a pass is only saying "any glaring nonrandomness can't be detected by this suite".
- adsr 13y ago
  Thanks, that's true but my comment was mostly a response to the "three million zeroes and a single four" as a valid random sequence comment. I wasn't suggesting it as a generic method to test the quality of a PRNG.