Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Re: IBM-PC random generator, source included Message-ID: <1992Jun25.071702.8945@cactus.org> Organization: Capital Area Central Texas UNIX Society, Austin, Tx References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org> + <1992Jun24.164407.28468@cl.cam.ac.uk> Date: Thu, 25 Jun 1992 07:17:02 GMT In <1992Jun24.164407.28468@cl.cam.ac.uk> rja14@cl.cam.ac.uk (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 language. >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. References: [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. 409-420. [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 ritter@cactus.org