[Cryptography] Duh, why aren't most embedded TRNGs designed this way?

[John Denker]

On 4/22/21 11:23 AM, Bill Cox wrote in part:
> To compensate, folks interested in more secure TRNGs for cryptography
> simply put multiple total crap TRNGs in parallel, and XOR their
> outputs together [...] I consider this to be n * totalCrap.

Yes, quite so.

> In the end some programmer gets asked to improve the rate of random
> data generated by the TRNG so that an embedded controller can boot
> faster, and this programmer, who doesn't know a thing about analog
> electronics simply looks at a hexadecimal string of bytes generated,
> and if it "looks" random enough [...]

Agreed, that's a problem.

>  pass the NIST entropy tests (also total crap), 
Agreed 99%.

///////////////

> Use two digital ring oscillators, which can be placed and routed in 
> an FPGA without worrying about how they are placed and routed. With 
> the first oscillator, clock a binary counter with enough to have 
> output bits that toggle with a delay long enough to accumulate 
> significant measurable jitter relative to the other counter. With 
> the other oscillator, clock a gray code counter, and record its 
> output on the rising edge of the appropriate bit from the binary 
> counter.

One ring oscillator is mostly useless for present purposes.
Using two of them is just (2 * mostly useless). This is the
same type of blunder that was condemned above.

A ring oscillator is basically a timekeeper. A good ring
oscillator would keep time accurately. The thing about
timekeepers is that what happens N ticks into the future
is very highly predictable based on what has gone before.

So we surmise that the objective here is to build a very
bad ring oscillator. That's hard to do. If it's possible
at all, it requires insane amounts of attention to detail,
including physics details that most chip designers know
nothing about.

> if only thermal noise causes the jitter. This should be measured by
> the host CPU continuously, as a health monitor.

There is no way to measure that. To paraphrase Dykstra,
statistics can prove the absence of randomness, but cannot
possibly prove the presence of randomness. So tests from
NIST or elsewhere are 99% useless (but not exactly completely
useless).

We agree that thermal noise is random, and should be the
focus of attention. So what we need is a way to capture the
thermal noise (aka Johnson noise) in a resistor. There are
direct ways of doing that. A ring oscillator is at best a
very indirect way of doing that.

We need to know the gain and the bandwidth of whatever is
capturing the thermal noise. That's not easy to do for a
ring oscillator. There are other approaches that are much
more direct, much more transparent.

> The deltas between gray code counter values form a normal 
> distribution 

That's just "whitening" of the kind that is scorned in RNG
design. It is just error /concealment/. It does not create
any new randomness.

>  - The distribution estimation should be updated continuously, as it
>  can drift with voltage, age, etc. - A filter continuously trained
> to predict the next output from several prior samples should be used
> to reduce the entropy estimate per sample

We agree that the estimation (if it were possible at all) would
have to be updated continually. The word "etc" is doing a lot of
work there. Usage of other circuits on the chip will introduce
interference, in ways that may be unknown, or known, or even
chosen by the attackers.

Another weakness here is that essentially all of the oscillator's
state is exposed to attackers under some circumstances. A better
design would spend some of its randomness and use one-way functions
to censor its state.

> This scheme should work well, assuming:
> 
> - One sample has negligible impact on a sample several in the future
>  (more samples than the trained filter has)

RNG design is a lot more complicated than that.

> Unfortunately, the assumption of independence of samples at least n 
> appart can easily be invalid.

Yes.