[Cryptography] combining lots of lousy RNGs ... or not

[Ray Dillinger]

On 11/22/2016 08:52 PM, John Denker wrote:
> On 11/22/2016 08:55 PM, Theodore Ts'o wrote:
>> So the question is what do you get if calculate
>>
>> 	H(squish_NSA | squish_KGB | squish_MSS)
>>
>> Well, it's certainly not "random", in the formal information
>> theoretical sense.  But from a _practical_ sense, if you assume that
>> the NSA, KGB, and MSS will never collude and/or admit to each other
>> that they introduced a NOBUS vulernabiliy into DUAL_EC, RDRAND, and a
>> TPM module, it might be _practically_ random.
> 
> I disagree.  It's an invalid argument leading to an unsound
> conclusion.

It's a completely valid argument.  TT's not speaking math, he's speaking
engineering.  Our public policy is unsound.  Compliance of hardware with
public policy is unverifiable.  Our engineering policy has to deal with
that unsoundness and unverifiability as ground truth.

There exists no single source that can be fully trusted.  There exists
no manufacturer whom we can assume will ever be allowed to create such a
source.  If a manufacturer makes an honest attempt to create such a
source we cannot assume that manufacturer has not failed in design or
implementation.  If a manufacturer has made an honest attempt to create
such a source, and has succeeded in design and would have succeeded in
implementation, we cannot assume that manufacturer has not been sabotaged.

The best we can do is make sure that all these untrustworthy sources are
transformed into output unrecognizable and unpredictable to anyone who
can recognize or predict the sources.  And that's what the mixer does.

If I'm to put all my eggs in one basket, that basket is a mixer fed from
as many diverse sources as I can find.

> This is a very serious public-policy issue.  Cryptographers (e.g.
> Matt Blaze) have been called to testify before Congress.  The
> point is, when this-or-that agency says something is NOBUS, you
> really, really must not assume it is actually NOBUS.

> Please do not assume any such thing.  It's bad engineering and
> bad public policy.

We can have no expectation that any of them are ever going to stop, even
if a day comes when "public policy" says that they must and all have
claimed to.  To assume we can ever have compliance with public policy
from anyone who could possibly get away with cheating, is bad
engineering and bad security policy.

We can use their bits, in the expectation that at least some of them
haven't cracked or colluded with the others.  We can use combinations,
hashes, and encryptions of their bits, in the expectation that combining
them with each other in hard-to-reverse and uncorrelated ways will
render them unrecognizable even to people who could predict or recognize
any one of those sources. And we can go right on gathering all the bits
we can get from sources whose unpredictability we're more certain of,
both because our public policy is deplorable and because it remains bad
security policy to assume compliance with public policy.

I have completely given up on the ideas of "random" and "entropy."  In
practical engineering terms, the crucial properties are
"unpredictability" and "unrecognizability".

The mixer is what ensures unpredictability and unrecognizability, when
no single source can be trusted to be unpredictable or unrecognizable to
the entities that provided it.

Air turbulence inside an old-fashioned hard disk drive was pretty
unpredictable. Once people started relying on it for unpredictable bits
there was a motive to sabotage the firmware, intercept calls that were
being used to detect turbulence, and provide predictable answers.  We
don't know if anybody actually did, but the source went from trusted to
mostly-trusted because someone could have.  These days people are using
SSDs and they provide no unpredictable bits at all.

RDRAND seems unpredictable.  It's claimed to be unpredictable.  It is
almost certainly unpredictable to non-state actors or I'd have seen the
cracks on the dark side of the net by now.  But there's a motive to
sabotage it, and we can't be certain nobody did, so it's mostly-trusted,
not trusted.  It's still useful, however, because even if sabotaged, it
can be rendered unrecognizable to the saboteurs as long as we encrypt or
hash it along with bits they can't predict or recognize.

Using it otherwise would be bad engineering, for the same reason that
protocols requiring a fully honest and fully error-free Trent have been
revealed to be bad engineering.

We can't assume Trent is honest and error-free.  We can't even assume
Trent will be ALLOWED to be honest. Even if Trent is both honest and
error-free Trent can still be deliberately sabotaged and adversaries
have demonstrated willingness to do exactly that.  Especially if Trent
manufactures hardware, because hardware is even harder to audit than
software. Cheating, failure, or sabotage are therefore harder to detect
and correspondingly more likely to happen.

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161123/d17738c4/attachment.sig>