An Algorithm for Cryptanalysis of Certain Keystream Generators Suitable for High-Speed Software and Hardware Implementations

Miodrag J. MIHALJEVIC  Marc P. C. FOSSORIER  Hideki IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A    No.1    pp.311-318
Publication Date: 2001/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
stream cipher,  keystream generators,  linear feedback shift registers,  fast correlation attack,  decoding,  

Full Text: PDF(245.7KB)>>
Buy this Article

An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.