I saw the following message on a cryptography mailing list.  It would
be good if someone did that analysis on the *BSD rng.

Begin forwarded message:

Date: Tue, 21 Mar 2006 11:01:55 -0500
From: "Heyman, Michael" <Michael.Heyman@sparta.com>
To: <cryptography@metzdowd.com>
Subject: Linux RNG paper


Gutterman, Pinkas, and Reinman have produced a nice
as-built-specification and analysis of the Linux random number
generator.

>From <http://eprint.iacr.org/2006/086.pdf>:

Following our analysis of the LRNG, we suggest the following
recommendations for the design of pseudo-random number generators.

=B2 Fixing the LRNG. The issues which were reported in this paper should
be fixed. In particular, the LRNG code should be changed to prevent
attacks on its forward security. The OpenWRT implementation should be
changed to provide more entropy to the LRNG, or at least save its state
during shutdown.

=B2 Implementing a quota for the consumption of random bits. Random bits
are a limited resource, and attackers can easily mount a
denial-of-service attack (even remotely) by consuming random bits at a
high rate. The common solution for this type of problem is to implement
a quota system which limits the effect of each user, or each process,
on the operation of other users of the same system. Such a quota system
should be added to the Linux kernel.

=B2 Adopting the Barak-Halevi construction. The Barak-Halevi (BH)
construction and its analysis [3] are attractive in their simplicity,
which clearly identifies the role of every component of the system, and
enables a simple implementation. In comparison, the current LRNG
construction is an overkill in some aspects (like the size of the pools
or the number of SHA-1 invocations), but its complexity does not
improve its security but rather hides its weaknesses. We suggest that
future constructions of pseudo-random number generators follow the BH
construction (and in general, try to "keep it simple").

=B2 Since randomness is often consumed in a multi-user environment, it
makes sense to generalize the BH model to such environments. Ideally,
each user should have its own random-number generator, and these
generators should be refreshed with different data which is all derived
from the entropy sources available to the system (perhaps after going
through an additional PRNG). This architecture should prevent
denial-of-service attacks, and prevent one user from learning about the
randomness used by other users

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to
majordomo@metzdowd.com



		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb