[cryptography] Random number generation influenced, HW RNG

grarpamp grarpamp at gmail.com
Fri Sep 6 17:03:27 EDT 2013


On 9/6/13, Eugen Leitl <eugen at leitl.org> wrote:
> ----- Forwarded message from Andy Isaacson <adi at hexapodia.org> -----
>
> From: Andy Isaacson <adi at hexapodia.org>
> Subject: Re: [liberationtech] Random number generation being influenced -
> rumors
>
> On Fri, Sep 06, 2013 at 10:45:46AM -0700, Joe Szilagyi wrote:
>> Does anyone put any stock into the rumors floating lately that the
>> government may have influenced Intel and/or AMD into altering

> However, I claim that the fear is well founded and should be taken into
> account by all threat models.
>
> HWRNG is a nearly-uniquely difficult security problem to crack.  By
> definition it is impossible to prove that a black-box HWRNG is safe.
> This is different from the security properties of a blackbox AES or
> MODMUL accelerator, which can be demonstrated to conform
> ...
> By contrast, a properly functioning HWRNG cannot be tested in a way that
> distinguishes it from the output of a stream cipher seeded with a
> backdoor key.  And there's no way to test the behavior of HWRNG on an
> ongoing basis; even if you had a test to run, it might switch to "stream
> cipher mode" under the covers.

Even dieharding the stream since inception is insufficient test.

> If your AES instructions don't do AES, then testing
> against a software implementation will show it!

Unless some of those billion gates are dedicated to
recognizing and modifying software AES to match, and
every separate processor you might have handy to run
software test on since AES came out has also been
backdoored. There is always custom test rig or by hand.

> This is not to say that RdRand is completely unusable.  Putting RdRand
> entropy into a software pool implementation like /dev/urandom (or
> preferably, a higher-assurance multipool design like Fortuna) is a cheap
> way to prevent a putative backdoor from compromising your system state.

> Weighing towards distrusting HWRNG we have the fact that NSA is reported
> (yesterday) to have intentionally backdoored Dual_EC_DRBG, and to have
> spent significant amounts of money to backdoor chip implementations,
> with enough success that they brag about it in administrative summaries.
>
> So, I put a lot of credence in distrusting HWRNG black box
> implementations.  But unfortunately we need a lot more reliable entropy.
> A fully open source, nothing up my sleeve hardware entropy source would
> be a huge improvement.

True, if you can't see and verify it you can't trust it. Assuming
there is no aforementioned subversion in other parts of the CPU,
an RNG is then of base importance to much crypto...

So what would be the cost per box to build 10,000 open source [1]
RNG's [2] and sell them for middling/no profit? As assembled boxes,
as you-build kits, or as free blueprints.

If you don't need speed/quantity for speedy/large OTP XOR streams,
these hobby jobbers would suffice to seed software prngs, and work
well in combination with other software sources.

What would be the cost bumps for speedy units, still complying
with [1 and 2], for various definitions of speed?

Dieharding this and any rng since inception over various
block sizes would seem warranted to catch component and other
failures [3], whereupon the /dev/<rng> device would block and
warn until fixed. No one is doing this extra step in kernel or
even in userland yet afaik. Why not?


[1] For example, entirely from breadboard discrete logic you can buy
and validate from any local parts supplier. ie: not using embedded
asics or fancy usb fobs... but resistors, diodes, 74 series gates, etc.

[2] Based on radiation, radio, audio/video, environmentals, etc.

[3] Neutrino and other hits, Intel/AMD on-die gate failure, etc.


More information about the cryptography mailing list