[Cryptech Tech] Maurer's Universal Test for Randomness

[Bill Cox]

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

On 09/20/2014 06:40 AM, Benedikt Stockebrand wrote:
> 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.

The board I build back in 1998 used the breakdown voltage between a
2N222, which is far noisier than the zeners I tested, but
unfortunately highly component specific.  I ran enough current that
the resulting noise signal was a continuous mountain range rather than
spikes separated by some amount of time, but my goal was a bit
different.  My board was not mass producible because of the dependence
on an unpredictable source.

I think focus on the avalanche effect is probably the right solution
for this project, and just taking zero-crossings sounds manufacturable
and reproducible.

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

It was 500 kbytes/second, which I derived by mixing 40 unwhitened
bytes from the A/D through a shift register that XORed the data and
shifted every cycle.  I didn't really need 500Kbytes/second, but I've
always been something of a speed freak :-)

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

I just ordered a Teensy 3.1 Arduino compatible board for my prototype.
 It is capable of 1 Mbyte/sec transfer to the host PC over USB, so
I'll target that bandwidth.

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

That's a great way to do it.  My board was a one-off.

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

With care, you can get the reverse breakdown of a 2N222, when
amplified carefully, and run at fairly high current, go generate a
mountain range with a high unpredictable 100MHz component.

However, sensitivity to external noise sources is a major concern.
This is one reason I want to play with the infinite noise multiplier
circuit.  It is practically immune to external noise sources.

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

Sounds good to me.

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

I figured out this security issue a few months ago.  My original
concept was a tiny IC generating whitened noise using parallel
infinite-noise multipliers.  The crypt-list guys liked the idea, but
had no use for the chip.  If they want post-whitened noise from an
un-auditable noise source they can just use the RDRAND instruction.

> 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

An HSM with an auditable TRNG and FPGA based processing sounds really
good to me.  I'll enjoy following the progress.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUHXVBAAoJEAcQZQdOpZUZsvAP/2UkY2WjdT/Fzdbaa/pIHziv
izrR4j1dh8Td+nRJ4P8Md/NcL9CrnvX8PGvyVp9IRahoAdPMHsFcEHrcQHyB6uWh
aNyPEFDlRZqRJNjmCTeYv3t772/SuD7f5Cbh3HpwzQsT7RO0EGKNR1FavbOILIFh
E7fcHxS6IUpKaiXbJ94HLP+YikmoOEZZ9GmfzNUJFzxXb9+P4hbPdHoToAEc5EXU
r1f26Gj4H8kWWmz0yyYjAEGYBu9SJlaI+KQ61Tk+VZP1eo9rnflARM3Abu//IbQH
qKo+mTLWqXcrwkOdx8mXpFnRDxRDGGiQEhI8LO+4Dbrq/A9Q6Lj1oico6eZSjt/K
Lpdw7IQqirOMruZVSFjLSXU6ythNFukncwFkJDz42x5at8zTM5lY2t/aK+H0Xq8M
OXLk4xVJmWp9zIrv7Hd327iqMuYYaHiYoucF87JC89zy6WnpjmclxZdOJGaFGHcq
Mut7G3hxH1deTpzgR5CwbSrmuy2bfl5m+l75iKngoT8fsGSjY9bdZktmkSBMDWmK
RFrCMF9/nBoW/dYaApjq3tpMeZFrgSTbX986Id5+kO4tHpuyEXK4jHOW0RTp9AAn
t9YSn0RcZBs3FWQmJuMV5K4UMY3TR4azzmldkyOAXp/zI/xLOmEUDymj8Z6Kv9jk
ZhHXie4bz8eCSbtzNwvj
=RbKr
-----END PGP SIGNATURE-----