[Cryptography] RNG design principles

[Theodore Ts'o]

On Wed, Nov 23, 2016 at 11:15:21PM -0700, John Denker wrote:
> That's not a very persuasive argument, for the simple reason
> that anybody who believes that, even a little bit, has long
> since given up on the field of cryptography and found another
> line of work, perhaps as a landscape gardener or as a pizza
> deliverator.
> 
> That's because the argument applies to everything, not just
> the RNG.  If the NSA has pwned the keyboard on which you
> type the passphrase, it doesn't matter what you use as your
> RNG, or operating system, or browser, or hash function, or
> cipher suite.

My attitude is that is that we need to consider all of these things as
*possible*, and then weigh the costs and benefits of the attacker
trying to use a particular vector, versus the costs and benefits of
trying to defend against that particular vector.  So for example,
mixing multiple sources that may introduce difficulty to potential
attackers from being able to predict the numbers generated from those
sources doesn't hurt, and might help, and is relatively cheap.  Yes,
we need to mix them such that if there is unanticipated correlation,
that it won't make things worse, but that's not that hard -- for
example, you can just use a cryptographic hash (which you would be
relying upon for your whitener, anyway) to do the mixing.

Does this slow down the random number generator, potentially?  Sure!
But I seriously question the claim that you *need* gigabytes of
cryptographically secure random numbers per second in the first place.

> I doubt many people on this list would say, "Golly, here
> are three different ciphers we found lying around.  We
> don't trust any of them, so let's just XOR them together.
> That should be hunky dory."

No, but we *would* consider nesting them with different keys.  e.g.,

	E_NSA(K_A, E_KGB(K_B, E_MSS(K_C, Sekrit)))

Why don't we do this?  Because it's slow, and unlike a CSRNG, where we
don't need bulk random number generation, we *do* want to be able to
do bulk data encryption.  So it's a question of whether the costs are
worth the potential benefits, and how much trust do we put in a
particular cryptographic algorithm that *wasn't* designed by the NSA
using secret criteria.

Does that mean that we need to potentially worry about backdoors in
keyboards?  Sure --- see the Jitterbug[1] paper.  Do we need to worry
about backdoored HDD firmware?  Yes[2].  And there are countermeasures
that can be used by both a careful cloud provider and by HDD
manufacturers to protect against this, and trust me, work *is* being
done to try to defend against these sorts of things.

[1] https://www.usenix.org/legacy/event/sec06/tech/shah/shah_html/jbug-Usenix06.html
[2] http://www.dailykos.com/story/2015/2/17/1364910/-Breaking-Kaspersky-Exposes-NSA-s-Worldwide-Backdoor-Hacking-of-Virtually-All-Hard-Drive-Firmware

But again, it's a matter of costs and benefits, both for the attacker
and the defender.  Things like keyboard bugs and HDD firmware attacks
are fine for an attacker interested in doing a targetted attack.  But
there are some real limits as to the practicality for using such
attacks for bulk trawling expeditions, including the fact that
keyboards and HDD's don't have network interfaces and thus can't
"phone home" for instructions or assistance --- and the SOC's used in
HDD's are relatively weak.  But yes, we *should* consider this, and
use layered models of security to try to make life as hard as possible
for the attacker.

And that's really the key for why mixing from multiple sources is a
good thing.  Think of it as layered security; defense in depth; belt
and suspenders.  So you use FDE on a hard drive, *and* you encrypt at
the cluster file system level, *and* you use application specific
encryption, *and* you encourage the user to use end-to-end encryption,
precisely so that if one layer has a weakness, you can hopefully limit
or eliminate the exposure caused by that weakness or security breach.

RNG design should be no different.

Cheers,

							- Ted