International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Resistance of SNOW-V against Fast Correlation Attacks

Authors:
Xinxin Gong , State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China
Bin Zhang , TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China; University of Chinese Academy of Sciences, Beijing, 100049, China; Guizhou shujubao Netw
Download:
DOI: 10.46586/tosc.v2021.i1.378-410
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8843
Search ePrint
Search Google
Abstract: SNOW-V is a new member in the SNOW family of stream ciphers, hoping to be competitive in the 5G mobile communication system. In this paper, we study the resistance of SNOW-V against bitwise fast correlation attacks by constructing bitwise linear approximations. First, we propose and summarize some efficient algorithms using the slice-like techniques to compute the bitwise linear approximations of certain types of composition functions composed of basic operations like ⊞, ⊕, Permutation, and S-box, which have been widely used in word-oriented stream ciphers such as SNOW-like ciphers. Then, using these algorithms, we find a number of stronger linear approximations for the FSM of the two variants of SNOW-V given in the design document, i.e., SNOW-V σ0 and SNOW-V⊞8, ⊞8. For SNOW-V σ0, where there is no byte-wise permutation, we find some bitwise linear approximations of the FSM with the SEI (Squared Euclidean Imbalance) around 2−37.34 and mount a bitwise fast correlation attack with the time complexity 2251.93 and memory complexity 2244, given 2103.83 keystream outputs, which improves greatly the results in the design document. For SNOW-V⊞8, ⊞8, where both of the two 32-bit adders in the FSM are replaced by 8-bit adders, we find our best bitwise linear approximations of the FSM with the SEI 2−174.14, while the best byte-wise linear approximation in the design document of SNOW-V has the SEI 2−214.80. Finally, we study the security of a closer variant of SNOW-V, denoted by SNOW-V⊞32, ⊞8, where only the 32-bit adder used for updating the first register is replaced by the 8-bit adder, while everything else remains identical. For SNOW-V⊞32, ⊞8, we derive many mask tuples yielding the bitwise linear approximations of the FSM with the SEI larger than 2−184. Using these linear approximations, we mount a fast correlation attack with the time complexity 2377.01 and a memory complexity 2363, given 2253.73 keystream outputs. Note that neither of our attack threatens the security of SNOW-V. We hope our research could further help in understanding bitwise linear approximation attacks and also the structure of SNOW-like stream ciphers.
BibTeX
@article{tosc-2021-30955,
  title={Resistance of SNOW-V against Fast Correlation Attacks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 1},
  pages={378-410},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8843},
  doi={10.46586/tosc.v2021.i1.378-410},
  author={Xinxin Gong and Bin Zhang},
  year=2021
}