Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Re: IBM-PC random generator, source included Message-ID: <1992Jun24.184848.21881@cactus.org> Organization: Capital Area Central Texas UNIX Society, Austin, Tx References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org> + <2797@accucx.cc.ruu.nl> Date: Wed, 24 Jun 1992 18:48:48 GMT In <2797@accucx.cc.ruu.nl> nevries@accucx.cc.ruu.nl (Nico E de Vries) writes: >You don't seem to believe in the actual jitter. How do you explain >the many hardware boards with crystals which are crystal jitter >based to work? Of course I "believe" in jitter. I started out as a hardware person. It is not at all unusual to see a scope display jitter when retiming signals from different clocks in a computing system. That does not make the system nondeterministic. As for the boards which are supposed to work, I can only say that the simple presence of multiple crystals on a board does not mean that any nondeterministic aspect of the board is based on crystal jitter. Of course, the presence of 40 such crystals on a board does not make it nondeterministic either, but it does present a degree of complexity which could be far beyond our ability to analyze the current state of the system from its output. Actually, if one is going to sample oscillators with oscillators and hope for nondeterministic results, I would expect that we would find the absolute *worst* oscillators possible, instead of the best. High frequency LC oscillators come to mind, if we eliminate temperature compensating capacitors, and maybe we can even find operating conditions for which known transistors are predictably unstable. Maybe we can get oscillators to oscillate simultaneously on multiple frequencies which interact. Or maybe we could use unijunction oscillators. We want change, not stability. If we have a choice, we probably would not use oscillators at all (except one, for digital timing), since the whole point of an oscillator is to produce a repeatable result. >I doubth the DMA refress is non-deterministic, it might be VERY >complex to predict its effects but since it is clock triggered >and does a deterministic job it seems to me is is deterministic. My point entirely. We have a deterministic digital system which is difficult to analyze. That does not make it nondeterministic. >I carefully studied the working of hardware boards >which use crystal jitter as well before I made the program. I does >seem to me there is no undeterministic element in a single clock >environment. There is very little which could *possibly* be nondeterministic in a two clock environment: Suppose we have two crystals. After division and the effect of instruction execution, we have two cyclic processes, one controlled by each clock. In general there will be some non-integer ratio between the cycle time of the processes, but to get into the argument, suppose the ratio is 3:2. Thus, counting from the slower process we get: 1, 2, 1, 2, 1, 2, 1, 2, ..., OR 2, 1, 2, 1, 2, 1, 2, 1, ... Note that both results are the same except for phase. Also note that in every other cycle we have had a "jitter" in which the higher frequency from the other process makes itself known. Now assume that the ratio is 3.11 TO 2, and we get: 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, (or any other phase representation) as we find 31 counts in 20 sample periods. But it has taken 20 periods to get a resolution of 0.1, and it will take 200 periods for a resolution of 0.01 and so on. Naturally we will use binary, but it is going to be a very long haul to get more than, say, three bytes worth. Moreover, not all these bits are a surprise. Sure, upon coming on the system we do not know the ratios of its construction, but after diligent analysis we know the general ratios from the crystals, dividers, CPU clock, the instruction loop and CPU cache effects. There are multiple things to look at, but these are all completely deterministic. Thus, with proper analysis, we should already know the ratio to some precision, say 0.01%. So all these bits are useless as sources of non-randomness. On a given system, with particular physical clock crystals, there will be some variation based on the particular crystals themselves instead of the design. With exponential effort, we can measure the associated cycle ratios to desired precision. This will be relatively unique to this particular copy of the equipment. However, it will also be fairly repeatable. Again, not particularly random. >I presume the best way to verify the correctness of the algo >is finding out why it works (what you are doing) and than if it >works. I don't know what is the cause of the jitter in the crystals >many random generators(mine too) use. If it is a deterministic >process than the random numbers might not be real random. Right. There is a faint possibility (though unlikely) that the chosen cycle times are related, in which case we cannot even cover the entire state-space from any single init. The difficulty of analyzing the overall cycle length in this system makes it less desirable than various linear RNG's with massive nonlinear confusion of the result. (Like lsb decimation and the 8-fold XOR in this system.) Crystal oscillators do not "jitter." We see "jitter" when we retime one clock source to another. This is deterministic except for the precise frequency ratios, which are exponentially hard to measure by cycle counting, which are to some extent known, and in any case repeatable. >I don't exactly see where your numbers come from but if they are >correct changing the repeat counter into 24 should make the random >generator better? If you mean instead of XORing 8 samples we should instead XOR 24, then, no. This might make it more complex to analyze, but it cannot make the machine nondeterministic. This is essentially a nonlinear output processing step tacked onto a deterministic system. It would not even add any more state to the process. >> Nico's approach is interesting in that it demonstrates how we can >> use hardware to detect background operations and make use of this >> information. >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 >a random generator which could generate an unlimmited number >of random bits, no matter how stable the environment (e.g. >unused machine at night etc). For small random number needs >(e.g. the PKZIP encryption scheme) grabbing much info of >the current state might be enough. I think you should reconsider. This is a way in which we might get nondeterministic reality to manifest itself in a deterministic machine. We simply cannot hope to build a nondeterministic process from a deterministic machine, even if we use background hardware on a different clock. All a different clock can hope to add is a few exponentially more rare bits which differ from our expectations simply due to expected retiming effects between highly-stable digital clocks. 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.) --- Terry Ritter ritter@cactus.org