[Cryptography] cheap sources of entropy

[Theodore Ts'o]

On Thu, Jan 30, 2014 at 08:29:08AM -0800, Dennis E. Hamilton wrote:
> The comfortable case is that if you have a truly unpredictable
> source (e.g., stream of uniformly-random 0/1-s) and it is xor-ed
> with another source of some distribution, the result consists of
> uniformly-random 0/1-s.

Sure, the problem comes when you don't have any "truly unpredictable
sources".  Sure, if you have a "truly unpredictable source", you're
golden, but is it really unpredictable?  Maybe the NSA has leaned on
the sound board manufacturer which John Denker's Turbid generator is
relying on, such that even though you *think* you're getting Johnson
Noise, you're really getting something that has been very cleverly
gimmicked to pass all the statistical tests, but in fact can be
predicted by the NSA.  Or maybe the sound card has just failed in some
interesting way that the author(s) of Turbid hasn't anticipated.

And then in real life, if you have mass produced consumer electronics
devices, how can you be certain that the manufacturing tolerances of
the hand-assembled units made in the US will be the same as the
mass-produced units made in Shenzhen?

This is why there are those of us who believe that it is useful to
pull in sources which might not be "truly unpredictable", but
"unpredictable to an outside, remote attacker" according to some
threat model.

For example, I might have the threat model that says even though the
relative strength of all of the access points visible to my wireless
handset might not be "truly unpredictable", the remote attacker will
not know be able to (a) get a detailed enough survey of my real-time
radio environment, and (b) get a precise enough location within said
radio environment, that given the effects of radio path bouncing,
blocking to the absorbtion of the wooden table (ie., is the cell phone
on top of the table, or below the table in my knap sack), that there
will be some amount of uncertainty that will not be known to the
remote attacker.

This is the "sow's ear" which John Denker has so disparagingly
referred to.  It is _not_ truly unpredictable; instead, it's that it's
probably not be predictable to an attacker given a certain threat
model, and if you have enough of these sources, it hopefully adds
enough uncertainty such that the attacker needs to do more work than
just simply doing a brute force search of the key space.

The same argument holds true of using keyboard or mouse event timing;
again, it's _not_ completely unpredictable, but unless you believe the
NSA might have a camera trained on your keyboard while you are
generating your GPG key, hopefully (in combination with other
environmental sources being gathered by the OS) maybe it's "good
enough".

At the end of the day it's all about engineering considerations.  My
arguments that you might not be able to trust the sound card to be
producing "true" Johnson noise is also about questioning certain
engineering assumptions.  The concern that the NSA could really
reverse engineer all of the "sow's ears" that might go into a random
number generator which is using cryptographic mixing of "hopefully
unpredictable" sources, is also a question of what assumptions you
might or might not be willing to make.

The devil really is in the details, which is why debates like this
tend to go on.... and on.... and on....

> The situation is more nuanced and there is much context to consider,
> especially in establishing that the effort and implementation
> doesn't lead to an actual reduction in cryptographic security in the
> presence of a determined adversary.

I'll also note that we also don't need perfection; we just need to
make it harder than other attack vectors.  The old joke of "I don't
need to run faster than the bear, I just have to run faster than
*you*" applies here.

If we make the random number generator sufficiently hard to attack
that it becomes easier to carry out other attacks (i.e., attacking the
BIOS or embedded controller in your laptop, etc.) then (a) the
rational, determined attacker will probably turn their attention to
the easier attack vectors, and (b) it the rational defender should
adjust their engineering resources to defending against those other
attacks, instead of being so fixed on random number generation to the
exclusion of all else that we end up constructing the cryptographic
equivalent of the Maginot Line.  :-)

	     	 	       		     	 - Ted