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.

• 1993-02-25 Ian Collier: (some comments on RNG implementation)
• 1993-12-09 George Fuellen: The really clean definition of randomness is an asymptotic one . . . . There are no "random" strings, but there can be algorithms that have a "random" output.
• 1994-02-02 Herman Rubin: If you want something good enough for Monte Carlo, it is impossible to test for it, because to test, say, that the bits are accurate to .001, a sample of about 10^7 will be needed, and for any complicated Monte Carlo, this is nowhere near good enough. Mere testing is not good enough.
• 1994-10-18 Charles Stevens: I have produced some programs to analyise the "randomness" properties of a binary sequence.

Testing Hardware RNG's

• 1994-08-04 Ross Anderson: If you take a number of 32-bit samples, then you should start finding collisions (values sampled twice) after you have drawn about D = 2^16 samples, values sampled three times after about T = 2^22 samples (actually 3N^{2/3}), and so on.
• 1994-08-04 Terry Ritter: For any particular population, the number of doubles in a trial of a particular size follows a distribution which is Poisson-like. Thus, any single trial can have an extremely wide range of results.
• 1994-08-06 Terry Ritter: (Subject: Re: multi-sided dice for RNGs)

Maurer's Test

Is it the ultimate window on reality?

• 1993-12-03 Peter K. Boucher: Here's a little ditty that passes Maurer and is not random at all.
• 1993-12-07 Peter K. Boucher: I modified the Maurer test poster earlier by Dimitri Vulis to get rid of the Q input. Q is the number of ``random'' values to skip so that, hopefully, at least one of each value has been seen before the actual testing begins.

• 1994-05-14 Donald T. Davis: maurer points out that in calculating H = -1 * sum(p*log2p), you can replace p, a bitstring's probability of appearance, with the interarrival time between repetitions of the bitstring.
• 1994-05-16 Mike Scott: While not good enough to test for Crypto strength RNGs . . . any such generator should pass this test
• 1994-06-14 Donald T. Davis: please realize that entropy estimation isn't any more powerful at detecting structure than standard statistical measures are

• 1994-10-31 Steve Allen: How universal is Ueli Maurer's Universal Statistical Test For Random Bit Generators?
• 1994-11-01 Mark Johnson: Regrettably, Maurer's test does not reject the infamous RANDU algorithm.
• 1994-11-01 Donald T. Davis: an entropy estimate is necessarily a very imperfect measure
• 1994-12-10 Steve Allen: See Ueli Maurer's test: He claims, as I understand it, that this test reveals *any* weakness in a RNG due to memory
• 1994-12-11 Terry Ritter: (quoting Nick Maclaren) "It is important to note that universal tests have been known to statisticians for half a century, but are little used because they tend to be very weak."

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.

• 1994-06-17 Robert I. Eachus: AFAIK the only algorithmic RNG that can be considered secure and has reasonable performance is Blum, Blum, and Shub.
• 1994-06-18 Terry Ritter: The primary BB&S requirement for N = P * Q is that P and Q each be primes congruent to 3 mod 4. This is exceedingly easy. But to guarantee a particular cycle length (Section 8, Theorem 6), there are two more Conditions [1:378]. Condition 1 defines that a prime is "special" if P = 2*P1 + 1, and P1 = 2*P2 + 1, where P1 and P2 are odd primes. Both P and Q are required to be "special." Finding a valid special primes P and Q is not easy.

• 1995-03-08 Peter Kwangjun Suk: How about using the secure Blum-Blum-Shub quadratic residue generator with a 512 bit modulus? We could run a fast 64-bit block cipher in OFB mode, and occasionally flush the shift register and insert 63 bits from seven iterations of the BBS generator.
• 1995-03-13 Peter Kwangjun Suk: From what I've read, BBS is secure, both to the left and to the right, so long as you only use a few (~lg n) bits of each X_(j).
• 1995-03-15 Don Beaver: there may be very simple and very "efficient" *polynomial-time* attacks that predict BBS for n<1000000. Alexi/Chor/Goldreich/Schnorr would not be contradicted in the least. Such attacks would merely _eventually_ fail. *How big* n has to be is not a part of the theoretical rating. There is no theoretical support to deny the existence of "efficient," polynomial-time attacks on BBS for n<1000000.
• 1995-03-19 Robert I. Eachus: Huh? The original Blum, Blum and Shub paper proved that at least one secure bit could be generated each iteration.
• 1995-03-20 Peter Kwangjun Suk: Moderation on this group seems to have produced a false positive in this case.
• 1995-03-21 Don Beaver: These results are only *asymptotic* results. Their implications have been strongly misunderstood. They say, essentially, that any (polytime) algorithm that tries to predict a BBS generator using a window of 1 bit [or lg2(N) bits, if you prefer] will have virtually no advantage, *for large enough N*. They say nothing about the success or failure of polytime algorithms on N that have fewer than a few thousand bits.
• 1995-03-22 Don Beaver: (reply to Bob)
• 1995-03-26 Don Beaver: (reply to Peter) complexity-theoretic results can't be used to say that lg(512)-bit windows of a BBS generator are secure.

• 1995-10-06 Robert I. Eachus: The Blum, Blum and Shub algorithm is at least as difficult to predict as it is to factor the modulus.
• 1995-10-07 Nick Maclaren: PLEASE remember that this paper is SERIOUSLY flawed, and the technique is NOTHING LIKE as good as it is claimed to be.
• 1995-10-08 Herman Rubin: the generator is far too slow to be of much use, unless one needs fantastically good pseudo-random numbers, and can afford the cost . . . A Tausworthe generator like x[n] = x[n-460] + x[n-607] has period 2^(s-1)*(2^607 -1), where s is the word length; this is in integer arithmetic. This class of procedures are now known to have drawbacks.
• 1995-10-09 Arthur Chance Could you explain that last sentence?
• 1995-10-09 Herman Rubin: the bad example was such a generator with a largest lag of 1279. In an Ising model for which the results were known, simulation gave wrong answers.
• 1995-10-11 Robert I. Eachus: The second bag of tricks and the one that makes it all practical is to use the Chinese Remainder Theorem to allow you to do all of the computations with machine arithmetic operations instead of multiprecision.
• 1995-10-14 Nick Maclaren: (comments on Tausworthe problems)

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.

• 1994-02-24 Carl Ellison: For example, if ranno() were to return a number in the range 0..14 and x were 10, then (ranno() % x) would produce an element in [0..4] twice as often as an element in [5..9]. So, the distribution is not uniform.
• 1994-02-24 John Kelsey: Suppose you had a random number generator that always put out a uniformly distributed number between 0 and 10. Now, imagine trying to get evenly distributed decimal digits by taking the output of that function modulo 10. You'd get twice as many 0s as any other number, right?
• 1994-02-25 Eli Brandt: Related problem: you often see code like if (!(rand()%1000)) { ... } with the intent that the block be run with probability .001, which it won't be.
• 1994-02-25 Carl Ellison: (correction)

• 1995-06-01 Adam Back: Here's a method which I think solves this problem.
• 1995-06-02 Peter da Silva: Or what I usually do:
• 1995-06-05 Felix Schroeter: (comments)