Messages in this thread | | | Date | Fri, 17 May 1996 13:02:31 -0400 | From | "Theodore Y. Ts'o" <> | Subject | Re: CONFIG_RANDOM (compromise?) |
| |
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
| |