Fast computation of linear approximation over certain composition functions and applications to SNOW 2.0 and SNOW 3G
- PDF / 586,503 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 136 Views
Fast computation of linear approximation over certain composition functions and applications to SNOW 2.0 and SNOW 3G Xinxin Gong1
· Bin Zhang1,2,3
Received: 14 July 2019 / Revised: 16 May 2020 / Accepted: 13 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study the linear approximation of certain composition functions, with applications to SNOW 2.0 and SNOW 3G. We first propose an efficient algorithm to compute the linear approximation of certain composition functions with parallel operations, which has a linear-time complexity for any given mask tuple, and thus allows for a wide range of search for linear approximations. Naturally, we apply this algorithm to compute the linear approximations of the FSM of both SNOW 2.0 and SNOW 3G. For SNOW 2.0, we compute the linear approximation of the FSM for a wide range of linear masks, and obtain some results which enable us to slightly improve the data complexity of the known fast correlation attacks, by using multiple linear approximations and combining a small technique when applying the k-tree algorithm. For SNOW 3G, we make a careful search for the linear approximations of the FSM and obtain many mask tuples which yield high correlations. Using these linear approximations, we mount a fast correlation attack on SNOW 3G and recover the initial state of the LFSR with the total time complexity 2222.33 and memory complexity 2221.74 , given 2220.74 keystream words. Our attack does not pose a threat to the claimed 128-bit security of SNOW 3G. Keywords Stream ciphers · SNOW 2.0 · SNOW 3G · FSM · Linear approximation · Fast correlation attack Mathematics Subject Classification 94A60 · 68P25
Communicated by T. Iwata.
B B
Xinxin Gong [email protected] Bin Zhang [email protected]
1
State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
2
TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China
3
University of Chinese Academy of Sciences, Beijing 100049, China
123
X. Gong, B. Zhang
1 Introduction A stream cipher ensures the privacy of the message transmitted over a communication channel. In such algorithms, the ciphertext is usually the XOR sum of the generated keystream and the plaintext, resembling the one-time pad principal. A classical class of stream ciphers is designed based on the binary linear feedback shift registers (LFSR) to generate the keystream from the underlying LFSR sequence, and for which correlation attack is a must-try cryptanalysis method. With the development of modern computer science, many word-oriented stream ciphers are proposed, which are based on the LFSR over the extension fields of the binary field F2 , and a non-linear combiner, with or without memory. The typical examples include SOSEMANUK [1], SNOW 2.0 [8], SNOW 3G [10], and SNOW-V [9]. In general, fast correlation attacks are commonly regarded as classical methods for such primitives. Fast correlation attack was first introduced by Meier and Staffelbach in 1989 [17], a
Data Loading...
