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