SNOW 2.0 is a word-oriented stream cipher that has been standardized by ISO/IEC 18033-4. At FSE 2006, Nyberg et al. proposed a linear distinguisher for SNOW 2.0 with absolute correlation 2−85:89, derived from four linear approximations of the Finite State Machine (FSM). When deriving the overall correlation, they assumed these four linear approximations to be mutually independent. However, they are in fact dependent because of a shared variable, which leads to the inaccuracy of the correlation calculation. Moreover, they impose the unnecessary restriction that all masks of the distinguisher must be identical, artificially limiting the search space and yielding inaccurate conclusions about the minimum number of active S-boxes. To resolve these contradictions, we first establish a general SNOW 2.0 linear distinguisher without any unnecessary restrictions. Secondly, we present and prove an exact formula to calculate the correlations of the general SNOW 2.0 distinguishers, thereby correcting the current best absolute correlation from 2−85:89to 2−86:14. Thirdly, we establish an Mixed Integer Linear Programming (MILP) model to search for the optimal SNOW 2.0 linear approximation trail, which will be used to derive both the optimal linear approximation trail and the minimum number of active S-boxes. The results prove that the maximum absolute correlation of the SNOW 2.0 linear approximation trail is no higher than 2−75. Consequently, if the maximum absolute correlation of the linear approximation trail is taken as the security measure, then SNOW 2.0 can guarantee the 128-bit security level against the linear distinguishing attack. Based on the MILP model, we prove that the minimum number of active S-boxes of the linear distinguisher is 12, not 14 as previously reported. Finally, we observe that the identical distinguisher masks tend to yield high absolute correlation. We therefore exhaustively enumerate this large class of distinguishers and find that the best absolute correlation remains 2−86:14. Then the time/data complexity of the linear distinguishing attack on SNOW 2.0 can be evaluated as 2172:28. Additionally, our formula reveals another distinguisher whose true correlation is 2−88:37, while the result calculated by the original formula is 2−107:23. These results demonstrate that ignoring the dependency among approximations can lead to significant underestimation of the correlation.

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 fromO(232)/O(296)/O(2384)/O(2384)/O(2384) toO(224)/O(231.98)/O(239.98)/O(239.98)/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 allO(2227.54)/O(2227.72)/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 areO(2151.94)/O(2151.35)/O(2151.35) andO(2165.91)/O(2165.43)/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.

Abstract It had always been believed that there was an inherent barrier to Differential Fault Attack (DFA) on the nonce-based authenticated encryption algorithm. At CHES 2016, Saha et al. proposed an Internal Differential Fault Attack on a parallelizable counter-mode algorithm. They induce the attack to classical DFA at the expense of one more fault injection in every encryption process. In this paper, we propose the DFA on HYENA, which is a nonce-based authenticated encryption mode for GIFT-128. Our work is the first pure classical DFA on a nonce-based authenticated encryption algorithm with only one fault injected in every decryption process. Firstly, we give the DFA on GIFT-128 with a fault injected into the 39th-round input. Based on this work, we inject a fault in the underlying GIFT-128 of a HYENA decryption process and make this decryption process still generate the correct tag and output plaintext. This makes the necessary conditions of DFA satisfied. Experiments show that at most 56 key bits of HYENA can be recovered with only a few faulty ciphertexts. In addition, our fault injection is easier to achieve than most other work about fault attack, because the injection location is relatively random and the fault type can be arbitrary. It should be noted that the left 72 key bits cannot be recovered in this way.

At CRYPTO 2018, Todo et al. proposed an effective fast correlation attack using multiple linear approximations, and gave effective attacks on the Grain-like stream ciphers with the same size of LFSR and key. However, many stream ciphers require that the size of LFSR must be at least twice the key size. For this type of stream ciphers, we propose an improved fast correlation attack using multiple linear approximations. The main idea is to reduce the number of attacked bits of parity-check equations by XORing the same linear approximation at different clocks, and then further bypass some unknown variables of parity-check equations by multiple linear approximations with an expected probability. Finally, full unknown variables are recovered by solving systems of linear equations. SOSEMANUK is one of the finalists in the eSTREAM project. The best absolute correlation of linear approximations of SOSEMANUK we found is 2-20.84, which improves the linear approximations with current best absolute correlation of 2-21.41. Finally, the improved fast correlation attack method is applied to SOSEMANUK, and a fast correlation attack with time/data/memory complexity ofO(2139.75)/O(2139.37)/O(2139.37) is given, and the success probability is 0.99. It improves the current best fast correlation attack with time/data/memory complexity ofO(2147.88)/O(2145.5)/O(2147.1) (ASIACRYPT 2008). For the optional key size ranging from 128-bit to 256-bit of SOSEMANUK, our attack result shows that SOSEMANUK can only guarantee the security of 140-bit key. In addition, we declare that our new fast correlation attack method can be applied to the linear analysis of other LFSR-based stream ciphers.

SNOW-V and SNOW-Vi are two new LFSR-based stream ciphers of the SNOW family designed for the 5G mobile communication system. Correlation attack is a well-known cryptanalysis tool for LFSR-based stream ciphers. The first step of a correlation attack is to establish a linear approximation of the cipher with high correlation. The process can be modeled and solved by automatic techniques. How to efficiently model the 8-bit S-box and how to give an effective search strategy are two challenges to automatically search for linear approximations of SNOW-V-like ciphers. For the first problem, we propose a divide-and-conquer dimension reduction method for modeling large S-boxes with Mixed Integer Linear Programming (MILP). It can transform the problem of modeling a high-dimensional set into sub-problems of modeling some low-dimensional sets. For the second problem, we propose an efficient heuristic MILP search algorithm for SNOW-V-like ciphers, which is applied to searching for the linear approximations of SNOW-V, SNOW-Vi, SNOW-Vi⊞32,⊞8, SNOW-Vi⊞16,⊞16and SNOW-Viσ0ciphers with high absolute correlations. Then we get the best absolute correlations of these ciphers at present, where the linear approximation of SNOW-Vi with the absolute correlation 2-45.796improves the absolute correlation 2-47.76proposed at EUROCRYPT 2022 by Shi et al. and the absolute correlation 2-47.567proposed at DCC 2022 by Zhou et al. Thus, a correlation attack with time/data/memory complexity of 2243.79/2235.08/2235.08is got. It is also the best state recovery attack at present. Thirdly, to simplify the search algorithm of the linear approximations of SNOW-V, we give two sufficient conditions under which a linear approximation of SNOW-Vi is also a linear approximation of SNOW-V. It can be proved that the correlation attack on SNOW-V has the same attack complexity as SNOW-Vi. Finally, for SNOW-Vi⊞32,⊞8and SNOW-Viσ0, we give the best state recovery attacks so far. The current best state recovery attacks of SNOW-Vi⊞32,⊞8and SNOW-Viσ0can be reduced by a factor of 264and 262, respectively. We also give the first attack on SNOW-Vi⊞16,⊞16. We emphasize that the new heuristic MILP model can be applied to the security evaluation of correlation attacks on the LFSR-based stream cipher structures. In addition, note that the existing fast correlation attacks, including our attacks do not threaten the security of SNOW-V-like ciphers because of the design constraint that the maximum length of keystream for a single pair of key and IV vectors is 264.

K2 is an LFSR-based dynamic feedback stream cipher and has been standardized by ISO/IEC 18033-4. The fast correlation attack (FCA) is a well-known cryptanalysis tool for LFSR-based stream ciphers. In this paper, we propose a guess-and-determine FCA on a dynamic feedback stream ciphers model. Moreover, we give a fast calculation method to calculate the correlation of the function$F(x,y,z)=x\boxplus _{n} S(y)\boxminus _{n} z$by directly characterizing subtraction modulo$2^{n}$. Then we propose a kind of mask structure of the linear approximations of the function$F(x,y,z)$with high correlations. The structural characteristics of the kind of masks reduce both the time complexity of the fast calculation and the memory complexity of connection matrices, which enables us to efficiently search for linear approximations with high correlations. Based on the structural characteristics and the analysis of the number of active S-boxes of the linear approximations of K2, we present an effective search strategy, where the number of active S-boxes is 4. The best absolute correlation we found is$2^{-24.21}$. Finally, we study the resistance of K2 against the FCA. For any of the four variants of K2, we give the best key recovery attack so far. The time/data/memory complexity is$O(2^{190.06})/O(2^{189.80})/O(2^{188.80})$, respectively. The results indicate that the four variants of K2 cannot guarantee the claimed 192-bit and 256-bit security if we ignore the design constraint that the maximum keystream length for a single pair of key and IV is limited to$2^{64}$. For the full version of K2, we present the first FCA, which is also the best attack result yet. And the time/data/memory complexity is$O(2^{313.57})/O(2^{149.02})/O(2^{148.02})$, respectively. The large security redundancy indicates that the dynamic feedback structure provides higher security.

Abstract The K2 stream cipher, designed for 32-bit words, is an ISO/IEC 18033 standard and is listed as a recommended algorithm used by the Japanese government in the CRYPTREC project. The main feature of the K2 algorithm is the use of a dynamic feedback control mechanism between the two linear feedback shift registers, which makes the analysis of the K2 algorithm more difficult. In this paper, for its simplified version algorithm, a key recovery attack is performed by using differential attacks. Firstly, for the unknown key, the same IV is fixed in two chosen IV differential attacks, and we use the input differences and the output differences of the S-box to recover the input of S-box; the internal state values can be uniquely determined by taking intersection of the input of S-box. This technology is used to improve the key recovery attack of seven-round algorithm proposed by Deike Priemuth-Schmid. Secondly, we find the constraint relationship between the keystream equations and the unknown differences by introducing the guess difference bit and eliminate the impossible differences by the constraint relationship. Thus, we expand the key recovery attack from seven to nine rounds. The time complexity of the attack is $\boldsymbol{O} \boldsymbol{(2^{113.93})}$, the data complexity is $\boldsymbol{O}\boldsymbol{(2^{8.71})}$ and the success rate is $\textbf{99.07\%}$.

The stream cipher SNOW 3G is the core of the 3G Partnership Project (3GPP) for implementing a confidentiality algorithm and data integrity algorithm. In this study, the authors analyse the initialisation stage based on the chosen IV differential attacks on the reduced‐round SNOW 3G and SNOW . Firstly, they show a distinguisher for 12‐round SNOW 3G and 255 distinguishers for 13‐round SNOW , respectively. Secondly, they use the input differences and the output differences of the S‐box to recover the input of S‐box, which can recover full keys in real‐time for 12‐round SNOW . The data complexity is 36 and the time complexity is small. Finally, they use the impossible differences of the S‐box as a filter to extend the initialisation rounds of the attack to 16‐round SNOW . The data complexity is 28 and the time complexity is . So far, the authors’ attack results are the best in terms of chosen IV differential attacks. At the same time, their attack results are superior to multiset collision attacks in terms of data complexity, and their attack method can recover full keys, while multiset collision attacks can only partially recover the internal states in 15‐round SNOW .