Algebraic Properties And Applications On Three Non-linear Feedback Models

A number of stream ciphers based on nonlinear feedback register appear in the assess progress of European eSTREAM and CARSAR projects. Their novel structure and design idea wildly draws the attention of people and the research of these ciphers becomes the hot topic of recent years. Nonlinear feedback model, as the abstract representation of a group cipher based on nonlinear feedback register, reflects the similarities and characteristics of the certain group. So it is meaningful and of guidance to study the model for the design and analysis of these ciphers.This paper takes Trivium-like nonlinear feedback model, KeeLoq-like nonlinear feedback model and KATAN-like nonlinear feedback model as research objects. Some algebraic properties of several typical ciphers of these models are studied and some new attack results are given. Then this paper attempts to give some design advices to the ciphers of the models. The main achievements are as below:1. Algebraic properties and applications of Trivium-like nonlinear feedback modelThis paper gives the input information contained by expression of Trivium-like model and analysises the diffusion and completeness of internal states and output bits of model. We propose a universal algorithm of completeness of stream cipher based on nonlinear feed back shift register, which can get the lower bound of round which crypto algorithms need to reach completeness more accurately. We apply this algorithm to Trivium-like cipher and study the completeness of these ciphers. Based on the results, we conduct a difference distinguisher on reduced version of Trivium with 398 rounds with a distinguishing advantage of 0.99998, which only needs 32 chosen IVs and we also conduct a real time divide-and-conquer attack on full round of Trivium-B with the compute complexity O(227) and the success rate of the attack is 0.994 when we get 107 bits output key stream.This paper gives the specific expression of Trivium-like model of reduced rounds, based on which we present a modified linearization technique. This technique can decrease the number of nonlinear terms and increase the linear bias effectively in the linearization phase when the expression is known. Then we apply this method in the linear cryptanalysis of the reduced Trivium and its modified version Trivium-Ml and Trivium-M2 and improve the previous results.2. Algebraic properties and applications of KeeLoq-like nonlinear feedback modelThis paper gives cube properties of KeeLoq-like model. Firstly, we attack KeeLoq of 64 rounds with cube attack. Fifteen linear equations of 15 key bits are found, all key bits can be recovered with a computational complexity of O(222.1). Then, combining meet-in-the-middle technique, we increase the attack round to 96 by using the linear equations.In order to enhance the cipher’s ability to resist cube attack and slide attack, we propose a modified KeeLoq. The new cipher adds nonlinear complement in subkey generation function. As a result, the output key stream bits are proved of a period sequence and the period is divided by no remainder. This property can prevent the modified KeeLoq from slide attacks. In addition, as the way that key bits combined with internal states is nonlinear, the modified KeeLoq can resist cube attack and is more secure.3. Algebraic properties and applications of KATAN-like nonlinear feedback modelIn this paper, we apply TASCA(Tolerant Algebraic Side-Channel Attack) to KATAN family implemented in microcontrollers with buses of 8-bit under Hamming Weight Leakage Model. The results show that this implement cannot resist this kind of attack.Moreover, we give the input information contained by expression of KATAN-like model and analysises the diffusion of internal states and output bits of model. Based on the results, how to choose the key bits when conducting meet-in-the-middle attack on KATAN32 is optimized, so the attack round increases to 179 rounds from 175 rounds with the computational complexity of O(278.85)(the previous is O(279.3)). The rounds of attack on KATAN48 and KATAN64 are improved to 137 and 120 respectively(the previous are 130 and 112 respectively) in the same way, with a lower computational complexity.