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