Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Crystal Oscillators Thought Harmful Message-ID: <1992Nov3.191534.17573@cactus.org> Keywords: random number generators, really random Organization: Capital Area Central Texas UNIX Society, Austin, Tx Date: Tue, 3 Nov 1992 19:15:34 GMT In <68454@cup.portal.com> Tony_S_Patti@cup.portal.com responded to a request for a "physically random" RNG: >My enhanced RANGER Device meets the critical features# 1, 3, 6 (cost, >connectivity, and performance) as follows: >1. The parts cost is less than $40 (you can build it yourself). >2. Based on jitter from 16 crystal oscillators instead of alpha rays. Because crystal oscillators are *specifically designed* to be *highly* predictable, I find a crystal oscillator to be an odd choice as a source of randomness. A crystal oscillator module is basically a linear sinewave oscillator with a digitized output. Noise is inevitable during digitization of continuous signals, and, in a repetitive signal, that noise will appear as "phase jitter." Thus, some crystal oscillator "phase jitter" must exist. However, I expect this effect to be *extremely* small. We might well question whether one could reliably detect such an effect with cheap hardware. For example, in ham radio usage we may have a 20 MHz crystal oscillator with measurable 3 KHz sidebands due to noise. (Note that if we consider a spectrum analysis plot of such an oscillator as a probability density, these sidebands are so far "down" as to be quite improbable on a cycle-by-cycle basis.) A 20,000,000 Hz signal implies a 50 nsec period, but a 20,003,000 Hz signal implies a 49.9925 nsec period, a change of just -7.5 psec. We might expect a total +/- 7.5 psec variation (max). Measuring or even detecting such random events will be tough. Other than noise from active devices, I am aware of no physical basis for an assertion of inherent "randomness" in a crystal oscillator. Thermal effects, for example, are extremely slow and certainly not random. But if active device noise is the original source, why not just use diodes or transistors and avoid the middleman? Certainly, many combinatorial possibilities are available to a 16-oscillator circuit. But if the operation is oriented around the current state of highly-predictable sine-wave signals, it is basically similar to the usual *pseudo* random RNG, perhaps with a physically-random initialization. But even random initialization is problematic, considering that there is but a single power source, and any startup might well affect similar oscillators similarly. >Additionally, billions of the bits were tested -- and passed -- >the statistical tests outlined in Knuth I do not trivialize this. Testing is important and necessary. But we must also realize that it is impossible to show randomness by testing the result, just like it is impossible to prove the strength of a cipher by testing the ciphertext. We can prove *non* randomness, by finding a short description of the sequence and we can prove cipher weakness by finding a successful attack. But we cannot prove randomness or cipher strength unless we test every possible shorter description or attack. The number of potential patterns (all of which must be checked to show they are not present) is beyond our reach. So, we cannot prove randomness or strength by testing. Note that modern *pseudo* random RNG's *also* pass all the normal statistical tests. (Indeed, RNG's are *designed* to pass these tests.) Statistical testing provides no indication of "real" randomness. Because testing is limited in what it can provide, a detailed *analysis* of a design is *at least* as important as testing. Without such an analysis, I would assume that any purported "randomness" in a device based on crystal oscillators must be largely illusory. Indeed, a multi-oscillator device is that much more dangerous because combinatorial complexity may obscure an understanding that physical randomness is not present. --- Terry Ritter ritter@cactus.org