Cryptology ePrint Archive: Report 2003/020

Attacks based on Conditional Correlations against the Nonlinear Filter Generator

Bernhard Löhlein

Abstract: In this paper we extend the conditional correlation attack ([LCPP96]) against the nonlinear filter generator (NLFG) by introducing new conditions and generalisations and present two known-plaintext attacks, called hybrid correlation attack and concentration attack. The NLFG is a well known LFSR-based keystream generator which could be used as a basic building block in a synchronous stream cipher system. Both new attacks use methods from the conditional correlation attack and additional from fast correlation attacks to derive the unknown initial state of the LFSR of the NLFG. The basic principle of iteratively cumulating and updating conditional correlations for the NLFG was proposed in [Loh01] and for general combiners with memory in [GBM02]. With the hybrid correlation attack it is possible to successfully attack the NLFG by applying a fast correlation attack, even if the filter function $f$ of the NLFG is highly nonlinear, e.g. the normalised nonlinearity $p_{e,f}$ is $\ge 0.45$. The concentration attack maps all computed conditional correlations to $D-B$ unknown LFSR bits, where $D \ge k$ and $1 \le B \le k$ are parameters which can be chosen by the attacker, and $k$ is the length of the LFSR of the NLFG. Even with low values of conditional correlations, it is possible to mount the hybrid correlation attack and the concentration attack successfully. This is not the case for the originally version of the conditional correlation attack ([LCPP96]) in a time lower than a full search over all possible initial states.

Category / Keywords: secret-key cryptography / stream ciphers, keystream generator, NLFG, conditional correlation attack, fast correlation attacks

Date: received 3 Feb 2003

Contact author: bernhard loehlein at t-systems com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: changed

Version: 20030203:172643 (All versions of this report)

Short URL: ia.cr/2003/020

Discussion forum: Show discussion | Start new discussion