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