[Cryptech Tech] Tesing of entropy sources in FPGAs

[Joachim Strömbergson]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

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.

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).

- - 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.


> 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.

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.

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

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. The
point is that what we try to do is make that knowledge and that
predictability really hard. No matter if it is our entropy sources or
the CSPRNG at the other end of the chain.

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).

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.

- -- 
Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
========================================================================
 Joachim Strömbergson          Secworks AB          joachim at secworks.se
========================================================================
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.22 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBCAAGBQJTsq/IAAoJEF3cfFQkIuyNXy4QANX8l85nfHix2LgeNcoMRjHo
Ipwj5kpd/rnWHLxVHUZDpBeOHGZ4dM5TtZyStAYPAh7S8CPNyildhIUU8Jw643lG
ULuEcByBI7WukAMiXLgi+bTdVDOX7f+oo65H8YV+2UtVaov2XHDAYkBY1QQkMF0c
3Y9B0GCmfzHBWotW5aamw1JqkkwMQFeq+ErTPj+hHDLp8o47cWNIb+9vqt1YKBoy
Vf9I4SB2Vw/9VN0ITNjWhyP9pA7wV4RVT3j2L9uTSAZKSvz1p7HS5uqb9R1qiueS
FR1pqefmn4eKjzIWXsbYh108PTPBdE3pP83OfrSeUPAbvOV7A/eemdYweIEnCKvK
+IgPGgtQVDzXlJ0r5ytrO8l7Y/ORX8zT0HnnHztiknT3zvncm4PrmzqwarKGCBOa
TrAWowUAF9ljmQA/b86otDlADP/F7goMRMhQjg4VILioHCzt6GLued8fViDR4iLv
UKyPd7aN28lWPxeuu4O00PRXRYpFeAv2aQr7upIe69GhkDoIk2wEBAX16js6IdBJ
e4rvgVn1UA1qG7qed6Ak0ZJyTNmoYjnygkx7dXTEYlQutnSnQi6nGmtEyDom6YCJ
yTk2aX+lEb8YgPQAIF4Fhu0rFEuLDeDDMlGdE4GRyD//0r/nx4KiBxDxMK/DIywS
InyhYYUfih+JE1ovt1g7
=Bn8i
-----END PGP SIGNATURE-----