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

[Benedikt Stockebrand]

Hi once more,

since Fredrik keeps coming back for more anyway, I guess I might get
this off the table as well...

Bernd Paysan <bernd at net2o.de> writes:

> What kills diodes and transistors in reverse breakdown mode is heat, so with a 
> reasonable large resistor to limit the reverse current, transistors won't get 
> damaged, either.

Last night I tried a couple transistors; the BC337-16 got me the best
result with any THT component except of course for the "magic" Zeners.
I'll do some more systematic measurements towards the end of the week,
but at least I do have a working option for a THT implementation.

On the SMD side it looks even better; I'm currently running a longer
test that gives me 16kB/s, and the preliminary results look good.  We'll
know more reliably in about two weeks, when I've got enough output to do
a full dieharder run.

> That part is pretty easy to do in an FPGA: [...]

I thought so, but it's sure a good thing to know for certain!

> It shouldn't hurt if you measure high- and low-times.

I was just about to write that with the numbers below it does hurt, but
I think I have an idea: With I/O pin to indicate the beginning and end
of measurements, we could get away with 2*2 clock cycles per
measurement.  The rest could then be left to an oscilloscope probing
that pin.  But it'll still slow things down some.

> Hm, if you feed a square wave into the diode, [...]

Within the generator core, the capacitor in the generator core should
deal with that problem.

And beyond that, that's why I use the boost converter; it should handle
this problem, or die in the process.  If I used another source, like
+12V from a PC PSU, I'd at least add a fat LC filter.

Which leads to another interesting question: Is there a failure mode
that makes the generator core oscillate at a fixed frequency?  That
would be pretty nasty.

> If you measure LSB of a clock between edges, instead of sampling the input 
> with a constant frequency, bias shouldn't be a problem.

If the average number of samples between edges was converging towards
infinity you'd be right, but with on average six samples there is a
serious bias---enough to trip dieharder, and rather quickly so.

Here are the numbers: The output runs at 16 KB/s, so that's 128 Kbit/s.
With the von Neumann extractor that means 512K measured intervals/s, and
since I can sample at most every second interval, that means 1M
intervals/s on the input pin.  At 20 MHz clock speed, and 3 clock cycles
per sample, plus feeding the serial interface etc., that gets me on
average about 6 samples per measured interval.

> If the von Neumann extractor doesn't improve the quality of the random
> bit stream, leave it away.

It does, as I've explained above; but an alternative I've tried when I
was still in the tinkering stage was to measure the length of three
intervals instead of one.  That reduced the speed by about a factor of
2, but at least the faster tests didn't show any problem---with the
"magic" Zener diodes.

However, the important thing here is that the von Neumann extractor
ensures a very desirable behaviour when things go wrong: If the analog
section goes flat, then the von Neumann extractor ensures that the
device simply stops, rather than generating deterministic output; if its
input gets more heavily biased, the output will slow down rather than get
biased itself.

This balancing between speed and robustness is pretty much systemic in
this entire thing, and considering how difficult it is to ensure that a
HWRNG is actually OK, I'd rather keep it.

If we want some entropy-rich noise to seed a CSPRNG with, we might not
use the extractor, but since I also want a standalone HWRNG as for my
original plan, the extractor is about the best option I have for that.

> IMHO, the von Neumann extractor is not very helpful to improve an entropy 
> source; it reduces the bit rate by a factor of 4 if applied to a perfect 
> random bitstream (50% likelyhood that two consecutive bits are identical: they 
> get removed totally.  The other 50% likelyhood will output the first of the 
> two bits only).

With the numbers mentioned above, it's effectively a factor of 2 rather
than 4.  And with an iterative von Neumann extractor this could be sped
up by another factor of 2 again; only an MCU is too short on memory for
that.

> 20kB/s doesn't sound too bad.  That's nearly 200kBit/s, and as you use a von 
> Neumann extractor, it's nearly 800kBits/s raw data going into that extractor.

Well, let's say with a bit of luck about 130 kbit/s with some "not so
magic" component (current tests pending), but even then: The reason for
the extractor is to increase the robustness of the design, not
performance.


Cheers,

    Benedikt

PS: I've tracked down the problems I had with the Zener diodes to a
    broken Makefile.  That caused the MCU I used for the tests to run a
    firmware that wasn't using the edge measurement but just sampled $n
    readings from its input, XORed them and passed them on to the von
    Neumann extractor---with an $n minimized for the "magic" Zener
    diode.  It's fast and good if the Zener diode keeps up with it, but
    not exactly robust if you try to plug in a "less magic" Zener diode
    without adjusting $n, or that thing breaks or somehow ages.  The end
    result was that all "less magic" Zener diodes I tested failed the
    tests.

    Well, at least I now understand what happened...

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