Cryptology ePrint Archive: Report 2014/277

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

Lin Ding and Chenhui Jin and 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.

Category / Keywords: secret-key cryptography / Cryptanalysis; Time-memory-data tradeoff attack; BSW sampling; Guess and Determine attack; Stream cipher; MICKEY; Grain; SOSEMANUK.

Original Publication (in the same form): AFRICACRYPT 2014

Date: received 21 Apr 2014

Contact author: dinglin_cipher at 163 com

Available format(s): PDF | BibTeX Citation

Version: 20140421:211838 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]