You are looking at a specific version 20030203:172643 of this paper. See the latest version.

Paper 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.

Note: changed

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
stream cipherskeystream generatorNLFGconditional correlation attackfast correlation attacks
Contact author(s)
bernhard loehlein @ t-systems com
History
2003-02-03: received
Short URL
https://ia.cr/2003/020
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.