[Cryptech Tech] Tesing of entropy sources in FPGAs

[Bernd Paysan]

Am Donnerstag, 12. Juni 2014, 09:39:49 schrieb Joachim Strömbergson:
> Based on this, it seems that having oscillators with designed different
> length of the delay path improves the quality. And/or having more
> oscillators affecting each bit. Also, my decorrelator seems to be pretty
> broken.
> 
> The next step for me is to try and improve on the fpga entropy source by
> adding a few more oscillators and see what happens. It would also be
> good to look at the tests that are failing, why and how to mitigate them.

Ok, my first question here is: What do you want to achieve?  This is a raw 
entropy source, which uses jitter and setup/hold time violations as source of 
entropy (i.e. as source of non-predictability).  This entropy source will have 
an inevitable per-bit bias, because rise and fall time delays are not 
identical, and therefore, the ring oscillator will not have a 50/50 duty cycle 
(even when people design a PLL, they rather divide the frequency by two than 
trying to achieve a perfect 50/50 duty cycle).  The duty cycle is further away 
from 50/50 the shorter the delay chain is; but the jitter, which actually 
produces the entropy, is higher then.  Therefore, reducing the chain length 
improves the entropy source at the cost of even distribution.  Even 
distribution therefore has never been a design goal, so there's no point in 
"fixing" this particular problem.

If you xor a short cycle rosc with a long cycle rosc, you will get something 
that has a significantly reduced bias (or almost no bias).  But it has very 
little additional entropy, as the long cycle RC oscillator has a low jitter.  
In other words: you just fooled 16 more dieharder tests, without really 
changing the actual situation (the entropy content of the signal still is the 
same).

The dieharder test is not made for entropy sources, it is made to test against 
perfect, evenly distributed randomness.  This isn't the right tool to check an 
entropy source against, because any small problem with a real entropy source 
like a bias will be found and reported as "not perfect".   On the other hand, 
e.g. AES in counter mode passes dieharder, but is perfectly predictable (even 
if you don't know the initial counter state - it is sufficient that you know 
the key).

One thing I'm focussing on is observability and experimental verification that 
the entropy source is actually the device it is supposed to be.  This means 
you have to read 2^n values out of each RC oscillator with a fixed frequency, 
FFT it and then verify how big the jitter actually is, and that the measured 
subsampling of the rosc frequency is roughtly a Gauss distribution.

If you add more things, it becomes more difficult to verify what it actually 
is, and therefore easier to replace with something else that is actually 
deterministic. Actually, if you look at your ent_fpga result, serial 
correlation incrased significantly; this is because the long chain ring 
oscillator has a low enough jitter to introduce a pattern into your result by 
toggling the bias of the short chain rosc - i.e. you remove the bias (as seen 
with the arithmetic mean being perfect), at the cost of adding a pattern 
(serial correlation reduced).

The post-processing of the entropy source to get it to pass dieharder is the 
conditioner, i.e. a cryptographic hash plus expand function.

The thing you have to proof for the entropy source is that it actually gathers 
entropy from a process you know is not under control from somebody outside, 
but is a physical process that is indeterministic by law of nature (e.g. shoot 
noise, metastability).  And that part is white-box testing.  That's what I did 
when I developed it, and that's what you have to repeat, as you somewhat need 
to characterize your device (which is not the same as mine, so it will behave 
somewhat differently).

My first recommendation would be that you split your data into the individual 
bit streams from each rosc, and compute the bias for each of them (and 
possibly run other statistical tests on them).  This should somewhat give a 
fingerprint of each device and probably also the place&route.

-- 
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/20140613/87001f96/attachment.sig>