Crossword Puzzle Attack on NLS

Joo Yeon Cho; Josef Pieprzyk

Paper 2006/049

Crossword Puzzle Attack on NLS

Joo Yeon Cho and Josef Pieprzyk

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.

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

Metadata

Available format(s): PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: Distinguishing Attacks Stream Ciphers Linear Approximations eSTREAM NLS Crossword Puzzle Attack
Contact author(s): jcho @ ics mq edu au
History: 2006-03-08: revised; 2006-02-14: received; See all versions
Short URL: https://ia.cr/2006/049
License: CC BY

BibTeX

@misc{cryptoeprint:2006/049,
      author = {Joo Yeon Cho and Josef Pieprzyk},
      title = {Crossword Puzzle Attack on {NLS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/049},
      year = {2006},
      url = {https://eprint.iacr.org/2006/049}
}