JUCS - Journal of Universal Computer Science 15(15): 2981-2998, doi: 10.3217/jucs-015-15-2981
Graph-Based Approach to the Edit Distance Cryptanalysis of Irregularly Clocked Linear Feedback Shift Registers
expand article infoPino Caballero-Gil, Amparo Fúster-Sabater§, Candelaria Hernández-Goya|
‡ University of La Laguna, Tenerife, Spain§ C.S.I.C., Madrid, Spain| University of La Laguna, La Laguna, Spain
Open Access
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.
symmetric cryptography, attack, linear feedback shift register