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 value, which is a key-dependent word, we present the graph showing how the bias of distinguisher vary with . In result, we estimate the average bias to be around . Therefore, we claim that NLS is distinguishable from truly random cipher after observing keystream words on the average. The experiments also show that our distinguishing attack is successful on of among 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}
}