Path: illuminati.io.com!uunet!pipex!lyra.csx.cam.ac.uk!rja14
From: rja14@cl.cam.ac.uk (Ross Anderson)
Newsgroups: sci.crypt

Subject: Re: hardware 2-oscillator RNGs
Date: 4 Aug 1994 11:05:42 GMT
Organization: U of Cambridge Computer Lab, UK
Lines: 43
Message-ID: <31qi26$4js@lyra.csx.cam.ac.uk>
References:  
NNTP-Posting-Host: ouse.cl.cam.ac.uk

In article , jathomas@netcom.com (John A. Thomas)
 
writes:

(description of hardware deleted)

> Statistical tests show good results.  For long files (>100K) a slight 
> predominance of "1" bits begins to affect the results.  Probably a result 
> of some sampling artifact, but I haven't tracked it down.  Anyway, 
> XOR-ing successive bytes together eliminates this.

It is also useful to check the diversity of the generator. If you take a 
number of 32-bit samples, then you should start finding collisions (values
sampled twice) after you have drawn about D = 2^16 samples, values sampled three
times after about T = 2^22 samples (actually 3N^{2/3}), and so on.

> AT&T used to make a RNG chip, the T7001, which used the phase jitter of a 
> free-running oscillator to generate random numbers in a similar way.  I 
> was recently told that this chip is no longer manufactured.

There was also an Intel chip, the KEYPROM, which used this kind of random number
generator to produce session keys. This definitely did have a diversity problem
- strings of zeroes were far too common.

The point is that, quite apart from sampling artefacts, circuits can have all 
sorts of strange resonances; many of these are not immediately visible to the 
naked eye. Even transient resonances (which may have been part of the Intel
problem) can make it much more likely than you hoped that your generator will
produce two keys which are the same or which agree in a large number of bits.

The theoretical background to this is the capture-recapture problem in statistic
s
(estimating the number of fish in a lake by capturing and ringing them) [1]; the
Intel KEYPROM is described in [2].

Hope this helps

Ross

[1] Schnabel ZE, ``The estimation of the total fish population in a lake'',
    in American Mathematical Monthly, v 45 (1938), pp 348 - 352

[2] Letham L, D Hoff and A Folmsbee, ``A 128K EEPROM Using Encryption of
    Pseudorandom Numbers to Enable Read Access'', in IEEE Journal of
    Solid State Circuits, v SC-21 (Oct 1986) pp 367 - 392