Multiple modular additions and crossword puzzle attack on NLSv2

Joo Yeon Cho; Josef Pieprzyk

Multiple modular additions and crossword puzzle attack on NLSv2

Joo Yeon Cho^*, Josef Pieprzyk

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

7 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Information Security - 10th International Conference, ISC 2007, Proceedings
Editors	Juan A. Garay, Arjen K. Lenstra, Masahiro Mambo, Rene Peralta
Place of Publication	Berlin ; New York
Publisher	Springer, Springer Nature
Pages	230-248
Number of pages	19
Volume	4779 LNCS
ISBN (Print)	9783540754954
Publication status	Published - 2007
Event	10th Information Security Conference, ISC 2007 - Valparaiso, Chile Duration: 9 Oct 2007 → 12 Oct 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4779 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	10th Information Security Conference, ISC 2007
Country/Territory	Chile
City	Valparaiso
Period	9/10/07 → 12/10/07

Cite this

Cho, J. Y., & Pieprzyk, J. (2007). Multiple modular additions and crossword puzzle attack on NLSv2. In J. A. Garay, A. K. Lenstra, M. Mambo, & R. Peralta (Eds.), Information Security - 10th International Conference, ISC 2007, Proceedings (Vol. 4779 LNCS, pp. 230-248). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4779 LNCS). Springer, Springer Nature.

Cho, Joo Yeon ; Pieprzyk, Josef. / Multiple modular additions and crossword puzzle attack on NLSv2. Information Security - 10th International Conference, ISC 2007, Proceedings. editor / Juan A. Garay ; Arjen K. Lenstra ; Masahiro Mambo ; Rene Peralta. Vol. 4779 LNCS Berlin ; New York : Springer, Springer Nature, 2007. pp. 230-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{34816d2974da4d779784bb993adb8ee5,

title = "Multiple modular additions and crossword puzzle attack on NLSv2",

abstract = "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.",

author = "Cho, {Joo Yeon} and Josef Pieprzyk",

year = "2007",

language = "English",

isbn = "9783540754954",

volume = "4779 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "230--248",

editor = "Garay, {Juan A.} and Lenstra, {Arjen K.} and Masahiro Mambo and Rene Peralta",

booktitle = "Information Security - 10th International Conference, ISC 2007, Proceedings",

address = "United States",

note = "10th Information Security Conference, ISC 2007 ; Conference date: 09-10-2007 Through 12-10-2007",

}

Cho, JY & Pieprzyk, J 2007, Multiple modular additions and crossword puzzle attack on NLSv2. in JA Garay, AK Lenstra, M Mambo & R Peralta (eds), Information Security - 10th International Conference, ISC 2007, Proceedings. vol. 4779 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4779 LNCS, Springer, Springer Nature, Berlin ; New York, pp. 230-248, 10th Information Security Conference, ISC 2007, Valparaiso, Chile, 9/10/07.

Multiple modular additions and crossword puzzle attack on NLSv2. / Cho, Joo Yeon; Pieprzyk, Josef.

Information Security - 10th International Conference, ISC 2007, Proceedings. ed. / Juan A. Garay; Arjen K. Lenstra; Masahiro Mambo; Rene Peralta. Vol. 4779 LNCS Berlin ; New York : Springer, Springer Nature, 2007. p. 230-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4779 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Multiple modular additions and crossword puzzle attack on NLSv2

AU - Cho, Joo Yeon

AU - Pieprzyk, Josef

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38149065302&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:38149065302

SN - 9783540754954

VL - 4779 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 230

EP - 248

BT - Information Security - 10th International Conference, ISC 2007, Proceedings

A2 - Garay, Juan A.

A2 - Lenstra, Arjen K.

A2 - Mambo, Masahiro

A2 - Peralta, Rene

PB - Springer, Springer Nature

CY - Berlin ; New York

T2 - 10th Information Security Conference, ISC 2007

Y2 - 9 October 2007 through 12 October 2007

ER -

Cho JY, Pieprzyk J. Multiple modular additions and crossword puzzle attack on NLSv2. In Garay JA, Lenstra AK, Mambo M, Peralta R, editors, Information Security - 10th International Conference, ISC 2007, Proceedings. Vol. 4779 LNCS. Berlin ; New York: Springer, Springer Nature. 2007. p. 230-248. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Multiple modular additions and crossword puzzle attack on NLSv2

Abstract

Publication series

Other

Other files and links

Fingerprint

Cite this