Research On Cryptanalysis Of ESTREAM Candidates

Stream cipher is an important branch of cryptology, and it has many attractive features such as high rates for encrypting and decrypting, easy for hardware implemen-tations, and without or having only several limited fault broadcast. Therefore, stream cipher is widely adopted in secure communications. Stream cipher is promoted further by the launch of European eSTREAM project. This dissertation investigates the techniques for cryptanalysis of stream ciphers, with emphasis on DECIMv2and Trivium. The author obtains main results as follows:(1) For the bit-search generator whose modified version ABSG is the important non-linear component of DECIMv2, a fast probabilistic key recovery attack based on multiple segments of keystream bites is presented using the idea of Martin Hell’s attack on the self-shrinking generator. Compared with the best known attack, the attack complexity can be significantly reduced from O(L3205L) to O(L32043L) where L is the length of the linear feedback shift register. If L is96, the attack complexity can be reduced to O(L32039L) with O(NL) of keystream bits, where N is the number of attacks. The experimental results show that:the complexity of this algorithm can be significantly degraded as the number of attacks increases; The longer the length of the key is, the more efficient our attack is.(2) For the Bit-Search Generators (BSG) with a low weight feedback polynomial, a fast key recovery algorithm is presented using the ideas of the guess-and-determine attack. A candidate differential sequence is recovered firstly from the intercepted keystream sequence based on the differential construction of the BSG sequence. Then the feedback polynomial is used to check the candidate differential sequence, which will reduce the number of the linear equation systems of L dimensions thus to significantly reduce the complexity of the algorithm. Theoretical analysis and simulation experiment results show that, when the weight of the feedback polynomial is less than10, the complexity of the attack is noticeably better than that of the existing methods.(3) For the simplified version2-round Trivium of Trivium, by finding more linear ap-proximations, a linear cryptanalysis of2-round Trivium is made utilizing multiple approximations. Compared with current single linear cryptanalysis, this method allows for a reduction in the amount of data required for a successful attack. That is to say, if n linear approximations can be found, this method can supply the same success rate with1/n of the data amount required by a simple linear cryptanalysis. (4) We propose a novel Correlation Power Analysis (CPA) attack on the hardware-oriented stream cipher Trivium, one of the finally chosen ciphers by the eSTREAM project. Based on the hamming distance model, the proposed attack exploits the resynchronization phase of Trivium. By choosing proper initial value vectors, the algorithmic noise of the device is completely eliminated. Furthermore, a novel con-cept of modified correlation coefficients is introduced, which can be used to describe the relation between the hypothetical power consumption values and the measured power consumption values. Through the calculation of modified correlation coeffi-cients, the effect of the electronic noise is significantly decreased and values of the hypotheses can be discriminated uniquely by the highest modified correlation coef-ficient. According to the recovered hypotheses, many equations on the secret key bits can be obtained, which will be sequentially solved to extract the secret key of Trivium. Compared with Fischer’s DPA attack on Trivium, the proposed algorithm is more efficient and robust. Finally, a simulation attack is mounted to confirm the efficiency of the algorithm.(5) The security of the candidate DECIM"2of eSTREAM project is studied with cor-relation power analysis. Based on the characteristics of its software implementation and hardware implementation, the security flaws which can be used in correlation power analysis are found. Through the introduction of modified correlation coef-ficients, we propose a correlation power analysis attack separately on the software and hardware implementation of DECIMv2.(6) We present a practical power analysis attack on linear feedback shift registers (LFSR) based stream ciphers. Based on Information Theory, the problem of power analysis is first converted into that of decoding over a3-ary symmetric channel. By setting two thresholds, the algorithm can significantly eliminate the effect of noise. Compared with Burman’s attack, the proposed attack algorithm is much more prac-tical as algorithmic noise and electronic noise are taken into account. Simulation results show that when the signal to noise ratio (SNR) is higher than-6.5dB, the algorithm can always be practically performed and effective.