A Method for Improving Fast Correlation Attack Using Parity Check Equations Modifications

Youji FUKUTA  Yoshiaki SHIRAISHI  Masakatu MORII  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.8   pp.2155-2158
Publication Date: 2003/08/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Information Security
Keyword: 
stream cipher,  nonlinear combiner generator,  fast correlation attack,  parity check equations,  

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




Summary: 
A nonlinear combiner random number generator is a general keystream generator for certain stream ciphers. The generator is composed of several linear feedback shift registers and a nonlinear function; the output is used as a keystream. A fast correlation attack is a typical attack for such keystream generators. Mihaljevi, Fossorier, and Imai have proposed an improved fast correlation attack. The attack is based on error correction of information bits only in the corresponding binary linear block code; APP threshold decoding is employed for the error correction procedure. In this letter, we propose a method which improves the success rate of their attacks with similar complexity. The method adds some intentional error to original parity check equations. Those equations are then used in APP threshold decoding.