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.