Re: CONFIG_RANDOM (compromise?)

Theodore Y. Ts'o (tytso@mit.edu)
Fri, 17 May 1996 13:02:31 -0400


Date: Fri, 17 May 1996 11:29:36 +0200
From: Harald Anlauf <anlauf@crunch.ikp.physik.th-darmstadt.de>

People seem to be too paranoid about the quality of pseudo random number
generators, but why don't you just ask the experts out there?

Indeed. People who want to understand this should read RFC 1750,
"Randomness Recommendations for Security".

You'll then understand why "passing all tests from Marsaglia's 'diehard'
suite of tests" is completely irrelevant to the topic at hand. I quote
an excerpt from RFC 1750:

[KNUTH] has a classic exposition on pseudo-random numbers.
Applications he mentions are simulation of natural phenomena,
sampling, numerical analysis, testing computer programs, decision
making, and games. None of these have the same characteristics as
the sort of security uses we are talking about. Only in the last two
could there be an adversary trying to find the random quantity.
However, in these cases, the adversary normally has only a single
chance to use a guessed value. In guessing passwords or attempting
to break an encryption scheme, the adversary normally has many,
perhaps unlimited, chances at guessing the correct value and should
be assumed to be aided by a computer....

These sequences may be adequate in simulations (Monte Carlo
experiments) as long as the sequence is orthogonal to the structure
of the space being explored. Even there, subtle patterns may cause
problems. However, such sequences are clearly bad for use in
security applications. They are fully predictable if the initial
state is known. Depending on the form of the pseudo-random number
generator, the sequence may be determinable from observation of a
short portion of the sequence [CRYPTO*, STERN]. For example, with
the generators above, one can determine V(n+1) given knowledge of
V(n). In fact, it has been shown that with these techniques, even if
only one bit of the pseudo-random values is released, the seed can be
determined from short sequences.

Not only have linear congruent generators been broken, but techniques
are now known for breaking all polynomial congruent generators
[KRAWCZYK].

- Ted