Crossword puzzle attack on NLS

Joo Yeon Cho*, Josef Pieprzyk

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

6 Citations (Scopus)


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 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 Konat 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 bias of the distinguisher to be around O(2-30). Therefore, we claim that NLS is distinguishable from truly random cipher after observing O(260) keystream words. The experiments also show that our distinguishing attack is successful on 90.3% of Konst among 232 possible values. We extend the CP attack to NLSv2 which is a tweaked version of NLS. In result, we build a distinguisher which has the bias of around 2-48. Even though this attack is below the eSTREAM criteria (2-40), the security margin of NLSv2 seems to be too low.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers
EditorsEli Biham, Amr M. Youssef
Place of PublicationBerlin ; New York
PublisherSpringer, Springer Nature
Number of pages7
Volume4356 LNCS
ISBN (Print)9783540744610
Publication statusPublished - 2007
Event13th International Workshop on Selected Areas in Cryptography, SAC 2006 - Montreal, QC, Canada
Duration: 17 Aug 200618 Aug 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4356 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other13th International Workshop on Selected Areas in Cryptography, SAC 2006
CityMontreal, QC


Dive into the research topics of 'Crossword puzzle attack on NLS'. Together they form a unique fingerprint.

Cite this