Algebraic Attack And Its Application On Some Lightweight Block Ciphers

Cryptography and cryptanalysis are two branches of cryptology. They have been mutually helping each other's development. Algebraic analysis has become one of research hot spots of cryptanalysis. The research of algebraic attack will benefit both cryptography and cryptanalysis.This thesis studies algebraic attack and its applications on some lightweight block ciphers. First we summarized the processes and methods of algebraic attack on block cipher. Algebraic attack consist two steps: building algebraic equations to describe the encryption and solving the algebraic equations to recover the key bits. Equations describing the encryption are extended from the algebraic description of S-Box. There are two methods of building algebraic description for S-Box. The expression form of the S-Box can be used as algebraic description. Using matrix method, we can build the other kind of algebraic description for the S-Box. By meet-in-middle method, we can reduce the intermediate variables without increasing the degree of these equations. There are several methods to solve the algebraic equations, including methods by Gr?bner bases, via SAT solvers and relinearization methods.By introducing differential technology, the efficiency of algebraic attack can be improved. In this thesis we present differential-S-Box. Using differential-S-Box, we can simulate the encryption process. Using simulate encryption, algebraic attack can be built for different scenes.PRINTCipher is a lightweight block cipher designed for IC-printing. It was presented in CHES 2010. We analyzed the S-Box in this cipher, and give the algebraic description for it. Using MiniSAT, we attacked the reduced round PRINTCipher. However full rounds PRINTCipher is immune to algebraic attack.Besides, this thesis studies algebraic attack of PRESENT cipher. We build equations of PRESENT by using meet-in-middle method. In the experiment, reduced round PRESENT is attacked by MiniSAT. We can recover keys of 4-round PRESENT in a minute. And it cost hours to recover keys of 6-round PRESENT. By introducing difference, the attack will be more effective. It can recover keys of 8-rounds PRESENT in reasonable time.