S. Petrović and A. Fúster-Sabater (Spain)

Telecommunications Technology, Spread Spectrum Techniques, Cryptanalysis, Edit distance, Correlation attack.

A pseudo-random sequence generator is the essential part of any spread-spectrum system. In this paper, a ciphertext only attack on a pseudo-random sequence generator with a linear feedback shift register (LFSR), whose clocking sequence is controlled by a subgenerator of general type, is described. Using a special statistical model as well as the edit distance with constraint on the maximum length of the runs of deletions, it is possible to determine the set of candidate initial states of the LFSR. The clock control sequence is obtained by performinga "depth-first" search through the constrained edit distance matrix that corresponds to each possible candidate. The search includes optimal and suboptimal paths, where the deviation from the optimal ones depends on the noise level. This method of determining the clock control sequence is more efficient than checking all the possible initial states of the subgenerator.

Important Links:

Go Back