Authors: Mihaljević, Miodrag J. 
Fossorier, Marc P. C.
Imai, Hideki
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Cryptanalysis of keystream generator by decimated sample based algebraic and fast correlation attacks
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 3797 LNCS
First page: 155
Last page: 168
Issue Date: 1-Jan-2005
Rank: M23
ISBN: 978-3-540-32278-8
ISSN: 0302-9743
DOI: 10.1007/11596219_13
This paper proposes a novel approach for cryptanalysis of keystream generators consisting of the composition of a linear finite state machine (LFSM) and nonlinear mapping. The proposed approach includes a dedicated decimation of the sample for cryptanalysis based on the following: Suppose certain B bits of the LFSM initial state as known and identify time instances where certain arguments of the nonlinear function depend only on these B bits and are equal to zero. As opposed to previously reported methods, the proposed one also identifies and uses certain characteristics of the LFSM state-transition matrix in order to reduce the nonlinearity of the system of overdefined equations employed in an algebraic attack scenario, or to reduce the noise introduced by the linearization of the nonlinear function which corrupts the linear equations employed in a correlation attack scenario. The proposed method is employed for developing efficient algorithms for cryptanalysis of the nonlinear combination keystream generator reported at INDOCRYPT 2004.
Keywords: Algebraic attacks | Decimation | Fast correlation attack | LFSRs | Nonlinear combination keystream generator | State transition matrix | Stream ciphers
Publisher: Springer Link

Show full item record


checked on Jul 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.