Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)

Subject: Re: IBM-PC random generator, source included
Message-ID: <1992Jun23.200511.27492@cactus.org>
Summary: Memory Refresh Produces Software Counter Phase Jitter
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+           <2677@accucx.cc.ruu.nl>
Date: Tue, 23 Jun 1992 20:05:11 GMT


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

 First, *without* the xor operation, we can expect a relatively
 constant bit-by-bit phase difference to accumulate, truncated to a
 single bit result.  That is, we would expect that the hardware would
 sample the software timer lsb with a relatively constant period
 measured in software cycle time.

 Normally, phase difference accumulates and when it passes a half-
 cycle of the lsb, will produce a bit-change discontinuity.  The
 question is how frequent and how repeatable these changes will be.

 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.

 By xoring 8 samples, the normal number of discontinuities per sample
 is increased by a factor of 8.  Thus, the simple patterns which I
 had expected will be obscured.  But the bit-change discontinuities
 will themselves be periodic.  The problem for analysis is to identify
 the phases of the various contributions well enough to predict bits
 based on the value of previous bits.  The best chance for such
 prediction is within a single 32-bit result, but then we have
 relatively few bits left to predict.  The phase delay to the next
 sample period should be relatively consistent inside a program, so
 once this is identified (approximately), it will take a few more bits
 of each sample to nail it down.  Discontinuities can be expected
 here as well.


>> Note that the claim of "two" oscillator crystals is limited to AT+

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

 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.


>My personal
>experience is there actually is "jitter" and I couldn't find any
>patterns even for huge collections of data.

 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.

 The real complication of the scheme is to use only a single bit from
 each sample, and then to xor 8 samples together.  This makes it very
 difficult to identify the internal state, and so predict the next
 bit.  Note that we could do the same thing with a simple LCG and
 make it far more difficult to break.  But this would not mean that
 such an RNG is really 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.  Worse, various areas
 of the state space will be "similar," and this is what we work with
 at the 32-bit result level, and between sequential results.  We might
 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
 solve the real problem.


 Nico's approach is interesting in that it demonstrates how we can
 use hardware to detect background operations and make use of this
 information.  But we could probably simulate such effects using
 equations in the foreground, given an equal amount of state data.
 Maybe the best thing we could do is to sample all three of the
 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.

 Alternately, it may be possible to find a similar approach in
 particular Unix environments, in which case multiple users and LAN
 interrupts could provide a never-ending source of true uncertainty,
 a few bits at a time.

 ---
 Terry Ritter    ritter@cactus.org