Paper 2006/049

Crossword Puzzle Attack on NLS

Joo Yeon Cho and Josef Pieprzyk


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.

Note: This is an extended version of the paper which was presented in SASC 2006.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Distinguishing AttacksStream CiphersLinear ApproximationseSTREAMNLSCrossword Puzzle Attack
Contact author(s)
jcho @ ics mq edu au
2006-03-08: revised
2006-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joo Yeon Cho and Josef Pieprzyk},
      title = {Crossword Puzzle Attack on NLS},
      howpublished = {Cryptology ePrint Archive, Paper 2006/049},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.