[Cryptech Tech] Hardware entropy

[Bernd Paysan]

Am Freitag, 16. Mai 2014, 18:49:27 schrieb Joachim Strömbergson:
> Aloha!

Hi!

> Bernd Paysan wrote:
> > Thanks to Heise, I got informed that you are working on a open+secure
> > 
> >  cryptochip.  Has anybody started with the entropy source yet?  I've
> > 
> > several ideas how to create entropy on an FPGA, and I'd like to try
> > them out...
> 
> Has Cryptech been mentioned in Heise? Do you have a link?

You already found it ;-).

> Cool of you to make contact. I'm almost a bit startstuck - you have done
> a lot of cool stuff since at least early 1990s with the 4stack machines
> etc. Your input and knowledge would be great.

Thanks.

> > The general structure of an entropy source would be: The source
> > itself (using unreliable, self-timing, or instable configurations of
> > the lookup tables, which probably requires some low-level entry, as
> > the standard Verilog compiler might want to eliminate them...), which
> > must have a raw access from the outside (to get and measure raw
> > entropy, so we can be confident that it is good entropy), and a
> > conditioner, which is a secure one-way function over the entropy bits
> > (which makes measuring the entropy extremely hard, as the one-way
> > function produces something that definitely looks like good
> > entropy).
> 
> As Fredrik wrote we will kick of a sub project that will produce the
> design of a stable, well tested PN avalanche noise based entropy source.

Fine; that means an external circuit.  PN avalance noise is a good entropy 
source.

> But our RNG does not hinge on that specific entropy source. In fact what
> we try to achieve is a complete, modular TRNG with support for several
> entropy sources (providers) that feed a mixer + CSPRNG that generated
> the actual random numbers. This follows similar TRNG structures as is
> present in modern OSs (Linux, OpenBSD) as well as the Bull
> Mountain/RdRand in Intels processor - if one is to trust what Intel
> presents.

Modularity is good; the problem with RdRand and the internal entropy 
collections in Linux and OpenBSD however is that you don't have access to the 
raw entropy pool to check if it is good - just to the conditioned output - 
which by definition looks good, even if it actually isn't.

> The following presentation (that needs to be updated) shows proposal:
> 
> http://trac.cryptech.is/browser/doc/presentations/Cryptech_TRNG_Ideas_2014-0
> 3-17.pdf

The "debug access to the raw entropy" is definitely a must-have.  i would 
prefer not to have an injection path to the TRNG; you may use the CSPRNG in 
isolation with a separate state, and test it that way.  Crafted injection into 
the TRNG should be avoided; the first blog posting of Dan Bernstein's blog was 
about entropy attacks: blog.cr.yp.to/20140205-entropy.html

That is important for DSA/ECDSA signatures.  Running the conditioner in 
absorb/squeeze modes however is something you can do (you don't have to inject 
entropy all the time, once you have enough entropy, the conditioner should be 
good enough to run in squeeze mode as DRNG); this also allows debugging at 
reset: don't absorb anything, just squeeze out things; this should give a 
deterministic result.

> Currently I have the basics of the mixer and CSPRNG almost done. The
> debug, test system is not ready. Nor are any entropy sources.
> 
> We have had long discussions on viable entropy sources. Some are pretty
> firm that PN avalanche noise is the only usable source of entropy. I
> think shot noise as well as meta stability in CMOS devices are usable
> too.

Any sort of non-deterministic behavior is an entropy source; it doesn't have 
to be perfect or white noise (even when your diode provides white noise, you 
will still have the ADC adding biases, because the ADC won't be perfectly 
linear, and will have a range larger than the variations of the voltage on the 
diode).

Shot noise manifests itself in CMOS circuits in variable delays (jitter), the 
entropy sources derived from that base on ring oscillators, which you capture 
at an asynchronous point in time (the normal system clock), and while the 
chance that you get a 1 or 0 are about 50%, the actual value is not very 
predictable, and XORing it with another independent ring oscillator removes 
the 50/50 probability.  This works even with very low jitter if you don't 
sample the free-running ring oscillators too often.  The TERA construct below 
builds on the ring oscillator idea (with a slightly different approach to turn 
the jitter into a random number).

Metastability usually has a bias (a part of the metastable circuits even has a 
deterministic response), so you can use metastability both to produce entropy 
and a reproducable unique identifier ("fingerprint").  For an ASIC, I would 
prefer a modified SRAM as entropy source; the modification is that you can 
force both bit lines to zero, creating the metastable state.  You can generate 
a big amount of randomly flipped bits in a very short time that way, and you 
can use the stable results as uniqe ID.  SRAM as entropy source also works for 
embedded controllers: You can gather the entropy of the SRAM at startup, and 
then run a DRNG with enough internal state for the rest of the operation (make 
sure it is a history-keeping DRNG, see below).

But unfortunately, for an FPGA, this is not the way to go, as we can't modify 
the SRAM that way.

> And the important thing is that we want to have more than one
> entropy source and of different types to make it harder to manipulate
> more that one physical process at the same time.

Agreed.  Just make sure that when one entropy source dies, the overall TRNG 
output doesn't become more predictable.

> The Cryptech system will however not force any implementor to use a
> specific entropy source or a specific number of sources. The PN
> avalanche noise is the basa one and then we can add more.
> 
> Regarding FPGA based entropy sources, there has been done some
> interesting work on it. The following report presents several variants
> that has been tested. The big problem is getting control of the layout.
> But when that works, the meta stability achieved seems to be able to
> produce an entropy source that meets AIS31.
> 
> http://www.eit.lth.se/sprapport.php?uid=498

I probably would use the carry chain as delay elements, these are pretty fast 
and have a predictable layout.  The downside is probably that the jitter of 
the carry chain is less due to the predictable layout.  This requires 
experiments ;-).

> I would love to test these, but if you are able to do it, even better.
> As long as you can get the source to generate 32-bit words (via a
> buffer) we can easily connect it to the coretest system and extract the
> data to do offline testing with Dieharder for example. Something like
> what I'm using today for the hash testing:
> 
> http://trac.cryptech.is/browser/core/coretest_hashes
> 
> Do you have any good FPGA dev boards available? I'm using the TerasIC
> C5G board and can recommend it. A great little board.

I'm using the Altera DE1 board. Not as new, but more than enough gates for the 
things I do (usually b16 stuff; any experiments I would do with an entropy 
source would first have a b16 core attached to do the data aquisition and then 
send the data to the PC).

> > I'd prefer to use Keccak as conditioner, because that's a hash I have
> > no doubts about.  There's a Keccak implementation on OpenCores.
> 
> You could easily replace the SHA-512 core in our TRNG with Keccak. I'm
> not sure users at large yet is as comfortable with Keccak as SHA-512,
> even though the SHA-3 compo is over.

All the Merkle Damgard constructs have known structural weaknesses; that was 
the reason for starting the SHA-3 competition... so they are all broken, at 
least in theory.  There's no practiacal attack on SHA-512, though, but SHA-3 
doesn't even have the theoretical weakness.  The comfort level with "old and 
proven to have a structural weakness" should be lower...

> What are your thought regarding CSPRNG? My idea is to use ChaCha or XChaCha.

I'm not fully comfortable with this construct; it's ok for crypto, where your 
security depends on a single key, but IMHO not ok for conditioning a TRNG, 
where your security depends on the entropy source.  In essence, the algorithm 
is that you have an input, which is key+counter+nonce (the key comes from the 
entropy source), and you generate an output for that, which is not related to 
the input (which comes from the entropy source).

This is fine for crypto (where the entropy source is your session key, and you 
have only one of that, and it has to be perfect), with the caveat that a 
constant starting point may provide ways for side-channel attacks, but the 
problem with conditioning a TRNG is that when the entropy source is poor (your 
"key"), it will result in predictable random numbers, when you also reset the 
counter when "new entropy" (which is actually mostly the same as the old 
entropy, as the attack vector here is a bad entropy source) from the entropy 
source arrives.  Don't.  If you don't reset the counter, you still have the 
problem that infrequent use of the crypto device starts with a predictable 
counter...  The problem here is that there's no history of the entropy, and 
that it should be sufficient if the entropy generator produces about 512 bits 
of entropy at startup - there's no need for more bits than those if you 
accumulate entropy.

There are ways to turn ChaCha into a state-accumulating sponge function 
(similar to how BLAKE has turned ChaCha into a hash function, which also needs 
to accumulate all the state it has seen), that would be ok.  The actual 
permutation function in ChaCha is fine for me; it's the mode of operation 
which is the problem.

I would use Keccak, and absorb the entropy source data, and squeeze out random 
numbers on request, always leaving a big enough residual state.  Each absorbed 
data changes the internal state of Keccak, and each squeeze round also changes 
the internal state - you have no chance to become predictable even if your 
entropy source stops delivering any entropy - you become deterministic in that 
case, but it still has enough entropy accumulated. If the entropy source still 
continues to deliver some entropy (a few bits per 32 bit word would be 
sufficient), the CSPRNG still would absorb and keep a history over that 
entropy.

I must say, I really like the sponge function principle. Any entropy you 
absorb adds to the entropy pool, and the even when you stop supplying new 
entropy, the output stream stays perfectly unpredictable.

The other thing I'm not comfortable with is NIST SP800-90A.  Not just because 
of Dual EC DRBG.  Better stick to AIS31.  In essence, however, the actual 
entropy source doesn't have to deliver unbiased, perfectly distributed 
entropy.  It just has to deliver entropy with known statistical properties; 
enough to feed the pool of the conditioner.  If half the bits are stuck, let 
them stuck, just feed in twice the number of bits.  This works if you get the 
conditioner right, and for that you need something that accumulates entropy 
history.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <https://lists.cryptech.is/archives/tech/attachments/20140516/de83d703/attachment-0001.sig>