Path: cactus.org!milano!cs.utexas.edu!sun-barr!olivea!samsung!uunet!mcsun!
+     sun4nl!alchemy!accucx!nevries
From: nevries@accucx.cc.ruu.nl (Nico E de Vries)
Newsgroups: sci.crypt

Subject: Re: IBM-PC random generator, source included
Message-ID: <2797@accucx.cc.ruu.nl>
Date: 24 Jun 92 09:44:18 GMT
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+           <2677@accucx.cc.ruu.nl> <1992Jun23.200511.27492@cactus.org>
Organization: Academic Computer Centre Utrecht
Lines: 101

In <1992Jun23.200511.27492@cactus.org> ritter@cactus.org (Terry Ritter) writes:


>>> Nico's RNG operates by incrementing a software counter in a tight
>>> loop.  Periodic hardware "tick" interrupts sample the counter and
>>> save the current value into an array.  The tick interrupt rate is
>>> increased by a factor of 64 to about 1165 ticks per second.  When
>>> 32 values have been collected, the lsb's of each saved value are
>>> extracted and returned as a single 32-bit value.

>>Not correct entierly. The process you describe is repeated 8 times
>>and the results of these are xored to return the final 32 bit value.

> I missed that, and it has some interesting implications:

>...
> There is an inherent jitter effect from the memory refresh DMA,
> but even at these sample rates we get 50 or so refresh cycles
> in each sample.  There will be a jitter of +/- one refresh cycle
> per sample.  Although the effect is *relatively* small, it could
> produce significant confusion in the results.  This could be the
> major source of apparent randomness.

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?

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.

> I think the "jitter" comes from the unknown phase of the background
> refresh operations instead of different clocks.  Single-crystal
> designs should produce similar results.

I don't think so. 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. Can anyone with a single clock please test the
code and tell us all the results? 

> The patterns produced in this scheme probably will not be detectable
> using standard statistical tests over the entire stream.  But most
> statistical tests generally do not detect significant non-randomness
> even in the simple linear congruential generators used in
> well-designed language RNG's.  If it is only necessary to pass such
> tests, there is no need for a hardware solution.

Correct. 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.

> The total state for Nico's scheme seems to be contained in: 1) the
> refresh counter-timer, 2) the interrupt counter-timer, 3) the
> software counter lsb, and 4) the period uncertainty when used in a
> particular program.  This will be 4.2 + 12 + 1 + 2(?) = 19.2 bits,
> and this is not enough to prevent analysis.  

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?

> increase the state-space by up to 7 bits by using the byte-parity
> of each sample instead of just using the lsb, but this will not

I don't see the advantage of this. The jitter can only be measured
when the last bit value changes (the time between two changes is
undeterministic). Thats why the repeat is there. 

> 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.

> timer counts and get about 32 really random bits *once*, then use
> those bits to seed a small cryptographic RNG which might be more
> difficult to attack.

Correct. Using e.g. MD5 is a usefull improvement to enhance the RNG.
For analyzation the "bare" generator should be used.

> Terry Ritter    ritter@cactus.org

Nico E. de Vries
_ _
O O  USENET nevries@cc.ruu.nl  FIDO 2:281/708.1  COMPUSERVE "soon" (tm)
 o   This text reflects MY opinions, not that of my employer BITECH.      
\_/  This text is supplied 'AS IS', no waranties of any kind apply.      
     Don't waste your time on complaining about my hopeless typostyle.

"Unfortunately, the current generation of mail programs do not have checkers
 to see if the sender knows what he is talking about" (A.S. Tanenbaum)