Newsgroups: sci.crypt
From: (Terry Ritter)

Subject: Re: IBM-PC random generator, source included
Message-ID: <>
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <> <>
+           <>
Date: Thu, 25 Jun 1992 07:17:02 GMT

 In <>
 (Ross Anderson) writes:

>The current flame war:

 Perhaps a frank exchange of views may seem like a "flame war"
 to some readers in more sanguine societies like the UK.
 I certainly do not consider such an exchange a "flame war."

 I hope I have not insulted anyone, nor the work of anyone,
 by pointing out that there exists no theoretical basis nor
 any known precedent for generating nondeterministic sequences
 on a deterministic machine.  This would not be a new design,
 it would be a major breakthrough.  Finding a useful
 nondeterministic aspect hidden in a normal computer would be
 a significant and important advance.

 It is important to be able to propose new ideas, and have them
 considered seriously from various points of view.  And it is
 especially important to be able to make mistakes without this
 becoming a social issue.

 If we have lost the ability to have a frank open discussion
 without having it demeaned as a "flame war," I think we have
 lost one of the main advantages of open communication.  We
 learn from our errors better than any quiet exchange of
 congratulation, and others find our errors better than we do.

 That said, communication between various societies may be
 trickier than we might expect, even when we use the same

>should be amenable to birthday testing.

>If Nico's generator does indeed approximate to a virtual state machine with
>less than 32 bits of state, then this could be detected by drawing at most a
>few hundred thousand samples and counting the number of doubles (and triples
>if any).

 Well, I know just about enough statistics to know that good
 statistical tests can be a lot trickier than they seem.

 Is this new work?  The "birthday test" is not a normal RNG
 test, to say the least [6,7].  It is not detailed in the
 extensive analysis in Knuth [5].  It is not a standard crypto
 RNG test [1,2,7].  And it is not one of the common statistical
 tests [3,4,8,9].

 I do have a reference to the "birthday paradox," with the
 equation for qn, the probability that no two of n random
 samples from m possibilities are the same:

         P(m,n)   m (m-1) (m-2) ... (m-n+1)
    qn = ----- =  -------------------------
          m**n    m   m     m   ...    m

 Given that we have m = 2**32, and n typically 10*5, I'm not
 even sure how to compute the probability.  I would like to
 see a discussion of this and its significance.

 It should be obvious that if we have a well-designed 32-bit
 RNG and use it to produce "a few hundred thousand" consecutive
 32-bit internal state results, there will be no duplicates at
 all.  A normal statistical RNG steps through (almost) its entire
 state without repetition.  But we may not agree that we have
 direct access to the entire state in Nico's design.

 Suppose we take the same well-designed 32-bit RNG and, for each
 sample, we accumulate 256 results, take only the lsb from each,
 and combine the resulting 256 bits into a single 32-bit value
 using XOR; wouldn't we expect duplicates?  Nico's extensive
 output processing is another unusual situation for an RNG.

 Let's do this, and compare the results.  Now, from "a few hundred
 thousand samples," can we distinguish between, say, 16, 24, 32
 or 40 bits (or more) of internal state in different RNG's?

 I dunno.  I'm dubious, but ready to listen.  (I'm also not at
 all sure how one does this on a DOS PC.)

 Normally I would run a number of Chi Square tests with, say,
 512 bins (use the top 9 bits) or mod 512 (use the bottom 9
 bits), but I doubt that would be acceptable in this case.


 [1] Beker, H. and F. Piper.  1982.  Cipher Systems.  Wiley.

 [2] Beker, H. and F. Piper.  1985.  Secure Speech
     Communications.  Academic Press.

 [3] Conover, W.  1980.  Practical Nonparametric Statistics.
     2nd Ed.  Wiley.

 [4] Crow, E., F. Davis, and M. Maxfield.  1960.  Statistics
     Manual.  Dover.

 [5] Knuth, D.  1981.  The Art of Computer Programming.
     Vol. 2, 2nd Ed.  Addison-Wesley.

 [6] Marsaglia, G.  1985.  A Current View of Random Number
     Generators.  Proceedings of the Sixteenth Symposium on
     the Interface between Computer Science and Statistics.
     Atlanta, March 1984.  3-10.

 [7] Maurer, U.  1990.  A Universal Statistical Test for
     Random Bit Generators.  Advances in Cryptology--CRYPTO '90.

 [8] Press, W., and others.  1986.  Numerical Recipes.
     Cambridge University Press.

 [9] Williams, F.  1992.  Reasoning with Statistics.  4th Ed.
     Harcourt Brace Jovanovich.

 Terry Ritter