[Cryptography] /dev/random is not robust

Theodore Ts'o tytso at mit.edu
Wed Oct 16 22:12:14 EDT 2013


On Wed, Oct 16, 2013 at 05:10:00PM -0400, Jerry Leichter wrote:
> I see the paper as valuable for proposing strong security
> definitions for "PRNG's with input", showing that neither Barak and
> Halevi's algorithm nor the Linux RNG's algorithm attain those
> definitions, but suggesting an algorithm that does.  The answer
> "well, yes, the Linux generator fails if its entropy sources are bad
> in a particular way, but we have entropy sources that aren't" misses
> the point.

The answer is, "#1, the paper's claim that the Linux generator fails
if the entropy sources are under the control of the adversary relies
on the fact that it stops collecting entropy when it thinks the
entropy pool is full, which is NOT TRUE, and #2, it's really, REALLY
stupid to assume the adversary has complete control of the interrupt
timing on your system."  I think you have missed the first part.

> At one time, not so very long ago, no one knew how to
> build a cipher secure against a known-plaintext attack.  Today,
> that's assumed.  A defense of a modern cipher as "well, we won't let
> anyone see the plaintext" isn't good enough.

I'm not sure that's the best analogy, because there are known attack
scenarios where someone might have some plaintext/ciphertext pairs and
might be interested getting the key.

I haven't seen an even half-way reasonable attack scenario where the
attacker can control all of the entropy sources in the system --- not
just know the interrupt timings, but to *control* the interrupt
timings, in a very fine-grained way.  (So it's not enough to just to
know roughly when a packet gets sent to the machine, but to be able to
send the packet such that you can control the exact value of the CPU
counter, so you can fool the entropy estimator.  And the attacker has
to be able to do this not just for network interrupts, but also for
disk, keynoard, and mouse interrupts, all at the same time.
Yeaah.....)

> (Even worse is the
> claim that "you can only see the state of the PRNG from root, and
> then there are other attacks".  This isn't even true - a Linux
> system frozen into a VM can't prevent anyone from reading that state
> if they want it hard enough.)

That's only true if they have fairly privileged access to the
hypervisor.  And while it's barely possible to imagine scenarios where
an adversary would have read access to hypervisor memory, but not
write access, that is actually pretty far-fetched.  Feel free to
construct a scenario....

> I'm not sure how the whole business of entropy estimation feeds into
> this.  There are others who've criticized it as just guesswork.
> Frankly, they have a point.  John Denker's work on Turbid provides a
> much more principled approach to the problem.  Still, the Linux
> kernel has to work with what it has.

Um, if you read the paper, its claim that /dev/random is not robust by
their definition relied fundamentally about the entropy estimator
being "wrong" because the adversary could control the inputs to the
entropy pool, and thus construct inputs that would fool the entropy
estimator.  So it feeds into the discussion in a rather fundamental
way.

In the Linux Pseudo Random Number Generator Revisited paper
(http://eprint.iacr.org/2012/251.pdf), the authors sampled and
analyzed the various real-life entropy sources, and found the entropy
estimation to be pretty good, and if it erred, it erred on the side of
convervatism, which is as designed.  In case you were wondering, I'll
consider this "good" academoc research --- not because I like the
result, but because they actually carried out research instead of
relying only on articially created attacks dressed up in the language
of mathematical formalism.

Formal proofs may be impressive, but it's nice if the formalism is
actually tied to reality, instead of tenuously based on some
fantastical assumptions, e.g., "The US Naval aircraft carrier is not
robust against photon torpedoes".  You can do lots of formal
mathematics involving weapons yield to "prove" such a result, but it
begs the question of whether photon torpedos exist in the real world.

						- Ted


More information about the cryptography mailing list