Cryptology ePrint Archive: Report 2006/049

Crossword Puzzle Attack on NLS

Joo Yeon Cho and Josef Pieprzyk

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.

Category / Keywords: Distinguishing Attacks, Stream Ciphers, Linear Approximations, eSTREAM, NLS, Crossword Puzzle Attack

Date: received 9 Feb 2006, last revised 8 Mar 2006

Contact author: jcho at ics mq edu au

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: This is an extended version of the paper which was presented in SASC 2006.

Version: 20060308:102445 (All versions of this report)

Discussion forum: Show discussion | Start new discussion