[Cryptech Tech] Maurer's Universal Test for Randomness

[Bill Cox]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Wow, that's great!  Nice work!  I love that it is so auditable.  Of
course, with the carry chains in the FPGA, there's likely no real area
benefit to Keccak's AND-XOR-ROTATE operations vs ARX.  In an ASIC,
replacing the ADD with AND helps quite a bit.  500Mbps is quite
respectable.

On 09/16/2014 02:47 AM, Joachim Strömbergson wrote:
> Aloha!
> 
> Hi Bill! Great to see you on the list, and welcome to Cryptech!
> 
> 
> Bill Cox wrote:
>> I also like some newer TRNG architectures.  One I've been wanting
>> to build I call the "Infinite Noise Multiplier", but I haven't
>> designed one for a board-level project yet.  It certainly will be
>> more complex than using zener avalanche noise, so likely not a
>> good match. With a Keccak sponge in an FPGA, I don't think
>> there's any real need for high bandwidth true random data, so
>> long as the TRNG seeds the sponge well.
> 
> The current TRNG design we have today have three main stages:
> 
> (1) Entropy providers. Each provider contains the functionality to 
> generate entropy based on some source. Currently we have one
> provider based on avalanche noise and one based on ring oscillators
> inside the FPGA.
> 
> (2) The mixer. The mixer pulls available entropy from the providers
> and collects them into 1024 bit blocks. The collection is done in
> strict round robin fashion, which means that even though the ring
> oscillator can generate much more entropy than the avalanche noise
> based provider, they provide the same amount of entropy.
> 
> The 1024 bit block is fed into SHA-512 which generates a digest of
> 512 bits which is used as seed. And actually we run SHA-512 twice
> with 1024 bit entropy added each time in order to get in total
> 2x512 bits of seed. This means that we need in total 2048 bits of
> entropy everytime we do reseeding. For the first, cold start reseed
> this takes less than a second. For the next reseed when the entropy
> sources have been able to work independently it is much faster (the
> entropy sources have (or will have) fifos). The 1024 bit seed is
> then given to..
> 
> (3) The CSPRNG. This is the part that generates the random numbers 
> provided to applications. The CSPRNG is basically the stream
> cipher ChaCha. The differences with vanilla ChaCha and our version
> is that the 64 bit counter initial value is not all zero, but taken
> from part from the seed. And that we do 24 rounds, not 20 (or 12 or
> 8). In total we use 512 + 256 + 128 = 896 bits of seed to
> initialize the CSPRNG.
> 
> Using ChaCha allows us to generate huge amounts of random data with
> high performance at low clock frequencies in the FPGA. (ChaCha
> being an ARX design is very compact and efficient in HW.) Also it
> allows users to trade between security and speed by
> increasing/decreasing number of rounds. Our 24 rounds is very
> conservative. Yet we can do about 500 Mbps @ 50 MHz in an Altera
> Cyclone IV device. (I'm running it on a TerasIC DE0-Nano board).
> 
> We could generate 2**64-1 512 bit blocks of random data before 
> reseeding. Currently though the build time define sets this a fair
> bit lower. There is also an API to allow the user to set the
> automatic reseed to any value lower than the build define value.
> And you can always just write to the control bit that forces
> reseed.
> 
> Currently there are debug access via the API to get raw data from
> the entropy sources, but no test seed or debug mode. It will be
> there in the future.
> 
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUGC4uAAoJEAcQZQdOpZUZiWQP/j4w+fTnHKjYuFrD6mogrOhE
jQdDetYT9TzkShhSE/aYEcw4PY983NF0LPLHT1r5qvZJ1tH0nMFDXAxzQfzP1WP5
rVFdxBvBRgt61p9JxbhLTUlBe3TD83BAwJXbLCQqNozO+ZkTOFTFKLkmAPaXnj/8
6TV878S3j5HQvRqgngjPjhGFlFr6SZP12NSnIF4Nr6Y7UI9ZLcdlYuIZ/+nZRdek
a5Cb4Wb1YuLojIG53/7IAR/PC06UtbmLNIT7aQpMqwnA3BVpyT9T4PZx2rAk40TI
fy6CA5ixQUNl4nXNq/5pxvLFIw4xbAeQ/z4PL+d1YtocA4dt0J1LfB2BWd1C3mXP
VB9WySENF1PifvO2v68JTO6jUjaCtLdEzsK55BCw8dL+mTy0iu9MObcaiNEfG/pP
LyC0x1LDzcV2l7VV/tLOzEMAgj3WHlMIl/XON6lDoQ0aBbSZ8dcFXcoXA3gu7Cb2
h8nimSsN3RJmnNKPqieJFMZC7SrQNZaqpYhY+Vc7xrLACqmsJkTvP1L/rgcbmBWx
8SmMHgIBZxMlY0blDih0gkxXqRw5lLfvoOXDa9PJAVPkadqLnkss1FtEABcLZiLG
oNUjjlhEIzHEXelMweKiVLaFU1ZgQp/TWG+o9lIqvMjmpC2prphP+jZQmrjKow2J
rQ9oHMbRjEruu8HRkMYe
=WHoM
-----END PGP SIGNATURE-----