Subject: Re: Hardware RNG support for EM64T systems
To: Brett Lymn <blymn@baesystems.com.au>
From: Travis H. <solinym@gmail.com>
List: port-amd64
Date: 02/23/2006 07:18:11
```On 2/22/06, Brett Lymn <blymn@baesystems.com.au> wrote:
> Very nice.  I was thinking a little bit about doing the same sort of
> thing but packaging it in a rs-232 backshell.  Getting rid of stray
> EMI was something that worried me quite a bit though, and rightly so
> it seems :)

You might want to check out Terry Ritter's website, he has a bunch of
stuff on small/simple circuits for noise generation.

http://www.ciphersbyritter.com/

> Nup - you are fooling yourself.  You are forgetting the Nyquist
> Theorem.  With _any_ sampled data system you are implicitly throwing
> data from the analogue signal away, any frequencies above the sample
> frequency are implicitly mapped to below the sample frequency.
> Normally in a sampled data system you make your sample frequency two
> times higher than the highest frequency you are interested in.

Well, I agree, I'm familiar with the Nyquist theorem.

Although I should point out that you only get frequencies of f/2 for
in-phase waveforms.  For example, imagine a sine wave sampled at 0
degrees and 180 degrees - both would be zero, so a sine wave that is
out of phase with the sample clock is wiped out.  Conversely, if you
sample at 90 degrees and 270 degrees, then it is present at full
scale.  So the Nyquist theorem gives an upper bound, not a complete
characterization.

> Theoretically, white noise has an infinite bandwidth so any sample
> freqency you choose is going to band limit your noise - regardless of
> the resolution of your a/d conversion.  All it would buy you is more
> bits per sample period.

Well, my plan was to sample at 44kHz with 16-bit samples, as opposed
to sampling at 19.2kHz with a one-bit A/D (formed by two inverters).=20
I think the former could very easily uncover structures in the latter,
and you haven't convinced me otherwise.  Sure you're aliasing some
frequencies (not throwing them away I would say)... but cryptanalysis
is full of examples of non-random structure which were too complex to
notice right away but once detected could be used against the system.=20
Throwing information away can only weaken your analysis, it can't tell
you what someone with the full set could predict.  One could, for
example, make a random number generator by taking some long ASCII text
file and throwing away the upper seven bits of each byte.  That may
make it unpredictable to you, or anyone who only has access to the
least significant bits, but not necessarily to me; I have access to
all eight bits and can start to predict the subsequent values,
assuming that the text file has structure (i.e. is in English).=20
Actually that's a bit of a poor example since English text may have
one bit of unpredictability per letter, but I think you get the point.

> Regardless of the number of bits per sample, they should be amenable
> to fourier analysis which would easily show up any strong frequency
> correlations over time.

Yes as a matter of fact, the did do a fourier transform (the DCT I
think) and to their surprise they found an AM radio station!  The deal
was, they were powering the unit from an external lantern battery, and
the battery plus the lead to it were acting as a very primitive
radio*, injecting it into the noise, getting it into the digital
samples.  Playing the digital samples through a speaker was sufficient
to hear it.

[*] Some have theorized that the lead to the battery was in poor
contact and acted as a "cat's whisker", doing primitive AM signal
detection by acting as a diode.  I don't know for sure, but I have
found radio signals in the strangest places.

Now what if those samples had been fed through something as trivial as
a von Neumann corrector (discards identical pairs of samples)?  I am
not so sure the signal would have been so easy to detect, but I think
it is quite likely that it would require something more sophisticated.
However, I also think that knowledge that such a thing was present
could be useful against the corrected stream.
--
Security Guru for Hire http://www.lightconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484
```