Cryptanalysis of nonlinear feedback shift registers. Issue 4 (3rd July 2016)

• Record Type: Journal Article
• Authors: Pommerening, Klaus
• Is Part Of: Cryptologia. Volume 40:Issue 4(2016)
• Page Start: 303
• Page End: 315
• Publication Date: 2016-07-03
• Subjects: Boyar-Krawczyk algorithm -- cryptanalysis -- nonlinear feedback shift register -- stream cipher; Cryptography -- Periodicals; 652.8
• DOI: 10.1080/01611194.2015.1055385
• Languages: English
• ISSNs: 0161-1194

Abstract

ABSTRACT: For a successful cryptanalysis of an NLFSR, the needed number of known plaintext bits is about the smaller of two numbers: the period (including the preperiod if the sequence is not purely periodic) and the number of degrees of freedom of the feedback function. Therefore, under the assumption that the feedback function is completely unknown, there is no better way to cryptanalyse an NLFSR than a straightforward search for the period. If the choice of the feedback function is restricted in order to guarantee its efficient computation, then an algorithm by Boyar and Krawczyk gives an efficient cryptanalysis of the NLFSR in the sense of asymptotic complexity.