Cryptology Cryptanalysis of Random Generators: Summary

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

In Sections 1 to 9 we developed a prediction method whose overall workflow is depicted in the following figure:

1. By guessing plaintext the cryptanalyst finds subsequences of the key stream until she succeeds in constructing a linear relation for the state vectors (Noetherian principle).
2. Using this linear relation she predicts some more key bits.
3. If a predicted bit turns out to be wrong—resulting in nonsense plaintext—, then the cryptanalyst has to guess some more plaintext and uses it to adjust the parameters accordingly; then she continues with predicting output bits.

One lesson learnt from these results is that for cryptographically secure pseudorandom generation we never should directly use the state of the generator as output. Rather we should insert a transformation between state and output that conceals the state. Section 9 illustrates that simply suppressing some bits—»truncating« or »decimating« the output—might be to weak as an output transformation. In the following section we'll learn about better output transformations.

There is a large twilight zone between pseudorandom generators that promise advantage to the cryptanalyst, and pseudorandom generators that put the cipher designer's mind at ease. In any case we should prefer pseudorandom generators for which both of the procedures

• state change
• output function

The following chapters present two approaches that are believed to lead to secure random generators:

• combinations of LFSRs with a nonlinear output transformation
• nonlinear congruentiale generators with substantially truncated output