Crossword puzzle attack on NLS

Joo Yeon Cho; Josef Pieprzyk

Crossword puzzle attack on NLS

Joo Yeon Cho^*, Josef Pieprzyk

^*Corresponding author for this work

Department of Computing

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

4 Citations (Scopus)

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 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(2⁶⁰) keystream words. The experiments also show that our distinguishing attack is successful on 90.3% of Konst among 2³² 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 language	English
Title of host publication	Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers
Editors	Eli Biham, Amr M. Youssef
Place of Publication	Berlin ; New York
Publisher	Springer, Springer Nature
Pages	249-255
Number of pages	7
Volume	4356 LNCS
ISBN (Print)	9783540744610
Publication status	Published - 2007
Event	13th International Workshop on Selected Areas in Cryptography, SAC 2006 - Montreal, QC, Canada Duration: 17 Aug 2006 → 18 Aug 2006

Publication series

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

Other

Other	13th International Workshop on Selected Areas in Cryptography, SAC 2006
Country	Canada
City	Montreal, QC
Period	17/08/06 → 18/08/06

Access to Document

Link to publication in Scopus

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

Cite this

Cho, J. Y., & Pieprzyk, J. (2007). Crossword puzzle attack on NLS. In E. Biham, & A. M. Youssef (Eds.), Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers (Vol. 4356 LNCS, pp. 249-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4356 LNCS). Springer, Springer Nature.

Cho, Joo Yeon ; Pieprzyk, Josef. / Crossword puzzle attack on NLS. Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers. editor / Eli Biham ; Amr M. Youssef. Vol. 4356 LNCS Berlin ; New York : Springer, Springer Nature, 2007. pp. 249-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a3c0c7c9ac8d46e88bfc662bf87f8940,

title = "Crossword puzzle attack on NLS",

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

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

year = "2007",

language = "English",

isbn = "9783540744610",

volume = "4356 LNCS",

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

publisher = "Springer, Springer Nature",

pages = "249--255",

editor = "Eli Biham and Youssef, {Amr M.}",

booktitle = "Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers",

address = "United States",

note = "13th International Workshop on Selected Areas in Cryptography, SAC 2006 ; Conference date: 17-08-2006 Through 18-08-2006",

}

Cho, JY & Pieprzyk, J 2007, Crossword puzzle attack on NLS. in E Biham & AM Youssef (eds), Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers. vol. 4356 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4356 LNCS, Springer, Springer Nature, Berlin ; New York, pp. 249-255, 13th International Workshop on Selected Areas in Cryptography, SAC 2006, Montreal, QC, Canada, 17/08/06.

Crossword puzzle attack on NLS. / Cho, Joo Yeon; Pieprzyk, Josef.

Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers. ed. / Eli Biham; Amr M. Youssef. Vol. 4356 LNCS Berlin ; New York : Springer, Springer Nature, 2007. p. 249-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4356 LNCS).

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

TY - GEN

T1 - Crossword puzzle attack on NLS

AU - Cho, Joo Yeon

AU - Pieprzyk, Josef

PY - 2007

Y1 - 2007

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

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

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

M3 - Conference proceeding contribution

AN - SCOPUS:38149092388

SN - 9783540744610

VL - 4356 LNCS

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

SP - 249

EP - 255

BT - Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers

A2 - Biham, Eli

A2 - Youssef, Amr M.

PB - Springer, Springer Nature

CY - Berlin ; New York

T2 - 13th International Workshop on Selected Areas in Cryptography, SAC 2006

Y2 - 17 August 2006 through 18 August 2006

ER -

Cho JY, Pieprzyk J. Crossword puzzle attack on NLS. In Biham E, Youssef AM, editors, Selected Areas in Cryptography - 13th International Workshop, SAC 2006, Revised Selected Papers. Vol. 4356 LNCS. Berlin ; New York: Springer, Springer Nature. 2007. p. 249-255. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).