On 9/6/13, Eugen Leitl <eugen@leitl.org> wrote:
----- Forwarded message from Andy Isaacson <adi@hexapodia.org> -----
From: Andy Isaacson <adi@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.