Provable Security Evaluations of XOR-Versions of SNOW Family Stream Ciphers Against Fast Correlation Attacks

Fast correlation attack is one of the most powerful attack methods for LFSR-based stream ciphers, and the primary problem of the attack is to construct the linear approximations with great absolute correlations. For some stream ciphers with complex structures of linear approximations, the search for the maximum absolute correlation of linear approximations has always been a difficult problem because of the extremely high amount of masks that need to be searched. In this paper, an analysis method for searching maximum absolute correlation based on the linear mask structure is developed, including the filtering technology based on mask propagation trail, a structural characteristic of linear approximations of linear transformations with fewer active bytes, and linear approximation equivalence theorem of composite function composed of the parallel identical S-boxes and linear transformation. These methods efficiently reduce the exhaustive time complexity of the masks. As applications, this paper proves that the suprema of absolute correlations of all the linear approximations for the five XOR-versions of SNOW family stream ciphers (i.e., SNOW 2.0⊕, SNOW 3G⊕, SNOW-V⊕, SNOWVi ⊕, SNOW 5G⊕) are 2−9/2−15:893/2−37:964/2−37:964/2−37:964. The exhaustive time complexity of the masks can be reduced from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(232)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(296)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2384)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2384)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2384) to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(224)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(231.98)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(239.98)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(239.98)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(239.98), respectively. Furthermore, we give the provable security evaluations of the five ciphers against fast correlation attacks under the success probability of 0:99 for the known fast correlation attack method. For SNOW-V⊕/SNOW-Vi⊕/SNOW 5G⊕, the time/data/memory complexity of the optimal fast correlation attacks are all <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2227.54)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2227.72)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2227.72). The results show that SNOWV ⊕/SNOW-Vi⊕/SNOW 5G⊕ cannot guarantee the claimed 256- bit key security for the known fast correlation attack methods if we ignore the design constraint that the maximum length of keystream for a single pair of key and IV is 264. For SNOW 2.0⊕ and SNOW 3G⊕, the time/data/memory complexity of the optimal fast correlation attacks are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2151.94)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2151.35)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2151.35) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2165.91)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2165.43)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(2165.43), respectively. The results show that both SNOW 2.0⊕ and SNOW 3G⊕ can guarantee the claimed 128-bit key security for the known fast correlation attack methods. In addition, this paper also discusses that the existing fast correlation attacks based on multiple linear approximations are invalid for these five ciphers.

Authors

Sudong Ma (ORCID: https://orcid.org/0000-0001-5296-4424)
Chenhui Jin (ORCID: https://orcid.org/0000-0003-4941-7133)
Senpeng Wang (ORCID: https://orcid.org/0000-0002-2306-3720)
Xinxin Gong (ORCID: https://orcid.org/0000-0002-5155-9889)
Ting Cui (ORCID: https://orcid.org/0000-0002-8074-4581)
Jie Guan (ORCID: https://orcid.org/0000-0002-0827-1513)
Lin Ding (ORCID: https://orcid.org/0000-0003-1482-1750)

Institutions

PLA Information Engineering University (CN)
State Key Laboratory of Cryptology (CN)

Publication Details

Journal: IEEE Transactions on Information Theory
Published: 2025-04-29
DOI: https://doi.org/10.1109/tit.2025.3565463
Primary Topic: Cryptographic Implementations and Security
Type: article
Field-Weighted Citation Impact: 0.00

Funders

National Natural Science Foundation of China
Natural Science Foundation of Henan Province

Provable Security Evaluations of XOR-Versions of SNOW Family Stream Ciphers Against Fast Correlation Attacks

Authors

Institutions

Publication Details

Funders

Provable Security Evaluations of XOR-Versions of SNOW Family Stream Ciphers Against Fast Correlation Attacks

Provable Security Evaluations of XOR-Versions of SNOW Family Stream Ciphers Against Fast Correlation Attacks

Abstract

Ask Laika to Summarize, Analyze, and Connect papers live on the map.