Paper 2006/049 Original: eprint.iacr.org/2006/049 ↗
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 newly 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 $Konst$ 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 average bias to be around $O(2^{-30})$. Therefore, we claim that NLS is distinguishable from truly random cipher after observing $O(2^{60})$ keystream words on the average. The experiments also show that our distinguishing attack is successful on $90.3\%$ of $Konst$ among $2^{32}$ possible values.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2006-03-08: last updated
- 2006-02-14: published
- Short URL
- https://ia.cr/2006/049
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2006/049,
author = {Joo Yeon Cho and Josef Pieprzyk},
title = {Crossword Puzzle Attack on NLS},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/049},
year = {2006},
url = {https://eprint.iacr.org/2006/049}
}