Slovak University of Technology in Bratislava
Faculty of electrical engineering and information technology
Degree Course: INFORMATICS
Author: Milan Vojvoda
Thesis: Design and cryptanalysis of a running key generator
Supervisor: prof. RNDr. Otokar Grošek, CSc.
1999, December

In the Diploma Thesis there are studied properties of a simple running key generator as well as its building blocks - linear feedback shift registers (LFSRs).

The running key generator consists of two clock-controlled LFSRs L1 and L2. The output is produced as the bitwise XOR of outputs of L1 and L2. The clocking of registers is asynchronous, dependent on the last keystream bit.

We proved a theorem determining the period of the keystream and several theorems concerning the number of runs in the maximum-length sequence.

In order to evaluate generated sequences we applied several statistical tests specified in FIPS 140-1, including gap test and serial correlation test. Our samples consisted from 100 different keystream sequences. All of them passed the tests given by FIPS 140-1, but failed the gap test and 5% of them failed the serial correlation test.

We also found conditions when a keystream passes the first Golomb's postulate, and the long run test.

Finally, a modification of the generator using substitution of FCSRs (feedback with carry shift registers) for LFSRs was studied, too. Neither this modification is resistant to known plaintext attack presented in [1].

[1] Vojvoda, M.: Cryptanalysis of a clock-controlled running key generator, Journal of Electrical Engineering, No.10s, 1999, pp. 16-18.