From: (Terry Ritter)
Newsgroups: sci.crypt

Subject: Re: hardware 2-oscillator RNGs
Date: 4 Aug 1994 16:19:41 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 109
Message-ID: <>

 In <31qi26$> (Ross Anderson)

>> 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 thre
>times after about T = 2^22 samples (actually 3N^{2/3}), and so on.

 Essentially what we are doing here is establishing a relationship
 between population and the number of "matches" found in trials
 of random samples.  But if we just sample until we start to find
 matches, the situation is more ambiguous than it needs to be.

 For any particular population, the number of doubles in a trial
 of a particular size follows a distribution which is Poisson-like.
 Thus, any single trial can have an extremely wide range of results.
 Clearly, a single test of this sort is not particularly useful;
 realistic tests must involve many trials.  But if the various
 trials take different numbers of samples, it is difficult to see
 the fixed relationship which is actually present.

 I call the usual match an "exact" or "binomial" double in my
 recent article [2]; these are predicted by the binomial formula
 (although Kullback's early work should be recognized [1]).  If we
 assume a particular population, the binomial formula can be used
 directly to give a probability of any particular number of exact
 doubles in a trial of any given size.  But the binomial equations
 are fairly complex and essentially one-way; it is not clear how
 the equations could be manipulated to produce a unique population
 value from the matches found in a trial of a given size.  Root-
 finding procedures can find multiple plausible populations which
 each satisfy the equation.

 But by changing our definition of "doubles," we can find a simple
 exact equation which we can use to predict population from the
 average number of "exact" doubles.  The desirable definition is
 the combinations of exact doubles taken two at a time, plus the
 combinations of exact triples taken two at a time, etc., a sum
 which I call "augmented" doubles.  Equation (2.3) [2:162] for
 Augmented repetitions (Ar) was printed incorrectly, and should be:

                 n     i
      Ar(k,r) = SUM [ ( ) ri ]
                i=k    k

 where k is the augmented level (doubles = 2) and ri the number of
 exact repetitions at level i.  An exact double implies an augmented
 double, but an exact triple implies three augmented doubles: the
 combinations of three things taken two at a time.

 Then we can predict the population (N) directly from the sample
 size (s), and the experimental augmented doubles (ad) value:

      Nad(s,ad) = s(s-1)/2ad

 For large numbers of trials and an average resulting ad, if the
 predicted population is not similar to the anticipated population,
 we have problems.  We can then run different experiments to try
 and isolate the problem, and then manipulate the experimental
 device to try and solve the problem.

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

 Yes.  Really-random generators must be experimentally tested, and
 they must be tested for population.

 Some problems are really not exposed by other tests.  For example,
 Chi-Square tests generally "bin" results and this will hide some
 problems.  Consider the situation of a population far smaller than
 it should be, but with values so evenly disbursed that several
 values make it into each Chi-Square bin.

 It is also possible that the local population could be inversely
 related to the probability of value occurrence.  This could lead to
 good average and Chi-Square statistics, despite a greatly-reduced
 population.  Since we usually depend on a large, homogenous
 population for security, such a result would be a problem.

 Another possible use for this technology is to test small "toy"
 versions of ciphers, to see if a particular cipher design has a
 tendency to produce fewer ciphertexts than one might expect from
 the anticipated population of keys.  It is not always possible
 to know that a keyspace is really as large as it appears to be.


 [1]   Kullback, S.  1976.  (first published 1938).  Statistical
       Methods in Cryptanalysis.  Aegean Park Press, P.O. Box 2837,
       Laguna Hills, CA  92654-0837  USA.

 [2]   Ritter, T.  1994.  Estimating Population from Repetitions in
       Accumulated Random Samples.  Cryptologia.  18(2): 155-190.

 Terry Ritter