[Cryptech Tech] Maurer's Universal Test for Randomness

[Benedikt Stockebrand]

Hi Bill and list,

> Hi, guys.  I'm new to this list, and may not have much time I can
> commit to it, but I saw in the mail archive some discussion about an
> avalanche based TRNG.  That's probably fine, assuming there's no need
> for higher bandwidth data.  

well, the key reason why I focus on the avalanche effect is because it
is easy to audit and can be done in a way that adapts to the tolerances
and aging effects of components.

> Two thoughts on it... First, I was able to get the data rate to
> 500Kb/s by adding an 8-bit 40-MHz A/D converter rather than just a
> comparator against 0.

OK, just to get this straight: Are we talking kbits or kbytes here?

With the Atmel ATtiny2313 microcontroller (MCU) I'm using, 50 kByte/s
(500 kbit/s on the serial line with 8N1 encoding) are an upper limit
which I can actually reach if I don't use the von Neumann extractor.
With the von Neumann extractor and up to 19 kByte/s output that means I
get about 80 kByte/s of raw noise (entropy+redundancy) which may still
contain some significant amount of redundancy, more specifically with
bit-wise bias.

And using the ADC in the tiny2313 is significantly slower than using a
digital I/O pin: According to the data sheet an ADC operation takes at
least 13 clock cycles.

Finally, the circuit I use intentionally amplifies the analog signal
from the noise source to near digital levels, so an ADC wouldn't do much
good here.  The reason why I do this again is to compensate for
tolerances of components.

> The signal wasn't moving that fast, but the LSBs were still highly
> unpredictable.

The problem here is that entropy only enters that stream when the
avalanche starts and stops; otherwise you just measure the tolerances of
your components and measurement equipment.  That may be difficult to
predict, but an attacker may actually have resources to do so while we
lack the ones to test each and every device continuously while in
operation.

> I XORed it down 80-to-1 to generate the output.  That was back in
> 1998, I think.

Yes, I've basically done that as well.  With the "magic" Zener diodes
(from a set of Zeners that failed quality control with regard to
noise...)  I started with I only needed 50 XORs, and it did seriously
blow up in my face when I replaced those Zeners with others and didn't
realize I was still using that firmware, rather than the edge detection
algorithm.

Since you probably haven't found that from the archives: The algorithm I
use to read noise is not by XORing values, but instead by measuring the
time (in clock ticks) between rising edges.  The advantage here is that
it ensures there's no correlation between bits and adapts the output
speed of the device to the amount of entropy coming from the Zener diode
or reverse biased BE junction of a BJT I use.

> If I were doing it today, I would consider building a hardware Keccak
> (SHA3 winner) sponge to provide the whitened data [...]

Looks like we need to bring you up to speed a bit here.

If you want to make things auditable, then you really need to separate
the hardware random number generator (HWRNG) or hardware noise generator
from the cryptographically secure pseudo random number generator
(CSPRNG/CPRNG).

The key problem is that hardware fails, and when that happens it is
rather difficult to detect if you can't tap the un-whitened noise,
especially so if you want to continually monitor this during regular
operation.

If you just use some sort of noise signal and feed it straight into your
Keccak or ChaCha or whatever CSPRNG, then you can't tell afterwards if
things (still) work or not.

Additionally, to test that the CSPRNG is working correctly, then you
need to feed it known seed data so you can compare its output to what
you expect.

Now, there's another thing you may want to be aware of: My original goal
(with the ARRGH board) is to build a HWRNG which produces true random
output.  The Cryptech project however wants to build a full-blown crypto
hardware device (HSM, hardware security module), and one of the key
differences between these two approaches is that I have to take
particular care to ensure that all redundancy is removed from the noise
signal I use before I pass it on, while an HSM may use "diluted" noise
still containing significant redundancy as seed for a subsequent CSPRNG.

In other words, you may sometimes find that I switch between these
slightly different design goals.  And anyway, so far it seems that even
with an HSM, first extracting pure entropy from the noise source before
feeding it to the CSPRNG is desirable because it makes testing/auditing
much easier.


Cheers,

    Benedikt

-- 
Benedikt Stockebrand,                   Stepladder IT Training+Consulting
Dipl.-Inform.                           http://www.stepladder-it.com/

          Business Grade IPv6 --- Consulting, Training, Projects

BIVBlog---Benedikt's IT Video Blog: http://www.stepladder-it.com/bivblog/