[Cryptech Tech] User auditable hardware entropy source/random number generator

[Benedikt Stockebrand]

Hi folks,

Bernd Paysan <bernd at net2o.de> writes:

> I think you can use more of the hardware of an MCU, if you want to (what 
> Benedikt actually does is explained in his reply).  The signal of such a diode 
> is white noise in the analog domain.  So to extract the most entropy out of 
> it, you amplify it so that the signal still fits within the range of the ADC.  

I've tried the ADC of an ATmega1284 early on but found it to be rather
slow, so I didn't pursue that option any further.

> You now can measure the ampliude of the signal, and you will get about 7 bit 
> of entropy per byte sampled.  

If you take several bits of output, they are in all likelyhood severely
correlated within that sample.  And if you take samples too quickly,
then the bits between samples do get correlated as well.

> Some people have reported that this diode noise is good for up to
> around 1 MHz,

I found some references claiming 300 MHz.  And judging from what I've
seen on the scope, it looks like there are huge differences in the
spectrums ("spectra"?) of different diode types.

> so you could sample with 2 Megasamples per 
> second, which gives you somewhat nearly 2 Megabytes of entropy per
> second.

>From what I've seen with the non-magic diodes (of which I've now got a
pretty selection) I'm a bit sceptical if you can get more than about a
quarter bit of entropy per sample.  You might capture more noise, but
you'll throw most of it away afterwards anyway.

BTW, just to avoid unnecessary confusion: When I say "random"
bit/bytestream or "entropy" or such, I mean actually processed data
without bias or correlation; anything before that I call "noise".  I
don't remember where I picked that up, but it made sense to me and I've
got rather used to it.

> As usual, YMMV, so doing some fast sampling first and then figuring
> out what you can usefully do is the best approach.

Basically, sampling at a speed anywhere near or above the average
breakdown frequency won't win all that much, because the timings of the
breakdown and recovery are what introduces the entropy; the rest should
be too deterministic to contain any significant entropy.  Again, that's
why I use edge-to-edge measurement.

> [...]
> So the next stage is to feed this raw code into a hash, and compress it 
> somewhat, so that you now get digital white noise out.  This part is identical 
> to what we need for the ring oscillator noise, too.

The problem here is that you don't really know how much entropy you've
actually got, and what is actually bias/correlation hidden by the
hashing.  This leads to the problem with the Yarrow algorithm's entropy
estimator: You have to estimate the entropy while you've effectively
made it impossible to measure it properly.  Fortuna no longer needs an
entropy estimator, but going without a way to reliably measure the
amount of entropy from some source is still like being blindfolded.


I've started some sort of report on the results I've got so far, but I
guess it'll take some time until I get to the testing methodology.  So,
in a nutshell:

In my opinion the best approach is to take whatever noise, then extract
entropy from it in such a way that any failure on the noise source gets
cleanly propagated to the output, then do whitebox testing for these
failures and pass the rest on as reliably random.  This is generally
what you'd expect from a /dev/random device on various (but not all)
Unixes; only after this is reliably done it makes real sense to feed its
output to a CSPRNG (aka.  CPRNG, in case I fall back to the terminology
I've become used to) like Fortuna to cater for /dev/urandom.


Cheers,

    Benedikt

-- 
Benedikt Stockebrand,                   Stepladder IT Training+Consulting
Dipl.-Inform.                           http://www.stepladder-it.com/

          Business Grade IPv6 --- Consulting, Training, Projects

BIVBlog---Benedikt's IT Video Blog: http://www.stepladder-it.com/bivblog/