Paper 2014/277

New Treatment of the BSW Sampling and Its Applications to Stream Ciphers

Lin Ding, Chenhui Jin, Jie Guan, and Chuanda Qi

Abstract

By combining the time-memory-data tradeoff (TMDTO) attack independently proposed by Babbage and Golić (BG) with the BSW sampling technique, this paper explores to mount a new TMDTO attack on stream ciphers. The new attack gives a wider variety of trade-offs, compared with original BG-TMDTO attack. It is efficient when multiple data is allowed for the attacker from the same key with different IVs, even though the internal state size is twice the key size. We apply the new attack to MICKEY and Grain stream ciphers, and improves the existing TMDTO attacks on them. Our attacks on Grain v1 and Grain-128 stream ciphers are rather attractive in the respect that the online time, offline time and memory complexities are all better than an exhaustive key search, and the amount of keystream needed are completely valid. Finally, we generalize the new attack to a Guess and Determine-TMDTO attack on stream ciphers, and mount a Guess and Determine-TMDTO attack on SOSEMANUK stream cipher with the online time and offline time complexities both equal to $2^{128}$, which achieves the best time complexity level compared with all existing attacks on SOSEMANUK so far.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. AFRICACRYPT 2014
Keywords
CryptanalysisTime-memory-data tradeoff attackBSW samplingGuess and Determine attackStream cipherMICKEYGrainSOSEMANUK.
Contact author(s)
dinglin_cipher @ 163 com
History
2014-04-21: received
Short URL
https://ia.cr/2014/277
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/277,
      author = {Lin Ding and Chenhui Jin and Jie Guan and Chuanda Qi},
      title = {New Treatment of the BSW Sampling and Its Applications to Stream Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/277},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/277}},
      url = {https://eprint.iacr.org/2014/277}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.