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