[Cryptech Tech] Tesing of entropy sources in FPGAs

[Bernd Paysan]

Am Dienstag, 1. Juli 2014, 14:55:36 schrieb Joachim Strömbergson:
> Aloha!
> 
> First Sorry for a _very_ late reply to this good mail.
> 
> Bernd Paysan wrote:
> > Ok, my first question here is: What do you want to achieve?
> 
> What I try to achieve is to develop an entropy source that:
> 1. Can be implemented within a FPGA with a reasonable good chance of
> working in different types and makes of FPGAs (Xilinx, Altera).
> 
> 2. Generates randomness with good enough quality to make it possible for
> a Cryptech user to convince him/herself that it works and can be trusted
> as one of the entropy sources feeding the rest of RNG chain.

Yes, that's fine.

> Point two implies that:
> - We must be able to point to and/or provide tools to allow the user to
> comprehensively test the entropy source(s).

That's something where you seem to miss the point.  The entropy source uses a 
noisy physical process.  It is *not* giving you true random numbers, it is 
giving you entropy.  An entropy source still is good when it has the following 
characteristics:

* It has a bias, i.e. the number of 1s is not equal to the number of 0s in the 
long run (this should show up as "fail" in any random number test)

* If you read it too fast, you get some sort of pattern: Especially this 
entropy source which bases on jitter will give show you that it has a 
frequency, which is just subject of some noise.  The entropy actually gets 
lower by reading less often, but there is a limit: If you cross that limit, 
reading more values will result in a diminishing amout of more entropy.

All this is not a problem for the entropy source: It still produces entropy 
(unpredictable results).  They are just not distributed in a way where you can 
run statistical tests designed for TRNGs on.

That's why you construct a TRNG out of two parst: The first part is the 
entropy source, which uses a physical process, and the second is a 
cryptographic conditioner, which converts the entropy into a stream of bits 
which pass the tests.

You guys seem to expect that the entropy source should pass these tests.  
However, please read FIPS SP800-90B:

http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf

The health test sums it up in one paragraph that those tests you've just run 
are going to fail with raw entropy sources:

"6.5.1 Health Tests on the Noise Source 
6.5.1.1 General Requirements 
The health testing of a noise source is likely to be very technology-specific. 
Since, in the vast majority of cases, the noise source will not produce 
unbiased, independent binary data, traditional statistical procedures (e.g., 
monobit, chi-square, and runs tests) that test the hypothesis of unbiased, 
independent bits almost always fail, and thus are not useful for monitoring 
the noise source. In general, tests on the noise source have to be tailored  
carefully, taking into account the expected statistical behavior of the 
correctly operating noise source."

This draft contains a number of statistical tests which estimate the actual 
entropy of an entropy source, which is usually <1 (the bits are not perfect 
random bits).

This draft has more tests than I use: I rely on a histogram to estimate 
entropy (the most frequent or lest frequent fixed-length sequence gives you a 
lower bound on the entropy), and FFT to see if the base frequency is 
sufficiently high vs. the sample frequency so that only the jitter noise is 
measured.

Therefore, to let the user gain trust in the entropy source, the first thing 
you need to do is to repeat my initial measurements: Read out the values at a 
fixed subsampling frequency, fast enough to actually show that the ring 
oscillators are oscillating, that the oscillation frequency has a jitter (i.e. 
the FFT shows a spread with roughly Gauss distribution), and that there is a 
noise floor as result of setup and hold time violations (that's expected).  
The DC component of the FFT shows you how the output is biased (it will be, 
and this is not a problem, as long as the bias is relatively small).

If you see that kind of behavior, you can calculate a first guess about how 
much entropy the source realy delivers.  And then you can do more tests:

* Reduce the sampling frequency so that no obvious peak is showing up in the 
FFT: This maximises the entropy you can get out of this source.

* Calculate a histogram of subsets (e.g. bytes) of the bitstream each source 
gives you

* Do statistical tests on those, which all give lower bounds of the entropy 
the source is emitting - the FIPS document above has several equations which 
base on such a histogram output.

> - We (at least I do) assume that Cryptech will provide several (at least
> two) different types of entropy sources, and in a reference
> implementation will use more than one entropy source and not of the same
> type.

I'm fine with that.

> > 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).
> 
> No, this is not correct. Dieharder does not assume anything about the
> source of the randomness. Diharder has been and is used for evaluating
> TRNGs (i.e. enropy sources with our without whitening), hybrid RNGs with
> entropy sources feeding CSPRNGs which generates the data as well as pure
> algorithmic generators.

You are really mistaking TRNGs with entropy sources (or you want to limit 
yourself to "full entropy sources", which is IMHO not a good idea).  An 
entropy source is *not* a perfect TRNG.  It just provides you with some 
entropy, usually less than "perfect".  Perfection is not necessary for the 
entropy source.

> There are test suites that are simpler and easier to implement as online
> tests, for example SBI AIS-31 and FIPS 186 (basically stuck at fixed
> value tests). And Dieharder shares tests with for example FIPS-140 and
> AIS-31. Diharder is simply the most comprehensive test suite that we
> (AFAIK) have.

Yes, it is very comprehensive.  But it is for something else, not for raw 
entropy sources.

> I agree that Dieharder contains tests that may be hard for some entropy
> sources to match. But a really good entropy source treated as a black
> box should generate randomness with good quality.

No.  That's not the point of an entropy source.  The point of an entropy 
source is to access a physical process that is unpredictable.  The 
*measurements* of this process will have predictable components like bias.  
And this sort of bias and stuff is not a problem.

In general, when you do cryptography, "black box tests" are only of limited 
use.  The attacker knows the inside, so he will use all knowledge he can have 
to break your stuff.  The crucial part is that even with full knowledge he 
can't break it.  For deterministic parts, you have to keep your keys secret, 
for indeterministic parts, law of nature keeps you safe.

> A random distribution
> with a bias is not good - no matter if it is generated by an algorithm
> or by sampling a physical process.

No, point missed.  Biases in measuring physical processes are very frequent 
and expensive to avoid, and it's not even harmful for the entropy source if it 
has some bias: You just need some more bits to get the entropy you want.

> Re you comments about AES-CTR and state knowledge. Anybody having full
> control/knowledge about the individual frequency of each digital
> oscillator, their duty cycle and their variances would be able to
> predict with a high degree what the FPGA entropy source generates.

No, not at all.  That's the entire point about random variances: You can't 
predict them.  The point of an entropy source is that it produces 
unpredictable output, unpredictable in a sense that there are physical laws 
that fundamentally prevents you from predicting actual results.  You still can 
make statistics, though.

An entropy source is good if you can have full knowledge, and it still won't 
help you.  You even should have that fulll knowledge, because it gives you 
confidence that the entropy source works as advertized.

> The
> point is that what we try to do is make that knowledge and that
> predictability really hard.

Knowledge and predictability must be orthogonal.  You must have 
unpredictability despite of having full knowledge.  Otherwise it's not an 
entropy source.  That's why I'm saying you need to characterize your device, 
using fast constant frequency subsampling and doing FFT over the results.  
That will give you an overview how big the jitter spread is, and that the 
frequencies are not all aligned.  This is the necessary stuff you need to know 
about a ring oscillator based entropy source.

> No matter if it is our entropy sources or
> the CSPRNG at the other end of the chain.

The CSPRNG is deterministic and therefore has other properties: Its input and 
internal state must be kept secret.  Then, its output seems to be 
unpredictable - the efford to predict it is the same as to break the 
cryptographic algorithm.  The entropy source doesn't have this property: The 
effort to break it is infinite (when you generate an infinite output sequence, 
the likelyhood to guess each bit is porportional to the entropy per bit, while 
in the CSPRNG case, all you need is to obtain the key).

> For me the important thing in point 2 above is provide means for a user
> to test the entropy source. If you have a good suggestion or even code
> that a user can use to do testing it would be great. Similarly for
> implementations of AIS-31, FIPS-140 etc. The more test the better (imho).

The stuff I have is code to calculate FFT and to generate a histogram, on 
which you can do some more entropy estimation calculations, as per FIPS SP 
800-90B.  Unfortunately, there hasn't been much work done on testing raw 
entropy sources, which is why 800-90B is a pretty recent draft, and contains 
not many tests, and no formalized test suite like Dieharder.

I think the "more work to do" is to write a suite that at least puts the tests 
in FIPS 800-90B into a framework you just can run on the data.  Plus the FFT 
tests I like to do (these are specific to ring oscillator entropy sources).

> Like this:
> > 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.
> 
> Good points. We need to codify it and make it possible to be easily
> repeatable.

Yes.

-- 
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/20140701/d9fa6ae3/attachment-0001.sig>