[Cryptography] A TRNG review per day: RDRAND and the right TRNG architecture

[Bill Cox]

The "right TRNG architecture" looks like this:

    auditable cheap low speed TRNG -> auditable high speed CPRNG -> happy
user

Respectable TRNGs like the new Cryptech Tech TRNG are switching to this
architecture.  If you use *any* secure TRNG to feed /dev/random, regardless
of it's speed, and then read your cryptographic key data from /dev/urandom,
then you are already using this model.

However, I happen to be something of a speed freak.  Intel's RDRAND
instruction is appealing to me.  The architecture is the fastest TRNG I
have seen.  So, why not use it?  Here's why:

- It is probably back doored
- It is not auditable
- Critical portions of its design remain secret (such as whitening and how
to disable it)
- We don't need a fast TRNG, even though it's cool

I have no knowledge of any intentional back door in this architecture, but
if I were to design a TRNG for a processor, and wanted to insert a hard to
detect back door, this is the architecture I would use.  I simulated this
architecture myself in SPICE in a .35 micron CMOS process.  It seems to
work, and man it's fast!  It basically powers up a latch and let's it
randomly initialize to either a 0 or 1, and uses that as it's random
output.  If you wait 20ns, the latch will have flipped one way or the
other, and you can read out the result.  If you don't mind reading the
latch before it's sure to have settled to a 0 or 1, you can read it as fast
as your clock runs, and still get a high average entropy per bit.  There is
simply no reason not to run this at 3GHz.

That said, this TRNG has so many drawbacks that I predict no one other than
Intel will ever use it.  First, it requires a couple of large-ish on-chip
capacitors to hold the control voltages that compensate for factors that
cause the latch to prefer to power up one way or the other.  Without
measuring the 0/1 bias and dynamically compensating for it, this circuit
simply does not work.  This by itself makes Intel's TRNG both large and
complex.  Worse, it is *massively* sensitive to nearby signals.  It is more
sensitive to external signals than any other architecture I know of.  No
other TRNG relies on amplifying such a small noise signal, and no other
architecture can be PWNed with as little injected energy.  This is
literally the most attacker signal sensitive TRNG ever designed.

It's power supply sensitivity is so bad, Intel actually *patented*
regulating the supply of a TRNG in order to reduce the impact of a power
drain attack on their device, thus making it *illegal* for any of us to
build this architecture securely.  Simply executing a power hungry loop
surely would otherwise cause this TRNG to output a long sequence of either
1's or 0's, until the bias circuit manages to charge the capacitors to
different levels to compensate.  There is *zero* published evidence that
Intel's power supply regulation actually works well enough to defending
against this attack.  We can't even test for ourselves, because Intel
purposely hides the raw TRNG output!

The power drain attack is so obvious that I suspect Intel's engineers who
aren't owned by a TLA would not allow this on their chip without a separate
power regulator.  This circuit is also is effected by substrate currents,
which is my preferred method for back-dooring it in a way that most Intel
engineers would not notice.  An attacker with special knowledge of
surrounding components could easily influence the device through this path,
which will not show up in any schematic.  It also will not be flagged as a
potential problem by any DRC or signal integrity tool.  No SPICE simulation
will reflect this attack unless the netlist is manually modified to take
this into account.  Intel's hordes of EDA tool pushers would give this
attack a green light, because it would pass every step in their
tried-and-true IC verification process.

If they did look for substrate current attacks, maybe I could PWN it using
light.  Certainly this device would change it's power-up behaviour by
simply shining a flashlight on it.  If I could get some circuit on the chip
to emit some low levels of infrared, I could probably PWN it that way.

Another potential attack is rapidly changing the thermal gradient.  If a
nearby portion of the die could be made hot very quickly, it might change
the power-up preference of the latch faster than the bias correction
circuit can compensate.

These are just some of the ways this device could be back-doored or PWNed.
I bet we could have an entertaining competition to come up with the most
create way.

Despite the NSA's likely back door in RDRAND, adding it to your entropy
pool will still defeat anyone who lacks knowledge about the back door.
Most of the bad guys we worry about lack this knowledge.  However, one day
the back door may be reverse-engineered and published on the Internet.
Relying on RDRAND for security is a bad idea, even if you don't worry about
the NSA's snooping.  However, adding it to the entropy pool is a good idea,
so long as we don't increase the entropy estimate.  Linus was right to bash
that guy who wanted RDRAND banned from the Linux entropy pool.

So, why do we need true random data at high speed so badly that Intel
decided to build in a device requiring large capacitors and it's own power
regulator?  The truth is, we don't need high speed.  As many people have
argued here, all any single system requires is 256 bits of true random
data.  That's all they *ever* need, so long as it remains secret (which is
hard), and so long as a cryptographically secure PRNG (CPRNG) is used to
generate all future cryptographically pseudo-random data (which is
comparatively easy).

A TRNG simply does not need to be fast.  A Lava Lamp generates entropy fast
enough for almost any application, so long as we use it to seed add a high
speed CPRNG firehose.  Anyone selling you a high speed TRNG for a lot of
money, based on quantum voodoo or whatever, is ripping you off.

Due to Intel's inexplicable reluctance to make their device auditable,
while relying on what is probably the hardest TRNG architecture to get
right, I have to rate RDRAND as snake-oil for use in cryptography.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141024/067a6b81/attachment.html>