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.

GEA-1 and GEA-2 are two standard stream ciphers used in GPRS (General Packet Radio Service) to protect against eavesdropping GPRS between the base station and the phone. Now, a range of current phones still support them. In this paper, a differential fault attack on the GEA-like stream ciphers under the random fault model is proposed for the first time. In this attack, an efficient dedicated algorithm for identifying the exact fault location is proposed. By using this dedicated algorithm, the attacker can succeed in determining the exact fault location. As applications, practical differential fault attacks on the GPRS standard ciphers (i.e., GEA-1 and GEA-2) are presented, which recover the 64-bit secret keys of GEA-1 and GEA-2 with time complexities of${2^{{\mathrm{{33}}}{\mathrm{{.807}}}}}$and${2^{{\mathrm{{33}}}{\mathrm{{.858}}}}}$, respectively. We validate the cryptanalytic results by simulating the whole attacks on the platform ChipWhisperer Lite. The experimental results show that both GEA-1 and GEA-2 can be broken within sixteen minutes on a common laptop. Finally, the possible countermeasures are presented to protect the processed data of massive GPRS devices.

With the increasing deployment of resource-constrained devices in daily life, ultra-lightweight ciphers become a necessity to tackle the security and privacy concerns in resource-constrained devices. In 2023, Gül and Kara studied the question of how to design a secure ultra-lightweight stream cipher with a small internal state, and introduced a new small-state stream cipher called DIZY. The cipher utilizes Truncated Pseudorandom Permutations (TPP) and has a provable security in the indistinguishability model. It consists of two versions, called DIZY-128 with a 128-bit key and DIZY-80 with an 80-bit key, respectively. In this paper, effective key recovery attacks on DIZY-80 and DIZY-128 are proposed. Both attacks leverage the weakness of DIZY that the attacker can easily reach a weak state in the middle of the initialization using chosen IVs. Based on constructing Hellman tables, the key recovery attacks on DIZY-80 and DIZY-128 are further improved. The cryptanalytic results show that DIZY-80/DIZY-128 can only provide a 65/86-bit security level against the key recovery attack, while it is claimed to provide an 80/112-bit security level by the designers. Finally, an improved variant of DIZY, called DIZYa, is proposed. The analysis on DIZYa shows that the improved variant can provide better security resistance against all known attacks including our attacks on DIZY, while maintaining the commendable characteristics of DIZY. This makes DIZYa a more suitable small-state stream cipher choice for resource-constrained devices like RFID tags.

ARX-based design is a major building block of modern cryptographic ciphers due to its efficiency in software. Forró is an ARX-based stream cipher proposed by Coutinho et al. at ASIACRYPT 2022, which was designed to provide higher security margin than the ChaCha stream cipher. In this paper, we propose a full automated MILP model calledMinForró, to derive linear approximations for the Forró stream cipher. For the differential part, a two-stage strategy to search for single-bit differential trails with high differential correlations is presented, which helps us to find the first-ever 3-round differential trails for Forró. By combining the linear approximations obtained byMinForróand 3-round differential trail for Forró, we propose improved differential-linear distinguishers for 4-, 5-, 5.25-, 5.5-, 5.75-, 6-, 6.25- and 6.5-round Forró with complexities 232.44, 246, 250, 264.32, 287.12, 2117.92, 2174.92and 2226.88, respectively. The proposed differential-linear distinguishers for 4-, 5-, 5.25- and 5.5- round Forró significantly improve the existing distinguishers by factors of 24.11, 283.68, 2127.64and 2178.20, respectively. To the best of our knowledge, this is the first differential-linear distinguisher for Forró that reaches 6.5 rounds, which is a significant advancement over the existing record of 5.5 rounds. We have implemented the differential-linear distinguishers for 4- and 5- round Forró on a common PC, and the experimental results confirm the correctness of these distinguishers. Furthermore, when combined with theProbabilistic Neutral Bits(PNB) technique, we obtain key recovery attacks on 5.5-, 6-, 6.5- and 6.75-round Forró with time complexities 2149.20, 2151.84, 2213.49and 2251.97, respectively. The proposed key recovery attack on 5.5-round Forró significantly improves the time complexity of the existing attack by a factor of 275.84. To the best of our knowledge, this is the first key recovery attack on Forró that reaches 6.75 rounds, which is a significant advancement over the existing record of 5.5 rounds.

ChaCha is currently one of the most widely used symmetric ciphers. At FSE 2023, Bellini et al. proposed a four-round differential-linear distinguisher with a correlation of 2−34.15. Recently, Xu et al. improved the correlation of this four-round distinguisher to 2−32.2by considering the differential-linear hull effect. In this paper, we present a new linear approximation from 5-round to 6.5-round for ChaCha256. Combining this new linear approximation with the four-round differential-linear distinguisher, we propose the first differential-linear distinguisher for 6.5-round ChaCha256 with complexity 2112.84. Furthermore, we use the MILP tool to obtain a linear approximation from 6.5-round to 7-round, and then a new differential-linear distinguisher for 7-round ChaCha256 with complexity 2161.92is proposed. It is 24.97times faster than the previous best attack.

GEA-1 and its successor GEA-2 are stream ciphers that were selected as the General Packet Radio Service (GPRS) standard encryption algorithms, used to protect the communication between phones and base stations from eavesdropping. These stream ciphers, once widely used for GPRS encryption in the late 1990s and early 2000s, are surprisingly still supported in many current mobile phones and in numerous developing regions even today. GEA-2a is a more secure, improved version of GEA-2 designed by Ding et al. in 2022. Side channel attack utilizes easily accessible information from cryptographic devices, such as power consumption, electromagnetic radiation, and runtime, to obtain secret information in the cryptographic systems. Side channel attack is a powerful attack method that has been successfully applied in many stream ciphers, such as TRIVIUM and GRAIN-128-AEAD. In this article, we put forward an automated framework that can mount side channel attack on stream ciphers with structures similar to the GPRS standard encryption algorithms GEA-1 and GEA-2. We use satisfiability modulo theory for modeling, while considering the software and hardware implementation of the algorithms, and use Microsoft’s open source solver Z3 to solve the constructed instances. The experimental results indicate that the internal states of GEA-1, GEA-2, and GEA-2a in the keystream generation phase can be recovered practically under the HW/32 model. For models where the solution time is too long, by guessing a small number of bits, the state bits can be fully recovered within an acceptable time. Our automated framework is effective in both noiseless and noisy trace scenarios.

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 To guarantee the security of symmetric key schemes against quantum adversary, developing quantum cryptanalytic techniques becomes a major worldwide challenge in the post-quantum world. In this paper, we present a general framework of classical guess and determine attack on stream ciphers, and then convert it into quantum guess and determine attack. It shows that, for a given stream cipher with a key size of $k$ bits and an internal state size of $n$ bits, if a basic guess and determine attack with a time complexity below $O ( {{{2}^{{3k}/{2}}}}/{n} )$ is available, there is a quantum guess and determine attack with multiple data that can recover all $n$ internal state bits of the cipher with complexity below $O ( {{2^{k / 2}}} )$. As applications, we present quantum guess and determine attacks on the SNOW-like stream ciphers. The results show that all of SNOW 1.0 with 128-bit key, SNOW 2.0 with 128-bit key and SOSEMANUK are insecure against quantum guess and determine attack. The resource requirements for implementing a quantum guess and determine attack on SNOW 3G are evaluated as a case study. To the best of our knowledge, this is the first time that the general quantum guess and determine attack is formally proposed and applied to the SNOW-like stream ciphers.

GEA‐1, a proprietary stream cipher, was initially designed and used to protect against eavesdropping general packet radio service (GPRS) between the phone and the base station. Now, a variety of current mobile phones still support this standard cipher. In this paper, a structural weakness of the GEA‐1 stream cipher that has not been found in previous works is discovered and analyzed. That is the probability that two different inputs of GEA‐1 generate the identical keystream can be up to 2 −7.30 , which is quite high compared with an ideal stream cipher that generates random sequences. Based on this newfound weakness, a new practical distinguishing attack on GEA‐1 is proposed, which shows that the keystreams generated by GEA‐1 are far from random and can be easily distinguished with a practical time cost. After then, a new practical key recovery attack on GEA‐1 is presented. It has a time complexity of 2 21.02 GEA‐1 encryptions and requires only seven related keys, which is much less than the existing related key attack on GEA‐1. The experimental results show that GEA‐1 can be broken within about 41.75 s on a common PC in the related key setting. These cryptanalytic results show that GEA‐1 cannot provide enough security and should be immediately prohibited to be supported in the massive GPRS devices.

The DECT Standard Cipher (DSC) is a proprietary stream cipher used for encryption in the Digital Enhanced Cordless Telecommunications (DECT), which is a standard for short range cordless communication and widely deployed worldwide both in residential and enterprise environments. New weaknesses of the DSC stream cipher which are not discovered in previous works are explored and analyzed in this paper. Based on these weaknesses, new practical key recovery attacks and distinguishing attack on DSC with lower time cost are proposed. The first cryptanalytic result show that DSC can be broken in about 13.12 seconds in the known IV setting, when an offline phase that takes about 58.33 minutes is completed. After then, a distinguishing attack on DSC in the related key chosen IV setting is given, which has a time complexity of only 2 encryptions and a success probability of almost 1. Finally, based on the slide property, a key recovery attack on DSC with practical complexities is proposed. The experimental result shows that DSC can be broken on a common PC within about 44.97 seconds in the multiple related key setting. The attacks on DSC proposed in this paper clearly show that a well-designed initialization is absolutely necessary to design a secure stream cipher.

In this paper, a general model for evaluating the correlations of correlation attack distinguishers for an LFSR-based stream cipher is given by the Walsh spectrum theory of composite functions. We transform equivalently the linear approximations with$k$consecutive keystream words into that of a composite function consisting of several simple functions, which enables cryptanalysts to derive linear approximations of any LFSR-based stream cipher by this model and to search for linear trails with high absolute correlations. This model suits any LFSR-based stream cipher, does not need the implicit independence assumption widely used in previous cryptanalysis, and can theoretically ensure that the correlation obtained is the accurate correlation of a correlation attack distinguisher. In addition, we prove that it is enough to consider the distinguishers where the masks of all LFSR elements are zero except for those of a maximal linearly independent system of LFSR elements involved in the update function and output function. As applications, the approximation processes for the correlation attack distinguishers of SNOW-V, SNOW2.0, ZUC, and Grain-128 are exhibited respectively by this method. Moreover, by the proposed method we can perform a full coverage search for binary linear approximations of them. For SNOW-V, we prove that the approximation given by our model is equivalent to that by Shi et al. at EUROCRYPT 2022, and is simpler and more intuitive. For SNOW2.0, we find more linear approximations with the best correlation. For ZUC, for the first time we get the accurate correlations of a series of linear approximations including the known results, and give the supremum of the absolute correlations for a larger set of linear approximations. For Grain-128, utilizing our method, we rediscover the best known correlation as well, which provides more support for the validity of our general model. Our work can give some evidence for the provable security of LFSR-based stream ciphers against correlation attack to some extent, and may provide the key clues in the analysis of complex stream ciphers.

GEA-1 and its successor GEA-2 are two stream ciphers, designed to protect against eavesdropping General Packet Radio Service (GPRS) between the phone and the base station. They were widely used for GPRS encryption in the late 1990s and during the 2000s, and are surprisingly still supported in a range of current mobile phones. In this paper, new key recovery attacks on GEA-1 and GEA-2 are proposed by combining with the time-memory trade-off technique. The new attacks significantly reduce the time and memory costs of the previous attacks on GEA-1, and show that GEA-1 only offers 32-bit (out of 64) security. Furthermore, the slide properties of GEA-1 and GEA-2 are first found and used to explore practical related key attacks. The results show that GEA-1 and GEA-2 can be broken on a common PC within about 0.81 and 6.2 seconds in the multiple related key setting, respectively. Finally, an improved variant of GEA-2 called GEA-2a is proposed. The reasons for making the changes from GEA-2 are explained in detail, which indicates that GEA-2a has significantly better resistance than GEA-2 against all known attacks and can offer 64-bit security.

ACORN v3 is a lightweight authenticated encryption cipher, which was selected as one of the seven finalists of CAESAR competition in March 2018. It is intended for lightweight applications (resource-constrained environments). By using the technique numeric mapping proposed at CRYPTO 2017, an efficient algorithm for algebraic degree estimation of ACORN v3 is proposed. As a result, new distinguishing attacks on 647, 649, 670, 704, and 721 initialization rounds of ACORN v3 are obtained, respectively. So far, as we know, all of our distinguishing attacks on ACORN v3 are the best. The effectiveness and accuracy of our algorithm is confirmed by the experimental results.

The well-known Welch–Gong (WG) stream cipher, proposed by Nawaz and Gong in 2005, was submitted to the hardware profile of the eSTREAM project. In the last several years, the original WG has come under several cryptanalytic attacks. However, as for the final version of WG, no attack has been published on it until now. In this paper, an efficient key recovery attack on the final WG stream cipher in the related key setting is proposed. Under related keys, we can recover the 128-bit secret key of WG-128 with a time complexity of |$2^{89}$| and a memory complexity of |$2^{45}$|⁠. The success probability of the attack is 0.6321. This result shows that our attack on WG-128 is much better than an exhaustive key search in the related key setting. Furthermore, our cryptanalytic results show that WG with IV size no less than 80 bits is vulnerable to a related key attack. The main feature of our attack is that it is independent of the number of steps in the key/IV setup of WG, and then increasing the number of steps in the key/IV setup cannot strengthen the resistance of WG against a related key attack. Finally, a recommended approach to repair the weakness and strengthen the resistance of WG against a related key attack is presented.

WG-8 is a new lightweight variant of the well-known Welch-Gong (WG) stream cipher family, and takes an 80-bit secret key and an 80-bit initial vector (IV) as inputs. So far no attack on the WG-8 stream cipher has been published except the attacks by the designers. This paper shows that there exist Key-IV pairs for WG-8 that can generate keystreams, which are exact shifts of each other throughout the keystream generation. By exploiting this slide property, an effective key recovery attack on WG-8 in the related key setting is proposed, which has a time complexity of 253.32and requires 252chosen IVs. The attack is minimal in the sense that it only requires one related key. Furthermore, we present an efficient key recovery attack on WG-8 in the multiple related key setting. As confirmed by the experimental results, our attack recovers all 80 bits of WG-8 in on a PC with 2.5-GHz Intel Pentium 4 processor. This is the first time that a weakness is presented for WG-8, assuming that the attacker can obtain only a few dozen consecutive keystream bits for each IV. Finally, we give a new Key/IV loading proposal for WG-8, which takes an 80-bit secret key and a 64-bit IV as inputs. The new proposal keeps the basic structure of WG-8 and provides enough resistance against our related key attacks.

ABSTRACT MICKEY 2.0 is a synchronous hardware‐oriented stream cipher designed by Steve Babbage and Matthew Dodd in 2006. It was submitted to eSTREAM and became one of the seven eSTREAM finalists. MICKEY‐128 2.0 is a variant version with 128‐bit secret key. In this paper, we present a weakness in the initialization of MICKEY family of stream ciphers (i.e., MICKEY 2.0 and MICKEY‐128 2.0). With this weakness, we apply a slide resynchronization attack to them, which finds for any K with k0 = d and for any IV with ivn = d, there is a (K′, IV′) pair with probability 2− 1 that generates 1‐bit shifted keystream, where d ∈ {0, 1} is a constant. Furthermore, we propose related key attacks on MICKEY family of stream ciphers. Our attacks can break these two ciphers in real time on a PC when 65 and 113 related (K, IV) pairs for MICKEY 2.0 and MICKEY‐128 2.0 are obtained, respectively. The success probabilities of our attacks on MICKEY 2.0 and MICKEY‐1282.0 are 0.9835 and 0.9714, respectively. This is the first paper presenting a weakness in MICKEY family of stream ciphers, and the results show that MICKEY family of stream ciphers are extremely weak against related key attacks. Copyright © 2012 John Wiley & Sons, Ltd.

The well-known stream cipher Grain-128 is a variant version of Grain v1 with 128-bit secret key. Grain v1 is a stream cipher which has successfully been chosen as one of seven finalists by European eSTREAM project. Yet Grain-128 is vulnerable against some recently introduced attacks. A new version of Grain-128 with authentication, named Grain-128a, is proposed by Ågren, Hell, Johansson, and Meier. The designers claimed that Grain-128a is strengthened against all known attacks and observations on the original Grain-128. So far there exists no attack on Grain-128a except a differential fault attack by Banik, Maitra, and Sarkar. In this paper, we give some observations on Grain-128a, and then propose a related key chosen IV attack on Grain-128a based on these observations. Our attack can recover the 128-bit secret key of Grain-128a with a computational complexity of$2^{96.322} $, requiring$2^{96} $chosen IVs and$2^{103.613} $keystream bits. The success probability of our attack is 0.632. This related key attack is “minimal” in the sense that it only requires two related keys. The result shows that our attack is much better than an exhaustive key search in the related key setting.

Loiss is a new byte-oriented stream cipher designed in 2010. It takes a 128-bit initial key and a 128-bit initial vector (IV) as inputs, and provides 128-bit-level security claimed by the designers. In this paper, we find a differential characteristic with significant probability over the full initialization of Loiss. Based on this differential characteristic, two differential key recovery attacks on Loiss are proposed. The first attack has a computational complexity of2123.61, requiring two related keys, 234.16 chosen IVs and 239.16 keystream bytes. The second attack is based on the first attack: reducing the computational complexity at the cost of increased data complexity. The second attack has a computational complexity of 264, requiring two related keys, 236.26 chosen IVs and 241.26 keystream bytes. The result shows that our second attack is much better than a brute force attack, and then Loiss does not provide 128-bit-level security. Furthermore, a new proposal for the initialization of Loiss is proposed. The modified Loiss keeps the basic structure of Loiss and provides enough resistance against our attacks on the original Loiss. Based on our security analysis, we conjecture that no attacks lower than brute force are possible on the modified Loiss stream cipher.

SOSEMANUK is a new synchronous software-oriented stream cipher with a variable-length key between 128 and 256 bits. In this paper, a guess and determine (GD) attack on the cipher is introduced with a computational complexity of O(2192), requiring only 7 keystream words. The results show that the cipher does not provide full security when the key of the length more than 192 bits is used.