[Cryptech Tech] Tesing of entropy sources in FPGAs

[Joachim Strömbergson]

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

Aloha!

I've (or at least my trusty FPGA board and machines) has been a fairly
busy the last week doing a lot of entropy generation and testing. After
working on my setup I have now a system where I can download new FPGA
designs, extract hundreds of MByte of entropy data and then perform
analysis on the data. The tools I'm using for analysis are:

* Dihearder with all tests available
http://www.phy.duke.edu/~rgb/General/dieharder.php

* ent
http://www.fourmilab.ch/random/

* view_rnd
https://github.com/secworks/view_rnd

Based on the results it is quite obvious that the entropy has to be
pretty bad to be able to spot. Basically repeating patterns or changes
in bias levels. The information provided by ent is also far from a good
measure on the quality of randomness. Thus ent and view_rnd are
basically only usable as a first, quick test to determine if a source is
not totally dysfunctional.

I've performed four tests:
1. concat: The BP entropy source with two arrays of 32 oscillators with
two bit operands. Each array is folded onto itself using XOR and the
resulting 2x16 bit results are concatenated into a 32-bit word.

2. mix: The BP entropy source with two arrays of 32 oscillators with two
bit operands. The outputs from the arrays are combined using XOR to
create a 32-bit word

3. fpga: A slightly modified version of the BP entropy source is
instantiated 6 times but with 2, 3, 7, 13, 41 and 43 bit operands which
means that the cin-cout path and thus oscillator frequency varies. The
outputs from the oscillators are XOR-combined into a single bit. 32 bits
are collected in a shift register to create the resulting entopy word.

4. fpga_vn: A mofified version of (3) where I've tried to add a von
Neumann decorrealator in HW to see if/how that improves the results.


(All code is available in test/-something in the Cryptech repo. If/when
any of these are promoted to real cores they will be moved to
core/-something)

Results:
Just counting PASSED, WEAK and FAILED tests in the Dieharder reports I get:

concat
- ------
FAILED: 70
WEAK:    4
PASSED: 40

mix
- ---
FAILED: 76
WEAK:    2
PASSED: 36

fpga
- ----
FAILED: 55
WEAK:    3
PASSED: 56

fpga_vn
- -------
FAILED: 63
WEAK:   13
PASSED: 38

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.

I've included the Ent and Dieharder reports with this mail. When I have
the test data on a file server I will post links including digests for
the files.

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

iQIcBAEBCAAGBQJTmVlBAAoJEF3cfFQkIuyNYxoQANLZbAbtbjNzkyd4chavOrMl
eO42Pr2Kkpt/9uY+bMvUzqHrRsnzBrwCZs2aE1PFypbHyMeheilXZyOVranoBbnK
5eedbk/IVp5nDOMmb/6l3LrdU3RBjtR/w7DE4RqqSd/n/TunoQrikYJYwhfJ9kwa
pRaeYMLbmbvIdWHh4Zbv/XIQJrLZYpdwws5P+JQVvIy3AQyJdSSHXMPzodB5vitS
0ogV2Fk8uW43O4XD1ePjExi6IZkHYYUbRgSBvgwqgYAQufM2dFT2QCnwmzr/EWAa
dxCVpTqoVJVz1w3p1sDSswLIG4RZwnwHz6uAovU7hjUy3FrbyofwRBMSxawWryjK
vL5VG8U8nbtMaa41MPV0t6zUpIOMZ4orfrZ8bndahwmpAx4I+uCzxIA9CN5kN0Uz
x8DSsY43JQzH0Sw7S/Oj4DH7FFj08FeL5pqze9ZyiAYDcyvvmV1u313in+H3/4CK
SgaHMEjcrDh6406mnDhCCxRQ63tYhhnpeMRFE1XZ9qInG6vECTNs/wN4iCpgN4LF
zT7BNTfOgYKxJjoLTjJ+U0Q+6dWNIeSfjucmUq796gCZy8GEAHkEAlYFwFByNFe5
qlWIBEOHxe0gLcFQP2WslRrJL8+aMtd6X1Ejks29XuOM2bLhoQ/JCqLkF9qmnrm8
ilp2NH0w3WOaaRQrcC4I
=WiUT
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ent_fpga_2014-06-08.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0008.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ent_mix_2014-06-07.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0009.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ent_concat_2014-06-07.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0010.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dieharder_fpga_vn_2014-06-10.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0011.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dieharder_mix_2014-06-07.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0012.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ent_fpga_vn_2014-06-10.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0013.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dieharder_concat_2014-06-07.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0014.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dieharder_fpga_2014-06-08.txt
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0015.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ent_fpga_2014-06-08.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0008.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ent_mix_2014-06-07.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0009.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ent_concat_2014-06-07.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0010.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dieharder_fpga_vn_2014-06-10.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0011.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dieharder_mix_2014-06-07.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0012.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ent_fpga_vn_2014-06-10.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0013.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dieharder_concat_2014-06-07.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0014.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dieharder_fpga_2014-06-08.txt.sig
Type: application/octet-stream
Size: 543 bytes
Desc: not available
URL: <https://lists.cryptech.is/archives/tech/attachments/20140612/0f3da7ed/attachment-0015.obj>