Randomness Tests; Blum, Blum & Shub

General References on Testing RNG's

  1. Beker, H. and F. Piper. 1982. Cipher Systems. Wiley. 169-174.
  2. Beker, H. and F. Piper. 1985. Secure Speech Communications. Academic Press. 104-109.
  3. Carroll, J. 1989. The binary derivative test: noise filter, crypto aid, and random-number seed selector. Simulation. 53(3): 129-135.
  4. Feldman, F. 1990. Fast Spectral Tests for Measuring Nonrandomness and the DES. IEEE Transactions on Software Engineering. 16(3): 261-267. (Also in Advances in Cryptology -- CRYPTO '87.)
  5. Knuth, D. 1981. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms, 2nd Ed. Addison-Wesley. 38-110.
  6. L'Ecuyer, P. 1992. Testing Random Number Generators. Proceedings of the 1992 Winter Simulation Conference. 305-313.
  7. Marsaglia, G. and A. Zaman. 1993. Monkey Tests for Random Number Generators. Computers & Mathematics with Applications. 26(9): 1-10.
  8. Marsaglia, G. 1985. A Current View of Random Number Generators. Proceedings of the Sixteenth Symposium on the Interface between Computer Science and Statistics. 3-10.
  9. Marsaglia, G. 1985. Note on a Proposed Test for Random Number Generators. IEEE Transactions on Computers. c-34(8): 756-758.
  10. Maurer, U. 1990. A Universal Statistical Test for Random Bit Generators. Advances in Cryptology -- CRYPTO '90. 409-420.
  11. Mund, S. 1991. Ziv-Lempel Complexity for Periodic Sequences and its Cryptographic Application. Advances in Cryptology -- EUROCRYPT '91. 114-126.
  12. Newman, E. 1951. Computational Methods Useful in Analyzing Series of Binary Data. American Journal of Psychology. 64: 252-262.
  13. Richards, T. 1989. Graphical Representation of Pseudorandom Sequences. Computers & Graphics. 13(2): 261-262.

Randomness Tests

Everybody has a favorite.

Testing Hardware RNG's

Maurer's Test

Is it the ultimate window on reality?

I sure didn't do a very good job formatting that last message, but as you can see it was basically just the earlier messages, plus one other reference. I included very few of my own comments. But apparently someone didn't like the implications, and sent that message to Ueli Maurer, perhaps with some goading comments. I consequently had a brief, sharp exchange with Ueli in private e-mail. Now, Ueli Maurer is a well-known, respected and very accomplished researcher in cryptography, and I have no "hidden agenda" either to damage his reputation or to improve my own at his expense (I am not an academic and need play no petty academic games). But in this particular case, the Title and Abstract of the paper can be extremely misleading to those not deeply involved with these particular issues.

  1. First of all, Maurer's paper is intended to apply to physically-random generators, and specifically disclaims the ability to test "software" RNG's. But randomness tests apply to sequences, not generators. How does the test know where a sequence comes from?

  2. Suppose we do test a physically-random generator. Also suppose that the fault in that generator is that it is a software-like state-machine. (Generators based on a multitude of crystal oscillators might be a good example.) It is not satisfactory for a test to pass such a sequence because the physically-random generator internally behaves in a way to which the test does not apply.

    Indeed, I would argue that even physically-random generators should be considered to be state-machines with essentially infinite state. (For one thing, this allows us to avoid "mystical" answers about the ultimate source of ever-increasing entropy.) This would mean that both "physical" and "software" RNG's could be analyzed on the same continuium.

  3. The Maurer test supposedly delivers the "entropy" of a sequence.
    Q: What is the entropy of a 32-bit RNG?
    A: 32 bits.
    If the entropy estimator does not get this, or if it takes impractically long to do so, it is not a very good estimator, or it is measuring some other definition of "entropy." But Mark Johnson (above) tells us that this test does not reject a well-known problem generator with minimal internal state.

    This is how we check randomness tests: We generate sequences with known characteristics and then measure them. Tests which fail are just failed tests. Failed tests are precisely what we do not use to analyze sequences with unknown characteristics. And new physical RNG designs or implementations are often rife with potential problems.

I consider the Maurer test to be another statistical test, useful for investigating it's own particular view of randomness. I do not, however, consider it to be a complete report on any possible problem in the generator, even in a physically-random generator.

Blum, Blum & Shub

Basically, the function x^2 Mod N used iteratively. The attraction is a proof of "unpredictability," which seems like it would solve "the" stream-cipher problem.

There are both theoretic and practical problems: The proof is asymptotic, and therefore provides no guidance as to the size of N needed for "unpredictability." (Presumably, it requires RSA-size values.) Practical problems include the need for other restrictions on P, Q (N = PQ), finding P,Q, and selecting x0.

Unbiased Range Reduction for RNG's

Suppose we have a RNG which produces values with a uniform probability of selecting any particular value in its range. Then suppose we want a lesser range. There are several wrong ways to do this.

Terry Ritter, his current address, and his top page.

Last updated: 1995-12-28