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

[Benedikt Stockebrand]

And yet another one...

Joachim Strömbergson <joachim at secworks.se> writes:

> It seems that at least quite a few hobbyist (and some professional
> solutions) use transistors connected as diodes instead of a real diode.
> Any thoughts on that?

I've tried with some transistors I've had lying around.  The noise
amplitude wasn't as good as with the "magic" Zener diodes, I didn't find
any definite information about their breakdown voltages, and most
importantly: Zener/avalanche diodes are built for this kind of use
(reverse breakdown, that is), while transistors aren't.

So even if this worked, I'd be rather worried about the average life
expectancy of such a design.

> See for example:
> http://holdenc.altervista.org/avalanche/
> http://www.entropykey.co.uk/tech/
> http://forums.hackaday.com/viewtopic.php?f=3&t=4189
> http://emergent.unpythonic.net/01257868826
> http://www.robertnz.net/hwrng.htm
> http://robseward.com/misc/RNG2/
> http://code.google.com/p/avr-hardware-random-number-generation/
>
> (I think Fredrik has an even more extensive list)

OK, I'll start reading... tomorrow:-)

> One thing Fredrik highlighted is the long term behaviour/stabilty of
> this source.

Exactly.  That's why I opted for the avalance effect, rather than
constantly pushing transistors close to a permanent breakdown.

> This example has some data on this behaviour and tries to
> control the source.
>
> http://code.google.com/p/avr-hardware-random-number-generation/wiki/AvalancheNoise
>
> Another issue we have been discussing is how fast one really can sample
> a PN avalanche noise source. One suggestion has been that anything above
> a few hunderd Hz is not good.
>
> Any ideas about this Bernd and Benedikt?

I think I have to explain about how I do the processing:

I don't sample invididual readings, or xor a cluster of them or so.
That (kind of) works, but I found something way more robust: Measuring
the time between rising edges on that pin, or rather, the least
significant bit of that.

The disadvantage of this approach is that it can't be easily
parallelized, and I don't know if this is feasible in an FPGA.

But it means that if the noise source goes flat, the output will simply
stop.  If the source's frequency spectrum shifts, then the output speed
will adjust accordingly.  And since I implicitly only measure every
second wave, the bits read may be biased but they are effectively
uncorrelated unless I feed a fixed frequency signal insted of noise.
It also reduces the effects of outside interference, e.g. from 50/60Hz
sources, and should even make intentional interference attacks from
outside significantly more difficult.

Afterwards I use a simple von Neumann extractor to remove any bias and
at the same time compensate for any timing measurement from the previous
stage.  I've wondered if a changing bias (e.g. influenced by
temperature) might have any noticeable effect on it, but even if there
is, I found it impossible to measure.  If that ever turns out a problem,
more than two bits can be used in the von Neumann extractor to
compensate for that (but no, you won't find *that* in Wikipedia).

With the "magic" Zener diode, I took about a month's worth of output (40
GByte) and ran it through FIPS140-2 (rngtest from the Linux rngtools)
and dieharder with options "-Y 1 -s 1 -k 2 -a -m 3"[1] and some
follow-up testing on those tests that use a single psample and therefore
can't really cope with the "-m 3"---dieharder is a bit awkward there.
So I guess that 20 kByte/s are actually possible, and with a faster MCU
or an FPGA possibly even more.

By the way, those 20 kByte/s on the output side of the setup seem to be
rather constant; that's why I assume it's where the current MCU and
firmware hit their performance limit.


Have a nice weekend everyone,

    Benedikt

[1] -Y 1 -> Test to destruction, using increasing amounts of psamples.
    -s 1 -> Rewind input for every test.
    -k 2 -> Handle large psamples correctly.
    -a   -> Run all tests (even the broken ones...)
    -m 3 -> Triple the number of psamples.

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