Algebrraic Cryptanalysis of Feistel Structure Based Light Weight Block Ciphers

Abstract

Light weight block cipher is a new trend in cipher design that is aimed at providing a trade-off between security and efficiency for resource constrained special purpose applications like RFID-tags, sensor nodes and smart card. Consequently, various cryptanalytic techniques are also taken into account to gauge very carefully the security of these light-weight ciphers. Algebraic cryptanalysis has been extensively applied to break many real world stream ciphers; however, exploitation of its potential against block ciphers is a grey area of research. In algebraic methods of block ciphers cryptanalysis, linear and nonlinear components; separately cipher and key scheduling, are modeled into systems of algebraic equations. These are then combined to determine the complex system of equations that completely describe the entire cipher. Solution of such systems, where possible, gives the key or plaintext. In this thesis, basic concept behind algebraic technique, light weight block ciphers and their algebraic cryptanalysis has been discussed. Due presence of nonlinear component i.e. S-box, in cipher design, resistivity of block ciphers against algebraic attacks lies in the S-box. This research also describes a step by step methodology to model any S-box in to system of linearly independent Multivariate Quadratic (MQ) equations. Initially, Proof of Concept (PoC) on a simpler 3x3 S-box has been implemented. Then targeted feistel structure based light weight block ciphers have been analyzed with respect to their resistivity against algebraic attacks. A simple algebraic representation of 32 round LBlock in terms of 2628 variables, 8928 equations and 43,908 monomials, 33 rounds of SEA48,8 in terms of 3216 variables, 10,560 equations in 34,320 monomials and SEA96,8 in terms of 6432 variables, 21,120 equations and 68, 568 monomials have been given. Moreover, it has also been shown that XSL attack doesn’t pose any threat to either LBlock or SEA. In addition, feasibility about applicability of cube attack in combination with algebraic attack has also been undertaken. A software tools has also been developed using Maple/C-sharp that can give algebraic representation of any lower order S-box. Developed tool can be utilized in S-box design as well as in algebraic cryptanalysis of other block ciphers.