[Cryptography] An alternative electro-mechanical entropy source (was 'We cannot trust' Intel and Via's chip-based crypto...)

[Nico Williams]

On Fri, Dec 13, 2013 at 10:59:17AM -0800, Steve Weis wrote:
> On Thu, Dec 12, 2013 at 3:44 AM, Arnold Reinhold <agr at me.com> wrote:
> > ...
> 
> A few comments:
> 1. You aren't trusting the CPU to generate random numbers, but you're
> trusting the motherboard and chipset that your proposed RNG device is
> plugged into. You're also ultimately still trusting the CPU which is
> consuming those values.

I know this thread got campy and all, but, it's one thing to trust
RDRAND and use its outputs without any further post-processing[*], and
it's another to trust the rest of the CPU.  It's true that one cannot
possibly fully test, say, 64-bit multiplication... but on the whole the
CPU has to implement deterministic operations reliably, and it's too far
down the stack to robustly implement the Ken Thompson attack[**][***].

So, yes, it is reasonable to trust a CPU but not its RNG.

The correct approach to RDRAND is to make it but one of several inputs
to a CSPRNG.  That is should be so is so clear now (and, IIRC the
consensus, if one were to try to determine one, of the /dev/*random
robustness thread) that we really should stop retreading over this.

[*] Or with entirely deterministic post-processing, if that processing
    is easy for the adversary to match.

[**] I've been reminded once that Thompson wasn't the first to think of
     it, and he'd given credit.  Still, you'll all understand when I
     refer to it as the Ken Thompson attack.

[***] Unless, I suppose, the CPU has another small computed bolted on
      that can operate independently of the CPU and which could flash
      the CPU's microcode.  "Hmmm".

> 2. How does a CPU authenticate that it's talking to a real, audited
> RNG device and not a spoofed device?

Physical security.  It still matters.  (I.e., tamper evident seals, et
cetera).  You have to trust HW within some perimeter.

> 3. I think an accelerometer measuring vibrations could be influenced
> by the CPU fans, which can be influenced by attackers running userland
> processes.

As long as they can't influence it at high enough frequencies...
Accelerometers are a decent source of entropy for mobile devices, though
probably not all the time (might use too much battery, or the device
might be close enough to at-rest relative to the local gravity well for
an extended period of time).

> If you try to address these issues, I think you'll end up with
> something that looks like a TPM: a cheap device plugged into a bus
> with a slow RNG, persistent storage, & crypto functionality that is
> supposedly made by a trusted manufacturer.

Except hopefully using parts usually already found in every computer.
Like mic inputs (see turbid), or just plain interrupt jitter + cycle
counters / hi-res clocks.  Plus a baked-in seed, plus a seed saved at
boot-/shutdown-time.

Nico
--