Graph-Based Approach to the Edit Distance Cryptanalysis of Irregularly Clocked Linear Feedback Shift Registers

Pino Caballero-Gil (University of La Laguna, Spain)

Amparo Fúster-Sabater (C.S.I.C., Spain)

Candelaria Hernández-Goya (University of La Laguna, Spain)

Abstract: This paper proposes a speed-up of a known-plaintext attack on some stream ciphersbased on Linear Feedback Shift Registers (LFSRs). The algorithm consists of two basic steps: first, to guess the initial seed value of one of the LFSRs, and then to use the resulting binarysequence in order to deduce useful information about the cipher parameters. In particular, the proposed divide-and-conquer attack is based on a combination of graph-based techniques withedit distance concepts. While the original edit distance attack requires the exhaustive search over the set of all possible initial states of the involved LFSR, this work presents a new heuristic op-timization that avoids the evaluation of an important number of initial states through the identification of the most promising branches of the search graph. The strongest aspects of the proposalare the facts that the obtained results from the attack are absolutely deterministic, and that many inconsistent initial states of the target LFSRs are recognized and avoided during search.

Keywords: attack, linear feedback shift register, symmetric cryptography

Categories: D.4.6, E.3, K.6.5