Path: cactus.org!milano!cs.utexas.edu!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: <2677@accucx.cc.ruu.nl>
Date: 23 Jun 92 11:09:23 GMT
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
Organization: Academic Computer Centre Utrecht
Lines: 73
Terry Ritter writes:
>>It is a hardware based random generator (the hardware is the IBM-PC)
>>based on the jitter of crystals. To be able to "measure" it two crystals
>>are needed. Some extra tricks are needed to convert the partly deterministic
>>results of this fase to completely undeterministic data.
> 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.
> Potentially, random interrupts from some external source could slow
> the software counter irregularly, and yet have minimal effect on the
> counter/timer interrupts. But this would be a special situation.
The software has been made with no external interrupts (other than
those of the clock) in mind. Those external interrupts are
undeterministic and do therefore not damage the random generator.
> Note that the claim of "two" oscillator crystals is limited to AT+
> designs. In the original IBM PC, a single 14.318 MHz crystal was
> divided to provide clock to both the CPU and the timer.
I didn't know that. The PC on which I tried it did have 2 crystals.
A real pitty since this means it doesn't work on ALL IBM-PC
compatibles like I hoped. But if I understand right it does work on
ATs and better. Does anyone know if there are clones with a single
crystal as well?
> Also note that crystal oscillators are deliberately intended to be
> stable; they *resonate*, and do not "jitter" (usefully). Using one
> crystal oscillator to sample another must be expected to produce
> fairly repeatable results, even if the results seem complex. Far
> less stable oscillators correlate usefully; this is how hetrodyne
> frequency conversion works.
I have been afraid of this myself when I made the routine. After all
the purpose of a crystal is to generate a stable rate. My personal
experience is there actually is "jitter" and I couldn't find any
patterns even for huge collections of data. I presume if the only
thing my source measures is resonance the pattern should repeat itsself
in a reasonable short cycle or at least aproach such a cycle. I used
huge collections of output of the generator trying with hashed searching
(like used in modern data compressors) to find patterns beyond the
coincedental pattern repeats but failed to do so. I made very sure no
interrupts occured while performing the generation. (generation to
memory, no disk I/O, mouse etc).
> In practice, I would expect to see some bit-by-bit predictability
> within each 32-bit sample, unless we have other interrupt effects.
> Some analysis is certainly possible, but it could be tough.
I couldn't find any, even for multimegabyte sequences. Did anybody
succeed in finding sequences? If my "jitter" assumption is noncense
what would the cycle size be?
> 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)