[Cryptography] A TRNG review per day: Turbid

Bill Cox waywardgeek at gmail.com
Mon Oct 27 21:46:19 EDT 2014

On Mon, Oct 27, 2014 at 4:47 PM, Clemens Ladisch <clemens at ladisch.de> wrote:

> Bill Cox wrote:
> >  - A sound card used by Turbid cannot be used for input, meaning most
> users
> > need a second sound card.
> Quite a few sound devices have several independent inputs.
> > - Once a user is buying extra hardware for use as a TRNG, there is no
> > reason to use a sound card, when a TRNG designed for the purpose can do a
> > better job.
> Sound devices are widely available, and cheap, and do not require
> an additional driver.

Some TRNGs also require no additional driver (like the one I'm working
on).  If you use a well accepted USB interface chip, you don't need one.

Turbid ideally uses a 24-bit sound card, though a 16-bit might work.  I see
a Creative Labs Sound Blaster 24-bit audio card at New Egg.  Is this the
sort of card recommended?

> >  Sound outputs will be correlated when sampled at high speed.
> If the output contains _only_ white noise, there will be the same amount
> of noise at all frequencies, so the sample rate would not matter.

This is inaccurate.  White noise with energy in every frequency would have
infinite energy and destroy the universe.  Thank goodness for quantum
mechanics!  All white noise rolls off somewhere.  In this application, I
believe the frequency of interest is the cutoff frequency of the
anti-aliasing filter, which is somewhat lower than 1/2 the sample rate
(Niquist frequency).  That gives you a decent thermal noise estimate.

If you sample at the maximum supported sample frequency, you will do a
better job capturing the entropy that is there, but sampling at a rate
beyond the anti-aliasing filter cut-off frequency insures successive
samples are highly correlated, violating the Turbid paper's assumptions.
However, the results are still valid, if they correct for short-term
correlations, which can be done easily.

> To help correct for this short-term correlation, Turbid could keep the
> > history of the next sample given several previous samples. This would
> > give a good estimation of surprisal, allowing more accurate entropy
> > estimation.
> I believe that estimating the entropy (i.e., amount of white noise) of
> a sound signal cannot be done reliably without computing the FFT.

Let's use Turbid's definition of entropy (which happens to agree with mine
- what are the odds?).  Entropy is the expected "surprise" (a good word by
the way...) in a snippet of samples.  Surprise is log2(1/probability of
snippet occurring).  I wrote this exact equation a few days ago in my
entropy estimator code before reading the Turbid paper.

The correlation I am concerned about here is correlation that normally
exists between successive samples from the sound card, which can be quite
high if you are sampling faster than the anti-aliasing cut-off frequency.
However, drop a decade in frequency and the correlation is likely
negligible.  This can be done easily by sampling 10X less frequently, at
the cost of losing most of the entropy available in the sound stream.
Alternatively, we can estimate the surprise in each sample based on prior
history, and adaptively tune our entropy estimator.  A linear predictive
code based surprise estimator would work OK, though it would be optimistic
about the level of surprise in each sample.

In my TRNG, I have a 1-bit output, which lets me have a table of
probabilities of the next bit being a 1 or 0 based on the prior 14
outputs.  This enables me to eliminate all but a small fraction of the
nearby sample correlations from my entropy estimate.  The entropy estimator
matches the expected entropy of log2(K) to within 0.5% on the first three
boards I built (which I built yesterday - see
github/waywardgeek/infnoise).  The health monitor kills the process if
estimated entropy drops below predicted entropy by more than 5%.

Turbid, from what I read in the paper, does not adaptively estimate
entropy, which makes it's health monitor fairly weak, IMO.  Instead it
requires hand testing of the sound system to come up with a good entropy
estimate, which is then set for all time.  Is this right?  Is there any
adaptation at all?

Even if someone put my TRNG in a cryogenic freezer, it's entropy estimator
would adapt, and it would kill the process when it dropped more than 5%
below expected entropy.  However, because I effectively compress so many
bits of thermal noise together while it's still an analog voltage (about 15
bits in the first design), the temperature required to get a 2X drop in
entropy would be on the order of 293K/2^28.  This would drop the noise
voltage by 2^14, leaving only about 1 bit of noise in for every bit of
entropy out,

> >  The paper states:
> >
> >  "The least-fundamental threats are probably the most important in
> > practice. As an example in this category, consider the possibility that
> the
> > generator is running on a multiuser machine, and some user might
> > (inadvertently or otherwise) change the mixer gain. To prevent this, we
> > went to a lot of trouble to patch the ALSA system so that we can open the
> > mixer device in “exclusive” mode, so that nobody else can write to it."
> >
> >  Instructions are provided for patching ALSA.
> AFAICS the patch is missing from the latest turbid version, and the
> makefile references an ALSA version that is over ten years old.


> However, no patch is needed; locking mixer controls has always been
> possible.  Apparently, ALSA's documentation is, er, capable of
> improvement.
> Regards,
> Clemens
> Yeah... I have trouble with it myself when I get that into the sound
system.  I'm basically still a noob at ALSA, but whatever I've tried seemed
to require shot-gunning many different possible API call sequences to see
what combination does what I need.

This is another reason I am reluctant to use the ALSA sound system as an
entropy source that I count on.  How many of us can dabble in ALSA, and
understand thermal noise well enough to estimate accurately the noise that
must be there?  Now, adding it to the pool is a good thing, just like
adding entropy from RDRAND, but I think both should be set to add nothing
to the pool's entropy level.  That way, I don't have to worry about all the
mistakes I make all the time (like the ones I'm sure I made above).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141027/e38f4720/attachment.html>

More information about the cryptography mailing list