Cryptanalysis Of ESTREAM Candidates

In 2004, ECRYPT (European Network of Excellence for Cryptology), a 4-year European research initiative, was launched. It's main purpose is to intensify the collaboration of European researchers in information security, especially in cryptology and digital watermarking. eSTREAM (ECRYPT Stream Cipher Project) is a project of ECRYPT to identify new stream ciphers that might suitable for widespread adoption. It was set up because none of six stream ciphers submitted to NESSIE project had been selected as the portfolio. The call for primitives was first issued in November 2004, and 34 primitives were submitted until April 2005. After three evaluation phases in four years, the project was completed with 8 primitives being the finalist portfolios in April 2008. Since the second evaluation phase, 8 algorithms in phase 2, 3 algorithms in phase 3, and 1 portfolio have been broken.Under the guidance of my supervisors, we mainly analyzes 4 candidate algorithms to eSTREAM Project ABC v3 (Phase 2), TSC-4 (Phase 2), CryptMT v3 (Phase 3), Grain v1 (portfolio): break ABC v3 and TSC-4 with weak keys, find a differential characteristic in the key initialization process of CryptMT v3 with probability 1, and break Grain vl with weak Key-â…£s.1. Break ABC v3 with weak keysABC v3 is a synchronous stream cipher with two previous versions v1 and v2. Its key length is 128 bits, and it is one of the fastest algorithms among 34 candidates. In 2005, Berbain, Gilbert and Khazaei found that the size of LFSR is so short that ABC v1 could be broken by divide-and-conquer attack. The weakness of ABC v1 was eliminated by increasing the size of LFSR in ABC v2. However, at SAC 2006, Wu and Preneel found that there exists weak keys in ABC v2, which result in a key recovery attack on ABC v2. After twisting the key initialization process and eliminating Wu-Preneel weak keys, ABC v3 can resist all previous attacks.The cipher body of ABC family consists of three components: a LFSR (component A), a T-function (component B) and a 32×32 S-box (component C) constructed by knapsack function. The keystream byte is the Modular Addition result of the least 32-bit word of component A and the output of component C. The number of terms in the feedback polyonmial of LFSR is 3, which improve the performance, however incurs fast correlation attack. In order to mask the linearity of the LFSR, the designers employ several nonlinear operations such as T-function, S-box, and Modular Addition, etc. Especially, the S-box constructed by knapsack function enhances the difficulty to cryptanalyze ABC v3. In order to break ABC v3 with weak keys, we find the linear approximations of the non-linear Modular Addition first, and then employ it to find the weakness of the kernel component S-box, which leads to recovery of the LFSR internal state.(1) Prove the probability advantage of two linear approximationsFrom the Modular Addition of ABC v3, we explore one linear approximation of Modular Addition with two integers. We find a type of linear approximation with high probability, and derive its concrete value by classification and mathematical induction. The probability is as follows:where, y, c, x are n-bit integers, y = c + x (mod 2ⁿ), F(y, m) =(?),δ_i(y) denote the ith least significant bit of integer y, and 1≤m≤n. That is the first type of linear expression.There exists another linear expression which reflects the linearity among the carry bits in three Modular Addition equations. The correlation among equations makes the problem more complex so that Wu and Preneel found the probability advantage of the second linear expression by experiment, and don't present strict mathematical proof. We prove the probability by classification and mathematical induction, and presented a generalized version. One of the results is as follows:where, a_i,b_i,c_i are three n-bit integers, c_i,n=δ_n(a_i+b_i), 1≤i≤3, and n≥2. Two linear expressions with probability advantage reflect the linearity of the nonlinear operation Modular Addition. Taking advantage of the two linear expressions, we derive a large amount (?)f weak keys and retrieve all the ABC main keys successively. Because Modular Addition and XOR operations are widely used in the design of symmetric ciphers, we believe that these types of linear expressions with probability advantages not only can be used to analyze some other symmetric ciphers, but also are important factors in the design of secure symmetric ciphers.(2) Find new type of weak keysFirstly, We prove that there is almost no bias which can be utilized to apply a fast correlation attack on ABC v3, and the weak keys defined by Wu and Preneel are eliminated. Consequently, ABC v3 can resist against all the previous attacks. Then, the difficulty and emphasis is to find new type of weak keys. The core component of ABC v3 is a 32×32 S-box based on a high non-linear knapsack function. Theoretically, the knapsack problem is NP problem which is hard to solve by known theories. Moreover, because of the limitation of the memory and computation, it is hard to search directly for weak keys with higher probability bias. After deep investigations, we find a type of weak S-box with which the output of S-box can leak the linearity of LFSR in component A, and provide a fast searching algorithm to find such weak S-boxes. The core of the searching algorithm is to construct a non-linear transformation with specific characteristic, which reduces the search space. As a result, the size of search space decreases by about 14263 times. We define the keys result in weak S-boxes as new type of weak keys. By experiments, we show that the total number of weak keys is about 2^103.71 for ABC v3.(3) Distinguish and recover weak keys The first step is to distinguish weak keys. Utilizing linear expressions with probability advantages and the linearity property of LFSR, and approximating the bi-nomial distribution with the normal distribution, we establish a distinguisher to identify the weak keys of ABC v3, and conclude that the weak keys can be successfully identified. Since one weak key exists among 2^24.29 keys, the complexity is about 2^36.62 keystream outputs and 2^41.48 XOR operations. The second step is to recover weak keys. Firstly, the initial value of component A (LFSR) is recovered by exploiting the strong correlation between the LFSR and the keystream. Secondly, the internal state of component B can be recovered from the property of T-functions. Thirdly, by a divide-and-conquer attack, we obtain the internal state of component C step by step. The total complexity of recovery all the internal states (three components A, B, and C) of ABC v3 is about 2^36.05 keystream words and 2^50.56 XOR operations.To sum up, the number of new type of weak keys is up to 2^103.71 in ABC v3. Recovering the internal state under a weak key requires 2^36.05 keystream words and 2^50.56 operations. The attack can be applied to ABC v1 and v2 with the same complexities as that of ABC v3. However, the number of weak keys for ABC v1 and ABC v2 decreases to 2⁹⁷+2^95.19. It revealed that ABC v3 incurs more weak keys than that of ABC v1 and v2. Hence, ABC v3 is still insecure.3. Break TSC-4 with weak keysSince T-function is introduced into cryptology by Klimov and Shamir, numbers of stream ciphers based on T-function have appeared, such as Klimov-Shamir algorithms, TSC-1, TSC-2 and TSC-3, etc. However, all of them were broken. TSC-4 is a T-function based stream cipher with 80-bit key, designed by Moon et al., and enters the second eSTREAM evaluation phase. At Indocrypt 2006, Fischer, Meier and Berbain et al. found that there exists some non-randomness in the key initialization process of TSC-4. Because the bias can not be found in the keystream output, the non-randomness could not be applied to attack TSC-4.TSC-4 consists of three components: two symmetric T-function structures X and Y, and a filter non-linear function whose input is obtained from X and Y and output is the keystream. Because the T-function employs several non-linear logical operations, chosen control operation and S-box, etc, its avalanche and diffusion effect are very strong, which is difficult to construct mathematical model. We combine the differential attack and divide-and-conquer attack, take experiments as basement, explore mathematical model from experiment data, and conclude the characteristic of weak keys with which break TSC-4 finally.(1) Construct two special differential characteristics in the key initializationThe key initialization of TSC-4 proceed as: Key and IV is loaded into X and Y first, and then 8 rounds iteration are performed. Each iterative round consists of three steps: step 1 mixes the information of X and Y into an output byte, step 2 is to rotation shift X and Y by one line, and step 3 confuse the output byte obtained in the first step with X and Y. We observe that the interaction of X and Y is caused by step 1 and step 3. If the differential of Y is non-zero, and both the differential of X and the output byte in step 1 are zeroes, the non-zero differential of Y can not be diffused to X, i.e., the differential of X will always be zero. Consequently, we can cut off the connection between X and Y in this way. Based on that, we can construct two special differential characteristicsΩ_X andΩ_Y If the differential characteristicΩ_Y holds, then the differential characteristicΩ_X holds with probability 1. The following is to find in which caseΩ_Y occurs with high probability.(2) Find weak keysFirstly, select K and IV randomly and perform the key initialization process. IfΩ_Y holds, reserve K and IV and corresponding X and Y. Secondly, employχ² test to Y by each column, and put non-random distributions. Thirdly, find linear expression about X and Y with high probability advantage based on the obtained non-random distributions. Fourthly, according to the Key/IV loading process, get the linear expression about K and IV by substitution of linear expression about X and Y. Fifthly, summarize linear expressions, define E_k as weak keys space which results inΩ_Y occurring with high probability and E_IV as special IV space. Sixthly, randomly select K and IV from spaces E_K and E_IV respectively, perform the key initialization process over again, and calculate the occurrence probabilityΩ_Y Finally, we conclude that there are 2⁷² weak keys among 2⁸⁰ keys. If chosen IV pair falls into E_IV, the occurrence probability ofΩ_Y is about 2^-15.40 for wgak keys and about 2^-24.74 for strong keys.(3) Identify and recover weak keysAlthough two special differential characteristics in the state initialization are constructed and weak keys are defined, the internal states are unknown except for the keystream output bits. Consequently, we need to construct a distinguisher which transfers the differential bias of the internal states to the keystream output bits. By experiments, we obtain the distinguisher successfully. At last, we conclude that there are about 2⁷² weak keys among the total 2⁸⁰ keys, and to recover 8 bits of a weak key needs about 2^40.53 chosen IV pairs. After that, we can recover the other 72 key bits by an exhaustive attack.As a result, TSC-4 is insecure. We reveal that there exists other types of weak keys and other attacks, such as related key attack, etc.3. Find a differential characteristic in the key initialization process of CryptMT v3 with probability 1CryptMT v3 is a stream cipher submitted to eSTREAM Project, and enters the third evaluation phase with 128-bit key. Because of employing multiplication operation etc, no attack has been published until now. Consider the key initialization process of CryptMT v3 as a function generator, i.e., a function family F={f_K:{0,1}¹²⁸→{0,1}^m} indexed by a key K randomly chosen from {0,1}^k. By differential attack, we construct a distinguisher A^f_K, which allows to distinguish f_K from a random function with probability 1. The result indicates that for each key K, f_K is not a PRF, and maybe result in potential attacks on CryptMT v3.4. Break Grain v1 with weak Key-IVsGrain v1 is one of the seven portfolios, Grain vO is its previous version, and Grain-128 is its variant version. In 2005, Khazaei, Hassanzadeh and Kiaei presented a distinguishing attack on Grain v0. At FSE 2006, Berbain, Gilbert and Maximov broken Grain v0 by a key recovery attack. Based on the slide resynchronization attack, (?). K(?)k presented a related key attack on Grain v1. Then two research groups extended the attack and proposed related-key chosen IV attacks on Grain-v1 and Grain-128. All the attacks on Grain-v1 and Grain-128 are in the related-key settings. The algebraic attacks on two algorithms were proposed by Afzal and Masood, however, the total time complexity exceeds the exhaustive attack. The final eSTREAM evaluation report considers that Grain v1/128 is secure, but the key initialization should be modified.The cipher body of Grain family consists of three parts, a LFSR, a NFSR, and a nonlinear filter. For Grain v0/v1/128, the secret key is 80/80/128 bits, and the IV is specified to be 64/64/96 bits, respectively. Denote the size of key K as k bits, and the size of IV as / bits. There are 2^k+l different keystream sequences totally corresponding to all different (K,IV) pairs. It is necessary to guarantee that each sequence possesses perfect random characteristic among 2^k+l sequences for secure stream ciphers. We break Grain v1 with weak Key-IVs.(1) The existence of weak Key-IVsIt is obvious that if the initial states of the LFSR are all zeros after the initialization process, NFSR is the only active component of the cipher body. Consequently, if the (K,IV) pair results in the all zero LFSR state, we define the (K,IV) pair as a weak Key-IV. We present an algorithm to search for the weak Key-IVs, and an example is illustrated for each version. Suppose that the internal state with 2k bits of the NFSR and LFSR is uniformly distributed after the key initialization, there are 2^l weak Key-IVs among total 2^k+l Key-IVs for each Grain version.(2) Distinguish weak Key-IVsWe apply the second Walsh spectra to the nonlinear feedback function of NFSR, and obtain its best linear approximation. Utilizing the linear approximation lemma, we construct one distinguisher to distinguish the weak Key-IVs for each Grain version. We can distinguish a weak Key-IV from 2⁸⁰/2⁸⁰/2¹²⁸ Key-IVs with successful probability 99.977%, the data complexity is about 2^17.8/2^49.4/2^91.8 keystream bits, and the computational complexity is about 2^21.1/2^52.7/2¹¹⁰ XOR operations for Grain v0/ v1/128, respectively. (3) Recover weak Key-IVsThe internal state of Grain family consists of k bits from LFSR and NFSR, re-spectively. When the cipher generates keystream bits, LFSR works indepen-dently, NFSR is driven by its nonlinear feedback polynomial and the output of LFSR, and the keystream bits are generated by both LFSR and NFSR. Thus, the nonlinear equations could be obtained from the keystream bits and the internal state bits of LFSR and NFSR. For weak Key-IVs, utilizing the algebraic attack presented by Afzal and Masood, we conclude that the known weak Key-IVs of Grain v1 can be broken with 2^30.7 operations and 150 keystream bits, and the known weak Key-IVs of Grain-128 can be broken with 2^93.8 operations and 100 keystream bits. The result of Grain v0 is similar to that of Grain v1.As a result, to break a weak Key-IV of Grain v0/v1/128,2^17.8/2^49.4/2^91.8 keystream bits and 2^30.7/2^52.7/2¹¹⁰ XOR operations are required, respectively. Our results show that there exists a weakness in the key initialization process of Grain vl and Grain-128, and the key initialization process should be modified.