Paper 2007/038

Multiple Modular Additions and Crossword Puzzle Attack on NLSv2

Joo Yeon Cho and Josef Pieprzyk

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 the 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 process after observing around $2^{74}$ keystream words.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Distinguishing AttacksCrossword Puzzle AttackStream CipherseSTREAMNLSNLSv2
Contact author(s)
jooyeon cho @ gmail com
History
2007-03-26: revised
2007-02-14: received
See all versions
Short URL
https://ia.cr/2007/038
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/038,
      author = {Joo Yeon Cho and Josef Pieprzyk},
      title = {Multiple Modular Additions and Crossword Puzzle Attack on NLSv2},
      howpublished = {Cryptology ePrint Archive, Paper 2007/038},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/038}},
      url = {https://eprint.iacr.org/2007/038}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.