Multiple modular additions and crossword puzzle attack on NLSv2

Joo Yeon Cho*, Josef Pieprzyk

*Corresponding author for this work

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

7 Citations (Scopus)


NLS is a stream cipher which was submitted to the eSTREAM project. A linear distinguishing attack against NLS was presented by Cho and Pieprzyk, which was called Crossword Puzzle (CP) attack. NLSv2 is a tweak version of NLS which aims mainly at avoiding the CP attack. In this paper, a new distinguishing attack against NLSv2 is presented. The attack exploits high correlation amongst neighboring bits of the cipher. The paper first shows that the modular addition preserves pairwise correlations as demonstrated by existence of linear approximations with large biases. Next, it shows how to combine these results with the existence of high correlation between bits 29 and 30 of the S-box to obtain a distinguisher whose bias is around 2-37. Consequently, we claim that NLSv2 is distinguishable from a random cipher after observing around 274 keystream words.

Original languageEnglish
Title of host publicationInformation Security - 10th International Conference, ISC 2007, Proceedings
EditorsJuan A. Garay, Arjen K. Lenstra, Masahiro Mambo, Rene Peralta
Place of PublicationBerlin ; New York
PublisherSpringer, Springer Nature
Number of pages19
Volume4779 LNCS
ISBN (Print)9783540754954
Publication statusPublished - 2007
Event10th Information Security Conference, ISC 2007 - Valparaiso, Chile
Duration: 9 Oct 200712 Oct 2007

Publication series

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


Other10th Information Security Conference, ISC 2007


Dive into the research topics of 'Multiple modular additions and crossword puzzle attack on NLSv2'. Together they form a unique fingerprint.

Cite this