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

[John Denker]

 On 11/20/2016 12:57 PM, Viktor Dukhovni wrote:
 
>> Anyone else care to comment on the wisdom or folly of RDRAND as
>> a principal (sole) seeding mechanism for a TLS stack?  

On 11/21/2016 02:40 PM, Ray Dillinger replied:

> Don't do that.  It is folly to rely on any *single* source as a
> seeding mechanism.				[1]

As a *minor* point that's not strictly true.  In this world there
are many situations where it makes sense to put all your eggs in
one well-guarded basket.  Birds have been doing precisely that for
the last 50 million years.  That is quite often preferable to the
opposite extreme, where the eggs are spread over so many baskets
that you can't efficiently guard any of them (let alone all of
them).

Meanwhile, the *major* point is that claim [1] all too often
morphs into a claim of the converse, namely that having more
sources is ipso facto better.


> [...] to make sure you're getting at least 128 bits that
> that particular set of attackers wouldn't know or be able to determine.
> If every last possible source of entropy on your box is known by or can
> be determined by *someone*, but for each possible *someone* there's at
> least one that they can't, then you can have some security as long as
> your adversaries don't share information, but your security depends on
> 128 bits from every source in the set that is unknowable to at least one
> of your adversaries.

I disagree, for the following reasons:

As a general principle, RNGs are just as important as ciphers.
Consider superencryption using multiple broken ciphers, such as
rot13 combined with single DES.  You wouldn't advise people to
do that, would you?  By the same logic, you should not advise
people to XOR a pile of broken RNGs.

It helps to introduce the following contrasting concepts:
 -- reliably predictable
 -- random, i.e. reliably unpredictable
 -- squish, i.e. neither reliably predictable
   nor reliably unpredicable

Here are some useful equations:
  random XOR squish = random
  squish XOR squish = squish   (*not* random)

> RDRAND is provided by a single entity and can't be audited. 
[...]
> For all we know, RDRAND is a deterministic generator keyed by CPU ID and
> reseeded by the time each millisecond.  I do not claim that this is the
> case; I claim only that it COULD be and nobody could tell the difference
> from the outside.  That would be a worst-case scenario deliberately
> designed as a backdoor.  If that were the case, then someone from the
> "In group" who knows about the backdoor, knows what time your seed was
> generated, and knows your CPU ID or MAC address (MAC can usually be
> correlated with what CPU that device was installed on the same
> motherboard with) can eavesdrop on your output, test a few hundred
> thousand possibilities which takes less than a second, and determine
> your key.

We can summarize by saying RDRAND is squish.  From our point of view,
it is neither reliably predictable nor reliably unpredictable.

Combining it with other sources of squish does not help!

The only solution is to find some source of randomness that *can*
be audited, and audit it.  The requires a boatload of work.  However,
just because the right thing is hard does not give us a license to
do the wrong thing.

On 11/21/2016 12:12 AM, John Gilmore wrote:

>> The beauty of allegedly-random numbers is that you can, and should,
>> xor them with OTHER independent allegedly-random numbers to produce
>> something that is no weaker than the strongest of them.

That is true, if interpreted sufficiently narrowly.  So far so good.

>> So if you trust RDRAND and somebody else trusts interrupt timing,
>> mash the two together and you can both trust the result.

No, that doesn't work, for the same reason that combining two ciphers
with NOBUS backdoors doesn't work.  It is only a matter of time before
the two attackers compare notes, whereupon both succeed in attacking us.

Seriously, folks:  The fundamental equation is:
  squish XOR squish = squish

And by induction, it doesn't matter how many lousy RNGs you combine:
  squish XOR squish XOR squish XOR squish XOR squish XOR squish = squish

Combining untrusted RNGs makes just as much sense as combining untrusted
ciphers, i.e. no sense at all.

Having two trusted RNGs would be great, but in the meantime, given the
choice between one trusted RNG and a whole steaming pile of untrusted
RNGs, you are much better off with the one good one.


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