Re: Fortuna

["Theodore Ts'o" <tytso@mit.edu>]

On Tue, Apr 19, 2005 at 04:31:47AM +0000, David Wagner wrote:
> Theodore Ts'o  wrote:
> >For one, /dev/urandom and /dev/random don't use the same pool
> >(anymore).  They used to, a long time ago, but certainly as of the
> >writing of the paper this was no longer true.  This invalidates the
> >entire last paragraph of Section 5.3.
> 
> Ok, you're right, this is a serious flaw, and one that I overlooked.
> Thanks for elaborating.  (By the way, has anyone contacted to let them
> know about these two errors?  Should I?)

I don't know of anyone who has contacted the authors yet.  I haven't
had the time, since I'm currently travelling at the moment.

> I see three remaining criticisms from their Section 5.3:
> 1) Due to the way the documentation describes /dev/random, many
>    programmers will choose /dev/random by default.  This default
>    seems inappropriate and unfortunate.
> 2) There is a widespread perception that /dev/urandom's security is
>    unproven and /dev/random's is proven.  This perception is wrong.
>    On a related topic, it is "not at all clear" that /dev/random provides
>    information-theoretic security.
> 3) Other designs place less stress on the entropy estimator, and
>    thus are more tolerant to failures of entropy estimation.  A failure
>    in the entropy estimator seems more likely than a failure in the
>    cryptographic algorithms.
> These three criticisms look right to me.

/dev/urandom is a cryptographic RNG, which is seeded from RNG.
/dev/random uses a very similar cryptographic RNG, but it uses large
pool to collect entropy, and uses an entropy estimator to limit the
amount of data that can be extracted from the rng.  

If the entropy estimator fails, /dev/random degrades to a
cryptographic RNG.  So it is not a disaster, whereas the approach
described in this paper (which uses a non-cryptographic extractor)
would seem to me to be *more* prone to catastrophically failure if the
entropy estimator fails than /dev/random.

As to whether or not applications should be using /dev/random or
/dev/urandom, /dev/random is no worse than /dev/urandom, as long as
the application doesn't mind blocking when the entropy levels are too
low.  In practice, most of the time this situation doesn't arise since
the appropriate way of using /dev/random is only to extract a small
amount of entropy when needed to generate long-term keys, or when
seeding a userspace cryptographic RNG for session keys.

						- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/