[Cryptography] cheap sources of entropy

Krisztián Pintér pinterkr at gmail.com
Mon Jan 20 14:50:50 EST 2014


John Denker (at Monday, January 20, 2014, 7:59:47 PM):

> Let's consider a few basic types of signal:
> 1) At one extreme there is perfect randomness, by which I mean 100%
> entropy density, such as a source that produces 8 bits of [...]

it is not that much of a concern. whitening is easy. all you need is
an estimate on the entropy density (which is impossible, but this is a
whole different issue, see later).

> In computer science and engineering there is the notion of
> "proof of correctness".  Can you /prove/ that a human waving
> his arms around is random?  More specifically, can you establish
> a provable lower bound on the entropy-content?

and this is where things go fishy. theoretically and strictly
speaking, there is no such thing as lower bound on entropy. we can
only put upper bounds. if you dig deep enough, at the bottom, we
arrive at the many century (millennia?) old determinism problem. if
the world is deterministic, entropy is pretty hard to even interpret.

in the more practical setting, we always talk about the entropy as
seen by some specific observer. in this case, the observer is the
combined knowledge of the scientific community that tries hard to
quantify and formulate the world. if a scientist comes up with a
better model of handwaving or a better model of how noise on a video
camera works, the effective entropy drops.

so we actually don't want a proof. we only want a reasonably sound
guess on what the attacker can know. apply some safety margin, and you
are good to go.

another interesting point is that you can hardly say anything looking
at the data. you must evaluate the process. you can of course
eliminate some foreseen failure cases, like no input, low input or
repeated patterns. but you will never be able to tell apart
fraudulent, attacker controlled data, or arcane failures from true
randomness.


> All the literature I've seen says that humans are /not/ in
> fact very good randomness generators.

if you mean, they produce very few entropy, i tend to agree. mouse
movements, waving or typing produces dozens to hundreds of bits per
second. this can be enough for some applications. after all, you need
only 128 bits, and you are good to go. also, a phone can possibly
gather data 24/7, accumulating it.

you are also correct that thermal noise can produce several orders of
magnitude more, and also much more stable.

but i disagree that thermal noise is fundamentally better. it is just
practically better.



More information about the cryptography mailing list