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

[Kent Borg]

On 11/21/2016 05:53 PM, John Denker wrote:
> 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.
> [...]
> 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!

Your definition of squishy is, shall we say, rather squishy. Any 
candidate source that is neither perfectly good nor perfectly bad, you 
call squishy. Why do you waffle? Why won't you definitively tell me 
whether the source is good or bad? Because you don't know! What *do* you 
know? You know that you can't predict its output, otherwise you would 
declare it "reliably predictable". Well, if you can't predict it, then 
it is useful, for XOR-ing it in will remove you from the population of 
observers who could predict the next random draw.

Get off the "squishy" hobby horse and hop on the "correlated" hobby 
horse: Much more useful would be if you were pedantic on whether 
candidate sources might be correlated with other sources. Because 
XOR-ing one more source can be *very* bad--if it is correlated with a 
previous source (e.g., some beautiful quantum-derived bit stream, and an 
inversion of the same bit stream).


What would you call a backdoored RNG from the NSA? I think you would say 
"reliably predictable", but I would say "useful"!

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

All "reliably predictable", but I XOR-them together and (assuming an 
observer can deal with sync issues), they are quite predictable 
to...very probably no one.

To put icing on the cake, I then XOR in some "squishy" local noise 
source. Maybe something that is very knowable to a local observer (who 
can see my lava lamp in the window), but as long as it isn't also know 
to that mythical cabal who has the keys to all those backdoored RNGs, 
the population that can predict my next random draw goes to zero.

Thought experiment: Is a streamcipher of a counter "reliably 
predictable" or "reliably unpredictable"? I guess you would call 
"squishy", because the key *could* be known. I would say the category 
"squishy" is meaningless, rather this hinges on on very concrete things: 
whether the cipher is good, and whether the key actually is known. (My 
taste is for local secrets to change. It unnerves me that if that local 
key is static.)

The goal isn't to have some perfect head-of-a-pin output, the goal is to 
get the number savvy observers ever closer to zero; the goal is to make 
the last holdouts work so hard acquiring my local RNG state information 
that they might just as well have rooted my computer in the first place 
because it would have been far easier, cheaper, and more resistant to 
detection. (The goal is also to worry about whether local software is 
actually using this valuable random data and not ignoring it.)

-kb, the Kent who doesn't care whether his RNG produces random data, he 
just cares that no one can back out all the "squish" and predict the 
next draw.