The perils of security tools

[Chad Perrin]

On Mon, May 26, 2008 at 11:22:18AM +0200, Simon Josefsson wrote:
> 
> For example, reading a lot of data from linux's /dev/urandom will
> deplete the entropy pool in the kernel, which effectively makes reads
> from /dev/random stall.  The two devices uses the same entropy pool.
> 
> I believe a much better approach would be if /dev/urandom was a fast and
> secure PRNG, with perfect-forward-secrecy properties, and /dev/random
> was a slow device with "real" entropy (whatever that means..) gathered
> from the hardware.  The two devices would share little or no code.  The
> /dev/urandom PRNG seed could be fed data from /dev/random from time to
> time, or from other sources (like kernel task switching timings).  I
> believe designs like this have been proposed from time to time, but
> there hasn't been any uptake.

My understanding of the situation is that the way you get secure use of a
PRNG is by feeding it "real" entropy, and the way you get fast use of a
PRNG is by feeding it whatever seeds you have on-hand, regardless of
"real" randomness -- or just don't feed it any seeds at all, if you don't
have any on-hand.  Thus, the reason /dev/urandom is fast is that it
doesn't actually *require* "real" entropy, and the reason /dev/random is
cryptographically secure is that it *does* require "real" entropy, which
of course means that it slows down a lot when you run out of "real"
entropy in the pool.

Assuming I am not mistaken in my understanding of the operation of the
two randomness devices, you could probably get reasonable security and
speed overall for /dev/urandom by limiting how quickly and often it
accesses the entropy pool, hitting it once in a while at (pseudo)random
intervals within a reasonable range to seed the PRNG.  This would make it
fast unless you're taxing the entropy pool so badly with multiple
processes using /dev/urandom or some /dev/random use that there literally
is no entropy left in the pool for /dev/urandom to use at all when it
tries to hit the pool.  It would not provide "perfect" forward secrecy,
however, because there would be brief intervals (between hits to the
entropy pool) during which knowing the PRNG algorithm and its current
state would allow someone to predict further PRNG output until the end of
the current entropy interval.  The length of the interval, however, could
conceivably be (effectively) unknowable.

Ultimately, I think the reason nobody has implemented a /dev/urandom that
allows for fast, secure PRNG operation with perfect forward secrecy is
that it's kind of a "pick n-1" situation, such as with the old saw, "Fast
good, cheap; pick two."  To get cryptographically strong randomness, you
need entropy, which taxes the entropy pool.  An additional entropy pool
would need more places to *get* entropy, of course.  Essentially, giving
the characteristics of cryptographically useful randomness and perfect
forward secrecy to /dev/urandom would ultimately mean you turned it into
a duplicate of /dev/random.

It looks like you're suggesting just changing the way /dev/urandom
receives its entropy so that it happens periodically, similarly to how I
described limiting it from exhausting the entropy pool above -- but that
won't solve the problem of giving /dev/urandom strong security and
perfect forward secrecy characteristics.

. . . or is there something I missed?

-- 
Chad Perrin [ content licensed PDL: http://pdl.apotheon.org ]
Baltasar Gracian: "A wise man gets more from his enemies than a fool from
his friends."
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20080527/c50298c9/attachment.pgp>