International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Crossword Puzzle Attack on NLS

Joo Yeon Cho
Josef Pieprzyk
Search ePrint
Search Google
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.
  title={Crossword Puzzle Attack on NLS},
  booktitle={IACR Eprint archive},
  keywords={Distinguishing Attacks, Stream Ciphers, Linear Approximations,  eSTREAM, NLS, Crossword Puzzle Attack},
  note={ 13215 received 9 Feb 2006, last revised 8 Mar 2006},
  author={Joo Yeon Cho and Josef Pieprzyk},