An approach to the initial state reconstruction of a clock-controlled shift register based on a novel distance measure

Abstract

The initial state reconstruction problem of a clock-controlled shift register is considered when the characteristic polynomial, a segment of the output sequence and the probability of ones in the clock sequence are known. This problem is more general than the considered one (in [2]), and it is solved using a quite different approach. A novel distance measure for comparison of two different length binary sequences is proposed and its main characteristics relevant for the cryptanalysis is derived. An algorithm for the cryptanalysis based on the proposed distance measure is presented and its main characteristics are pointed out. Expected minimal length of the observed sequence for the unique initial state solution is estimated. Illustrative numerical examples are included.