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)