Algebraic Attacks On Symmetric Ciphers And The Study Of Algorithms For Solving Systems Of Multivariate Equations

Recently the algebraic attacks on symmetric key ciphers,which are some of the newest and most efficient forms of cryptanalytic attacks,have received more and more attention from the cryptological community.Differing from the previous classical "statistical" attacks,the attacks which use the algebraic approaches to cryptanalysis on a cipher is called by a general name,algebraic attacks.The principle of algebraic attacks is to set up a system of multivariate polynomial equations describing internal stages of encryption on any cipher with the input(key) bits as unknowns and the output bits,and try to resume the keys by solving this system in case it is low degree,overdefined,or sparse.So,the computational hardness of solving large overdefined systems of sparse and low degree multivariate equations is a necessary condition for the security of many modern symmetric cryptographic schemes.The public research increasingly focus on finding the new and fast efficient algorithm for solving systems of large multivariate equations.A tiny amount of data needed by the attackers is maybe the most absorbing feature of algebraic cryptanalysis,and sometimes one single or two known plaintexts are enough. This unprecedented quantity of algebraic attacks has simply no equivalent in any known cryptographic attack.It is precisely the reason why algebraic attacks are potentially very devastating,however immature and inefficient they are today.Another advantage of algebraic attacks is that they are new methods for cryptanalysis and still can be improved a lot.There are both theoretical significance and practical worthiness in the research of algebraic attacks.Historically the basic idea of the algebraic attacks goes back on several so called multivariate public key schemes and block ciphers such as Rijndael and Serpent.The attacks reduce the cryptanalysis of key recovery to solving a system of low degree multivariate quadratic equations(MQ problem).Even if algebraic attacks have not yet been tested on really examples,the existence of overdefined and sparse systems of quadratic equations of S-box is an important threat for Rijndael and Serpent.Since XL algorithm is proposed as an efficient technique for solving systems of low degree multivariate equations, algebraic attacks on LFSR-based stream ciphers have gained much attention,as a development of earlier ideas of higher order correlation attacks.Instead of considering outputs as functions of inputs,one should rather study algebraic relations between the input and output bits.It is shown that most LFSR-based stream ciphers are(potentially) vulnerable to algebraic attacks.In recent years there are new productions for algebraic attacks.For example,both 6 rounds of DES(using only one single known plaintext) and full rounds of KeeLoq can be broken by algebraic attacks converting MQ problem into SAT problem.In this paper we analyze the theoretical and practical aspects of algebraic attacks on LFSR-based stream ciphers and block ciphers,such as Toyocrypt,LILI-128,E0,Sf'mks, Rijndael,Serpent,DES,KeeLoq,and so on.We also investigate the efficient algorithms for solving systems of large multivariate equations,such as the classical Buchberger's algorithm for constructing Gr(o|¨)bner bases,XL algorithm and its derivative,and converting MQ problem into SAT problem.Studing the third algorithm can bring along algebraic attacks because it is simpler and more efficient than the first two algorithms,and it needs much little known plaintexts.We can apply this algorithm to efficiently break 6 rounds of DES and full rounds of KeeLoq.We study methods for efficiently converting systems of low-degree sparse multivariate equations into a conjunctive normal form satisfiability (CNF-SAT) problem.By using the low gate count non-standard representation of DES, requiring only one single known plaintext,and fixing 20 key variables,we write a system of 3076 sparse quadratic equations with 2900 variables for full 6 rounds of DES.We convert this system into SAT problem with 4203 variables,and 16880 clauses of total length 51514,then resume other 36 key bits with SAT-solvers,MiniSAT 2.0.In the last we briefly introduce the notion of Algebraic Immunity,the new design criteria for cipher components.We indicate the notion of algebraic immunity which defined with Annihilator cannot guarantee security of all ciphers to all algebraic attacks.We should study algebraic immunity in a broader perspective:the existence of some "simple" algebraic relations(I/O relations) that relate input and output bits of the non-linear components(S-boxes and Boolean functions alike) in the ciphers.From this we derive new design criteria for cipher components resisting algebraic attacks.