Algebraic Cryptanalysis of Stream Ciphers with Non-linear Update

Abstract

Stream ciphers are quite well known for providing security in comunication. Due to their efficient implementation they have received attention of many cipher designers in previous years. Many new designs have been proposed and extensively analyzed in the form of NESSIE and eSTREAM projects. In general a new proposed design has to ensure, at least, that it is resistant to the existing attacks. Algebraic attack is now quite a familiar threat for stream ciphers. Therefore, to make out the design components, that can strengthen a cipher, against algebraic cryptanalysis must also be of interest to stream cipher designers. Algebraic cryptanalysis, in its general form, aims at recovering the internal secret state bits of the registers of the cipher by solving non-linear algebraic equations. That is why it is considered, not to be applicable on stream ciphers, where registers are updated non-linearly. Since, in this case, degree of algebraic equations, which relate internal states with key-stream bits, increase with each clock. However, different designs with nonlinear update may offer disparate levels of resistance. In this thesis, we analyze some structures of stream ciphers with non-linear update and identify the level of resistance their design shows against the reocvery of secret internal states. Our objective is to analyze and compare the design of the key generating mechanism and not the cipher along with its initialization mechanism. Thus, we concentrate on the key generating part and compare the ciphers on the basis that how many of their internal state bits can be recovered by solving nonlinear algebraic equations, using guess and determine approach. Caused by a rise in the degree of equations with each clock, some of the internal state bits have to be guessed to recover the remaining. Our analysis reveals, that due to some thoughtful guessing, more internal state bits can be recovered which are not possible otherwise. However, some structures are resistent to give secret state bits by solving algebraic equations, even after guessing large number of bits. Aim of this thesis is to identify such structures. Ciphers considered for this work are A5/1, A5/2, Trivium, Grain and Mickey. Significance of this work also lies in the fact that we have analyzed those ciphers which have been selected for the final portfolio of completed eSTREAM project. Based on our analysis, we also propose some modifications in the design of Grain-v1 to strengthen it against intial state recovery attack, without any increase in the secret state bits. Some modifications in the design of Trivium are also suggested therefore, the same structure can be used with larger key bit space.