Hacker News Reader

Comment by Someone1234 | Hacker News Reader

As a bit of a tangent: Does this happen semi-regularly because proving "randomness" is so difficult? Is there a system which can, with enough data, show that something is at least nth degree of randomness or is such a thing impossible mathematically?

View on HN

I would guess so, yes. You can never prove that something is random, merely that it behaves randomly "enough". There are lots of testsuites[1][2] you can run that will test that a generator is uniform and doesn't follow any patterns or has any other statistical weaknesses, but you can never prove that something is fully random without knowing the process that generates those numbers. A statistically sound RNG might just output the digits of pi, which would be non-repeating, uniform and pass any randomness test, but if you knew which digit the RNG started from and how many it has output so far you can easily predict the next one. Likewise if you're given a large enough sample you can search the digits to figure out the state of the RNG.

[1]: dieharder: http://www.phy.duke.edu/~rgb/General/dieharder.php

[2]: http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP80...

Statistical tests exist, but when it comes to cryptographic security, they are virtually useless. A statistical test attempts to examine a stream of bits and determine if they "look random" from a narrow, naive point of view, often predefined ahead of time.

On the other hand, a cryptographic adversary actively seeks to break the RNG, which may include tricks that statistical tests simply do not account for. As an example, the Mersenne Twister passes many statistical tests, but after observing 630 or so outputs, an intelligent adversary (with some math) can predict all future outputs of the RNG. That is not something a simple test can uncover.

So, essentially, if your RNG fails statistical tests, it is totally unworthy of any consideration at all from a cryptographic standpoint. If it passes all the selected statistical tests, good for it---all that means is that it might not be totally broken.

That isn't to say that statistical tests are without value. If they were in the build checking process, they could spot when the RNG has failed catastrophically, sometimes. They could not spot when cryptographic problems arise, though.

There are fairly standard statistical tests for randomness. They can't be 100% perfect (if it is truly random you can expect some results that don't look random occasionally) but with enough runs you can be sure to an acceptable degree.

It can't be beyond the wit of man to add such tests to automatic build and regression tests if the project has such a process in place, though it would potentially slow that process down depending on how you define the "acceptable degree" and therefore how aggressively you test.

Proving "randomness" is impossible, akin to finding the shortest program to reproduce a larger string (Kolmogorov complexity). Strings are Kolmogorov Random when they can not possibly be compressed any further by any program: Kolmogorov Random strings simply have no predictable information left to use for further compression. But Kolmogorov Complexity (KC) can not be computed, since that causes a paradox, much like "A description of the natural number that can not be described in less than fifty English words".

But we can of course talk about a degree of randomness, like we can also try to approach KC. Good randomness is all about unpredictability (given the first half of a random string, can you use that to predict the second half?), but that does not mean that proper randomness should be void of identifiable patterns (such as "00000000111111111" in a random binary string). Such orderly-looking patterns do appear in proper randomness, because the absence of those patterns would make the randomness more predictable, not less.

You can measure level of randomness with statistical methods [1], compression [2], visual methods [3] and die-hard tests [4]

[1] A simple method is the chi-square test.

[2] Compression ratio tells us something about the randomness. Random data can not be compressed by everyday-use compressors. That no one claimed the money for the challenge to compress RAND's digits in a binary file tells us something about the rigor that team had in coming up with random numbers. The more you can compress a string, the more order it contains and the more predictable it is.

[3] You can plot random points inside a circle. After a lot of points are added, you should see no patterns and a properly, evenly spaced circle. Another method are Moiré patterns: Take a field of random noise, copy it, slightly rotate it, and overlay. Non-random patterns will become more visible. But these patterns are visible without Moiré rotation too when using very basic PRNG's like the standard Python random library.

[4] The programmer's way of brute-forcing a lot of simulation runs to see if the PRNG works as expected: http://en.wikipedia.org/wiki/Diehard_tests

I’m curious about that too. How could you unit/regression test `rand`?

Statistic testing seems like it ought to work. However, I believe there's also the issue of actual uses of the RNG; it's not enough to test the kernel implementation, one must also test that libraries are using the implementation correctly (i.e. not using constant or completely-predictable seed), etc.

So it's not a trivial problem, because (among other reasons) nondeterministic, statistical testing is not well-understood in the testing culture.

Further complication: many RNGs will produce output as a function of their seed state (e.g., rc4 or chacha20). That output will look really good, even with weak seeds. You'll have a hard time detecting that two chacha20 streams were seeded with gettimeofday() for instance, unless you happen to check the exact time used.

assert(rand() != dummy_random_read_phony())

If dummy_random_read_phony() is rand(), that test will always pass. Almost every implementation of rand() will never return the same result in a row.

You use statistics. For example, take the birthday paradox problem and check if the collisions are higher than expected.

eh, I'm not sure that works. A random number generator of "return number++" will pass your birthday test.

I just gave an example. I never intended to say you just need this sole solution.

It's also a good lead for a further search query on the topic. Almost all test sets include a birthday test ;) For example this page: https://sites.google.com/site/astudyofentropy/background-inf...

Coming from just the data, I'd say impossible. It would be like achieving infinite compression on any pseudorandom data. There's no practical way to search through all possible short algorithms that could generate it.

With knowledge of the algorithm, you can do a lot more.

Reminds me of this old Dilbert cartoon...

http://dilbert.com/strip/2001-10-25

Reply on news.ycombinator.com