[Cryptography] combining lots of lousy RNGs ... or not
kentborg at borg.org
Tue Nov 22 10:25:50 EST 2016
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
More information about the cryptography