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

John Denker jsd at av8n.com
Tue Nov 22 14:04:07 EST 2016


I have long emphasized the distinction:
  -- reliably predictable
  -- reliably unpredictable
  -- squish

On 11/22/2016 08:25 AM, Kent Borg wrote:
> 
> Your definition of squishy is, shall we say, rather squishy.

No, it is neither new or vague.  It mathematical terms, it is well
defined.  Formal examples -- *constructively* provable examples --
have been known since Gödel (1931).  Intractable and undecidable
propositions are well known in computer science.  In practical
terms, squish is directly useful and well understood, and has
been for a very long time, so long that it has a Latin name:
   "argumentum ad ignorantiam"
and it is the subject of English maxims as well:
   "absence of evidence is not evidence of absence."
Application to RNGs in particular was discussed by Knuth (1969).

True story:  One of my earliest experiences in the workplace:  We
needed a PRNG, and I was instructed by the pointy-haired boss to
get rid of my LFSR and instead use the Program Counter as saved
by the last interrupt, because that was «unpredictable».  I kid
thee not.  In fact this was a terrible RNG.  Successive calls
tended to return the same number, and even if you got two different
numbers, one of them was likely to be the PC of the null job.  I
tried to explain that even though it was not reliably predictable,
it was not reliably unpredictable.


> Give me the NSA's backdoored RNG, give me a Chinese backdoored RNG,
> give me a Russian backdoored RNG. The more the merrier!

That's like putting three locks on your door ... and then hiding the
first key under the mat, the second under a nearby rock, and the third
atop the lintel.

Of course there are protocols where the /interested parties/ get
together and XOR their various contributions.  However, neither the
NSA nor the Spetssvyaz nor the Third Department have my interests
at heart.  At such a meeting, any sane person shows up with a RNG
that *he* can trust.  [XX]

   At every poker table there is a fish.  If you look around the
   table and can't spot the fish, it's you.

Nit-pickers note:  There exist contrived cases where XOR actually
helps, for instance if one source is truly random in the bottom
half of the word (but zero in the top half), while the second
source is random in the top half of the word (but zero in the
bottom half).  However, such a situation does not naturally arise
in practice, and if it did there would be easier ways of dealing
with it.

There exist realistic cases where the combination of two things is
better than either of the components separately, for instance the
hardware part plus the software part of a well-designed HRNG.
The two components were never intended to work separately.  The
proof of correctness applies to the system as a whole.

Proper operation requires the two components to be very carefully
engineered to work together.  They are joined in an intricate way.
This does not even remotely resemble the bogus construction that
launched this thread, namely
     squish XOR squish = squish

On 11/22/2016 04:13 AM, Jerry Leichter gave a commendably clear
discussion of correlated failures.  He cited Knuth's example,
which is dead-center in the domain of RNGs.  Without proof of
decorrelation, simple multiplicity has at best an untrustworthy
upside, and on the downside it is a waste of resources.

  Tangential but more general remark:
  Correlations are not the whole story, and simply counting
  the multiplicity is not the whole story, for the following
  reason:  Extra chains in parallel might give you added
  strength ... whereas extra chains in series just exacerbate
  the weakest-link issue.

  Weak links in series are even worse than correlations, in the
  sense that failure of any one link takes out the whole chain,
  whether or not the other links have failed.


=====

I wrote:
  random XOR squish = random			[1]

On 11/22/2016 08:13 AM, Phillip Hallam-Baker replied:

>> ​No. random XOR squish = squish		[2]
>> 
>> If I can interfere with squish, I can undo your random if I know it. And in
>> real world systems I can often know it.

General point:  I'm not convinced that's a good way to think about
it.  If the first component can so easily be interfered with, I
would have classified it as non-random to begin with.  Chez moi
"random" means /random enough/, i.e. /reliably/ unpredictable.
See paragraph [XX] above.

Specialized point:  When we apply it to the topic of the day, insofar
as statement [2] is even partly true, it's yet more of a reason why
the idea of XORing a squishy source with something else should be
abhorred.


More information about the cryptography mailing list