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: Wed, 24 Jun 1992 18:48:48 GMT

 In <> (Nico E de Vries)

>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

 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

 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