[Cryptography] The best TRNG architecture, comming soon?

[Bill Cox]

Ring oscillator based TRNGs suck, hugely.  They are the reason we have so
many RSA keys out there with one common factor.  They are hard to get right
because no one knows exactly how much entropy is coming from them, and
everyone wants to boot fast, so we read them too soon.

The best, but patented IIRC, architecture for a TRNG is super simple.
Since I'm not supposed to look at patents anymore, can someone take a look
and see when this circuit will be available for the world to use
unencumbered?  Here's a picture of the circuit:

[image: image.png]

In real life, you probably want to add more inverters than this.  This is
like a traditional ring oscillator, but with an *even* number of
inverters.  You take two inverters at opposite ends of the ring and turn
them into NAND gates.  The other inputs of both NAND gates are tied
together to make the ENABLE input.  When ENABLE is low, OUT is low.  When
ENABLE goes high, two edges in the ring oscillator chase each other.
Eventually, due to thermal or other noise, one edge catches the other, and
they annihilate each other.  The oscillator stops oscillating at this point.

To extract entropy, in a tight counter loop, poll the output.  When it is
stable for enough samples, say 32, the random output is the last loop
counter value where OUT changed.  Write  this value into the entropy pool,
and permute the pool (in Linux, just write it to /dev/random).  Repeat
until you have enough entropy in your pool.  The counter values form a
Poisson distribution.  The entropy per sample
<https://en.wikipedia.org/wiki/Poisson_distribution> is roughly:

    entropy ~= 1/2 * log(2πeλ) - 1/(12*λ) - 1/(24*λ^2)

However, a simpler rule is for counter values up to 100 million, you get
over  40% of log2(count) entropy per sample.  So, if you have a 12 bit
counter value, add 0.4*12 = 4.8 bits to your entropy estimate when you mix
in the counter value.

Advantages of this scheme vs the traditional lame ring oscillator that
causes IoT devices to get PWNed:

- Easy to estmate entropy per sample, due to a good physical model for
entropy.
- An attacker might lock the oscillator to their oscillator source, but
they cannot reduce the entropy in the output sample.
- If for whatever reason the noise in the this source becomes weaker over
time, it self-compensates by running longer.
- The layout matters little.  Just let the place and route tools place it
however it likes.

This circuit retains the nice properties of traditional ring oscillator
TRNGs, which make them so popular:

- Simle and tiny.
- Easy to implement on CPLDs, FPGAs, and ASICs.
- Purely digital: no analog design skills required.

I've forgotten how long the patent on this circuit will run.  It *might*
have expired by now, I have no idea.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20190825/4d062ce2/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 22336 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20190825/4d062ce2/attachment.png>