Linux RNG paper

Heyman, Michael Michael.Heyman at
Tue Mar 21 11:01:55 EST 2006

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

>From <>:

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

² 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.

² 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.

² 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").

² 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 at

More information about the cryptography mailing list