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

Youji FUKUTA, Yoshiaki SHIRAISHI, Masakatu MORII

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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.8 pp.2155-2158
• Publication Date: 2003/08/01
• Type of Manuscript: LETTER
• Category: Information Security

Authors

Youji FUKUTA
Yoshiaki SHIRAISHI
Masakatu MORII

Keyword

stream cipher,  nonlinear combiner generator,  fast correlation attack,  parity check equations