[Cryptech Tech] Hardware entropy

[Bernd Paysan]

Am Dienstag, 27. Mai 2014, 07:54:16 schrieb Stephan Mueller:
> I looked a bit into the code and found a number of questions:
> 
> - rosc.v: Unless I miss something, but it seems that you have only one
> inverter here. Is that correct?

An oscillator oscillates if it has an odd number of inverters, and enough 
delay to keep ringing.  The delay elements are the carry chain logic (fast and 
with a fixed relative placement; this helps to get good results without hand 
layout).  Technically, CMOS logic always inverts, so when you have a non-
inverting logic cell, it consists of at least two internal inverting elements.  
But as 1 is an odd number, things will oscillate even if these non-inverting 
elements wouldn't consist of two inverters.

> - entropy.v: the module instantiation with the following code seems to imply
> to generate 16 times two ring oscillators, correct?

Yes.

> Or do you build up the
> inverter chain here (but if so, how come that you have an even number of
> inverters)?
> 
>   genvar i;
>   generate
>     for(i=0; i<16; i=i+1) begin: tworoscs
>       rosc px(clk, nreset, rng1, rng2, p[i]);
>       rosc nx(clk, nreset, rng1, rng2, n[i]);
>     end
>   endgenerate
> 
> Now, if I understand the code correctly, you have 32 independent inverters
> which each is used to sample one bit, right?

Yes.

> If so, how do you counter the
> general problem that the inverters start to swing in harmony with a severe
> lack in entropy?

By characterizing the device.  That's what I've done with my measurements on 
the DE1 board: The frequencies of the different ring oscillators are all 
measured as independent, and they are not aligned.  I don't measure the actual 
frequency, I subsample it at 50MHz/16, and according to Shannon, I get a 
folded down frequency between these 0 and 3.125MHz; the real frequency is some 
x*3.125MHz higher (the x is not important for the actual entropy, because the 
jitter is the entropy source, not the stable part of the oscillation).

The theory is that when your sampling interval is big enough, the jitter 
caused an unpredictable clock drift, so that each sample is random.  The ring 
oscillators will have a bias, because it is difficult to make such a fast 
clock have a 50% duty cycle with all-digital delay elements (they aren't 100% 
symmetric).  If you want to cancel the bias, XORing two outputs will do; but 
this reduces the overall entropy.

> Shouldn't there be, say, one ring oscillator on the chip only? Or if there
> are multiple, their frequencies should be relative prime to each other to
> prevent the harmony?

No, the harmony is a theory of yours, and can't be seen in measurements.  If 
you have a theory, you have to perform measurements to support your theory.  
The measurements I've done don't support your theory.

There is for sure some intermodulation between the different ring oscillators.  
For one, the delays are not even, so the inverter at the start of the chain 
with routed wires has a significantly longer delay than the fixed carry 
elements.  Therefore, the power consumption will be high when the carry 
elements are flipping, and low when the routed wires flip.  This power 
consumption will slightly modify the freuqency of the other oscillators.

However, all these devices are quite small, and the automatic routing will 
cause the wire delays to be significantly different between different 
instances, so the base frequeny will have a much higher variation than these 
power supply induced changes: They are just anouther noise source.

> Another question which I could not figure out: What is the frequency of the
> inverter (chain) and at which frequency does the sampling occur?

I don't know what the frequency of the rosc is, and actually, I don't care 
enough to make the effort to measure it.  This is tricky, and deliberately so.  
I want a high frequency and a short chain to make sure the jitter is 
relatively high, because the jitter is one source of entropy.  The other 
source of entropy is the DFF sampling and having setup and hold violations 
(metastability).  Metastability here is another source of entropy.

You could probably feed the rosc into an asynchronous counter to measure the 
frequency; this is something I could try, and see if I get reliable, plausible 
results.

The sampling frequency (50MHz/DELAY_MAX) is the

parameter DELAY_MAX             = 32'h004c4b40;

and about 1/10s of a second.  I've sampled with one sample per 16 clocks to 
extract a meaningful folded down frequency and to see the jitter (frequency 
distribution).  That would be too fast to get well distributed entropy, but 
that is a good way to characterize the circuit.  IMHO this should be done 
first, and there might be some needs to change the delay chains to reduce too 
high biases or to increase the jitter (depending on which side of the equation 
you are).  The less the delay, the higher is the expected bias, but the jitter 
will also be higher, allowing faster readout and therefore more entropy.

> I would
> expect that there is a high oversampling rate (i.e. the inverters run at a
> much higher frequency than the sampling code).

Yes.

> How do you kickstart the inverters in case they do not start swinging
> immediately?

Metastability in deep submicron designs takes sub-nanoseconds to resolve.  
I.e. they will start swinging immediately.   And it will already ring during 
reset, because the reset state is active oscillation.

> Shouldn't there be some kind of dead-test or a wait for some
> time or wait for a number of ring oscillator swings before sampling the
> output?

Yes, there should be a stuck-at-1 or -0 test as part of the general entropy 
health test module.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <https://lists.cryptech.is/archives/tech/attachments/20140527/af8bf8cd/attachment.sig>