Font Size: a A A

On Cryptanalytic Methods Of NLFSR-Based Stream Ciphers

Posted on:2016-12-21Degree:DoctorType:Dissertation
Country:ChinaCandidate:L DingFull Text:PDF
GTID:1108330482479224Subject:Military cryptography
Abstract/Summary:PDF Full Text Request
The eSTREAM (ECRYPT Stream Cipher Project), launched at 2004, greatly promoted the development of design and analysis of stream ciphers. NLFSR (Non-Linear Feedback Shift Register), a new driven component, had been utilized in the design of stream ciphers. Design and analysis of NLFSR-based stream ciphers attracted so much attention all over the world, and became a hot spot of research on stream cipher. Some representative NLFSR-based stream ciphers, e.g., Grain, Trivium and MICKEY, had been three of the seven finalists in the final eSTREAM portfolio. It shows that the NLFSR-based stream ciphers provide a high security level, and then exploring effective attacks on them is quite difficult.As a whole, from the start of eSTREAM, very few works on the cryptanalytic methods of NLFSR-based stream ciphers had been published, and the progress of cryptanalysis of representative NLFSR-based stream ciphers had been slow, though so much attention had been paid to the NLFSR-based stream ciphers. The research on the cryptanalytic methods of NLFSR-based stream ciphers has become one of the most difficult and pressing work in the field of analysis of stream ciphers.This paper studies the cryptanalytic methods of NLFSR-based stream ciphers closely. With respect to the main key points of design of stream ciphers, i.e., the design of Boolean functions, the algorithm model, the initialization, the key size and key loading, this paper targets four powerful cryptanalytic methods, i.e., algebraic attack, guess-based composite attack, slide attack and Time-Memory-Data Trade-Off (TMDTO) attack. Cryptanalytic results of Grain, Trivium and MICKEY are provided. This paper takes the research on cryptanalytic methods as the main body, and takes the cryptanalytic results on the stream ciphers as the examples. A deep study on the resistance of NLFSR-based stream ciphers against these four attacks is given. The main innovative results are summarized as follows.Firstly, a new variant of algebraic attack and probabilistic algebraic attack based on conditional nonlinear approximation are proposed, aiming at the design of the Boolean functions in NLFSR-based stream ciphers.In this paper, a new cryptanalysis technique called dividing attack on stream ciphers is proposed. Based on guessing most of all key bits, the given stream cipher is divided into a number of different sub-ciphers, each of which supports a small key size. For each sub-cipher, the attacker is able to describe the keystream bits over the remaining key bits accurately, which makes the recovery of them to be easily done. This is the basic idea of dividing attack. We demonstrated the effectiveness of dividing attack by applying it to the full Trivium stream cipher. The results show that our attack is much better than all known attacks on Trivium, and is the first attack better than exhaustive key search on full Trivium. Furthermore, dividing attack is likely to be powerful on many NLFSR-based stream ciphers which seem to be secure against all the known attacks.This paper first shows some flaws in the probabilistic algebraic attack on Grain v1 by Pratish Datta et al. The idea of conditional nonlinear approximation is proposed in this paper, and utilized in the probabilistic algebraic attack on Grain-like stream ciphers, which improves the attack by Pratish Datta et al. The results show that the conditional nonlinear approximation is a powerful tool in the cryptanalysis of NLFSR-based stream ciphers.Secondly, two new guess-based composite attacks, i.e., the guess-affine attack based on the weak normality of the employed keystream output and the guess-and-check attack based on TMDTO, are proposed, aiming at the design of the algorithm model in NLFSR-based stream ciphers.The Grain vl stream cipher is one of the seven finalists in the final eSTREAM portfolio. Though many attacks have been published, no recovery attack better than exhaustive key search on full Grain vl in the single key setting has been found yet. This paper first shows some flaws in the attack on Grain vl by Mihaljevic et al. Unlike their attack we utilize the weak normality order of the employed keystream output function in Grain vl to mount new state recovery attacks on the cipher. These attacks have remarkable advantages in the offline time, online time and memory complexities, which are all better than exhaustive key search. The proposed attack primarily depends on the order of weak normality of the employed keystream output function. This shows that the weak normality order should be carefully considered when designing the keystream output functions of Grain-like stream ciphers.Combining with TMDTO attack, this paper proposes a new guess-based composite attack, named guess-and-check attack in this paper. The attack consists of two phases, the offline phase and online phase. In the offline phase, the attacker should construct a checking table, and make a preprocessing on the keystream. The new attack is applied to the simplified Grain-like and MICKEY-like stream ciphers, with time complexities better than the exhaustive key search. Unlike the algebraic attack, the complexities of guess-and-check attack are independent of the algebraic degree of NLFSR.Thirdly, slide attack based on slide property with hide information is proposed, aiming at the design of the initialization in NLFSR-based stream ciphers.This paper analyzes the slide property with hide information in NLFSR-based stream ciphers, and explores the hide equations behind the slide property. Utilizing the TMTO technology, the attack algorithm is proposed and its complexity is analyzed in detail. The attack solves the problem of recovering the hide information behind the slide property.The well-known stream cipher Grain-128 is an improved version of Grain-128 stream cipher with authentication. 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. In this paper, we give some observations on Grain-128a, and then propose a slide attack on Grain-128a based on these observations. Our attack can recover the 128-bit secret key of Grain-128a with complexities much better than exhaustive key search in the related key setting.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. As confirmed by the experimental results, our attack recovers all 80 bits of WG-8 in<3 min on a PC with 2.5-GHz Intel Pentium 4 processor. This is the first time that a weakness is presented for WG-8. 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 slide attack.Fourthly, a new TMDTO attack based on BSW sampling technique is proposed, aiming at the design of the key size in NLFSR-based stream ciphers. A new TMTO attack based on the structural weakness of MICKEY is proposed and better than exhaustive key search, aiming at the design of the key loading in MICKEY.By combining the time-memory-data tradeoff (TMDTO) attack independently proposed by Babbage and Golic (BG) with the BSW sampling technique, this paper explores to mount a new TMDTO attack on NLFSR-based stream ciphers. The new attack gives a wider variety of trade-offs, compared with original BG-TMDTO attack. It is efficient when multiple data is allowed for the attacker from the same key with different IVs, even though the internal state size is twice the key size. We apply the new attack to MICKEY and Grain stream ciphers, and improves the existing TMDTO attacks on them. Our attacks on Grain vl and Grain-128 stream ciphers are rather attractive in the respect that the online time, offline time and memory complexities are all better than an exhaustive key search, and the amount of key stream needed are completely valid.This paper point outs the existence of a divisibility property in the initialization of the MICKEY family of stream ciphers (including MICKEY 2.0 and MICKEY-1282.0), and show that it can be used to explore a new key recovery attack to improve exhaustive key search (currently the most efficient attack on both MICKEY 2.0 and MICKEY-1282.0). We prove that for the MICKEY family of stream ciphers, there certainly exists a key recovery attack in the single key setting with the time complexity better than exhaustive key search. For MICKEY 2.0 with 80-bit IV, the new attack improves the time complexity of exhaustive key search by a factor of 2. To the best of our knowledge, this is the first attack better than exhaustive key search on the MICKEY family of stream ciphers.The eSTREAM, which enriches the’data base’of the research on stream cipher, greatly promoted the development of design and analysis of stream ciphers. Security analysis of NLFSR-based stream ciphers becomes a hot and difficult spot of research on stream ciphers all over the world. The security analysis of NLFSR-based stream ciphers is beneficial to making a better understanding of cryptanalysis of NLFSR-based stream ciphers, and contributes to enrich the cryptanalytic theory of stream ciphers.
Keywords/Search Tags:Stream cipher, Cryptanalysis, Algebraic attack, Guess strategy, Slide attack, Time-Memory-Data Trade-Off(TMDTO)attack, Grain, Trivium, MICKEY, WG-8
PDF Full Text Request
Related items