@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",
}