CryptoDB
Crossword Puzzle Attack on NLS
Authors: | |
---|---|
Download: | |
Abstract: | NLS is one of the stream ciphers submitted to the eSTREAM project. We present a distinguishing attack on NLS by Crossword Puzzle (CP) attack method which is newly introduced in this paper. We build the distinguisher by using linear approximations of both the non-linear feedback shift register (NFSR) and the nonlinear filter function (NLF). Since the bias of the distinguisher depends on the $Konst$ value, which is a key-dependent word, we present the graph showing how the bias of distinguisher vary with $Konst$. In result, we estimate the average bias to be around $O(2^{-30})$. Therefore, we claim that NLS is distinguishable from truly random cipher after observing $O(2^{60})$ keystream words on the average. The experiments also show that our distinguishing attack is successful on $90.3\%$ of $Konst$ among $2^{32}$ possible values. |
BibTeX
@misc{eprint-2006-21542, title={Crossword Puzzle Attack on NLS}, booktitle={IACR Eprint archive}, keywords={Distinguishing Attacks, Stream Ciphers, Linear Approximations, eSTREAM, NLS, Crossword Puzzle Attack}, url={http://eprint.iacr.org/2006/049}, note={ jcho@ics.mq.edu.au 13215 received 9 Feb 2006, last revised 8 Mar 2006}, author={Joo Yeon Cho and Josef Pieprzyk}, year=2006 }