Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Re: IBM-PC random generator, source included Message-ID: <1992Jun25.201323.20044@cactus.org> Organization: Capital Area Central Texas UNIX Society, Austin, Tx References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org> + <2808@accucx.cc.ruu.nl> Date: Thu, 25 Jun 1992 20:13:23 GMT In <2808@accucx.cc.ruu.nl> nevries@accucx.cc.ruu.nl (Nico E de Vries) writes: >I am not sure, like you claim, a crystal is fully deterministic. If you will look back at <1992Jun23.080147.15804@cactus.org> you will see: Also note that crystal oscillators are deliberately intended to be stable; they *resonate*, and do not "jitter" (usefully). My position is not that crystal oscillators do not jitter *at all*. At some level of measurement, virtually everything electronic is "nondeterministic." However, for practical purposes, using PC timers and software measurement, crystal oscillators do not "jitter." Crystal oscillators also drift, somewhat, in oscillation frequency, (although this would represent very little information). Such drift will be small, relatively repeatable and exponentially difficult to measure. But at least this might be *possible* because as we extend the measurement period we can pick up smaller and smaller effects. This is not possible for phase jitter. >- suppose the cycle time of a crystal is completely deterministic >- meaning there is a limmited cycle size for my random gen because of that >- suppose this cycle is long enough to be sure either > - the starting point in the cycle is non deterministic and the cycle > is shorter than the requered numbers > - in the cycle period something else but the crystals (temperature, > other devices, air flow from than fan) might add enough to make > the cycle non-deterministic (or much longer). Well, fine. Now show that this is true. It may be in this type of design that we have a generator which is nominally cyclic, with infrequent bit surprises. Technically, and measurably, such a generator would be acyclic. However, for cryptographic use, such a generator would be *practically* cyclic, and subject to analysis under those conditions. I note that you do promote your generator for cryptographic purposes. Actually, depending upon temperature and air flow seems far more repeatable and minor, and thus less random, than any attempt to use the external multi-user or LAN overhead effects that you don't like: >>That is another way of random generation which I didn't wan't to >>have. They work like "adding enough mess makes it random". I wanted >>... >I am not sure, like you claim, a crystal is fully deterministic. I do not claim that *anything* is *fully* deterministic. I do claim that crystal oscillators are deterministic within the stated environment. >But >supose it is, >postprocessing the output with MD5 (as I said before) should make >the random generator usefull enough for practical aplications. If you just want something which passes statistical tests, you don't need a hardware solution. Use a cryptographic RNG which has some degree of expected performance. Then your problem reduces to initializing that RNG. >So >even if crystals are deterministic it might still work. (well actually >is DOES work but we don't know why and how well it does). In <2670@accucx.cc.ruu.nl> you described the design as: Subject: IBM-PC flawless true random number generator This is rather difficult to misinterpret. To say that your design "DOES work" means that you believe that it generates "true" random numbers "flawlessly." I would like to know the basis for such a belief. I know of no way to identify "true" randomness by test. Statistical RNG's pass even the most strenuous statistical tests; since these tests obviously do not identify "true" randomness, they cannot be used to claim that your design "DOES work." Since you claim to be measuring crystal phase jitter, perhaps you would be good enough to explain in detail how your method can measure events of the expected magnitude in an environment which includes background memory refresh operations which you do not eliminate and do not compensate. Until you have some realistic analysis, you cannot validly say that your "flawless true random number generator" "DOES work," even to yourself. >> On the other hand, if we can measure the results of the uncertainty >> from external events, then we have a source of "real" randomness. >> (Or perhaps just access to an apparently infinite amount of state.) >In practice probably a mix is best. That would be mess (external) + >my algo + MD5. Probably noone can "break" that. If you are going to hide the sequence behind a cryptographic hash, I see very little reason if worrying about "real" randomness. If you have "real" randomness, you are already far beyond what MD5 can do for you. Otherwise, just init a statistical RNG and use that to run MD5. If you believe in MD5. --- Terry Ritter ritter@cactus.org