Research On Impossible Differential Cryptanalysis And Algebraic Cryptanalysis Of Some Block Ciphers

Block cipher is one of the most important components in cryptography, which iswidely applied in network communications, electronic commerce, smart cards and so on.As a basic module of data encryption, the block cipher was used to design stream ciphers,pseudorandom number generators, message authentication codes and hash functions. Up tonow, researches on block ciphers mainly include designs, cryptanalysis, modes ofoperations and evaluations. Among them, cryptanalysis of block ciphers is a hotspot incryptology. There are three cryptanalytic methods in the main, i.e., differentialcryptanalysis, linear cryptanalysis and algebraic attack. Meanwihle, many efforts have beenmade to generalize and extend these approaches in order to derive more effectivecryptanalytic methods such as impossible differential cryptanalysis, truncated differentialcryptanalysis, higher order differential cryptanalysis, multidimensional linear cryptanalysis,non-linear cryptanalysis, differential-linear cryptanalysis and so on. Such work has not onlypushed forward the analysis theory of block cipher dramatically, but also resulted inconsiderable improvement of the design theory of block ciphers.In this dissertation, we mainly study the security of several well-known block ciphersand some new block ciphers against impossible differential cryptanalysis or algebraicattack. Our results may be helpful in the security evaluation of these ciphers. Moreover, wealso analyze the security of MiFare Classic system from the aspect of the legitimate readerand study the security of some variants of Crypto1against known attacks. Thecontributions of this dissertation are listed as follows:（1） LBlock is a lightweight block cipher with32rounds, which can be implementedefficiently not only in hardware environment but also in software platforms. By exploitingthe structure of LBlock and the redundancy in its key schedule, we propose an impossibledifferential attack on21-round LBlock based on a14-round impossible differential. Ourattack requires2^62.5chosen plaintext,2.^72.221-round encryptions and2^57.5bits ofmemory, while the previous best results in single key setting were integral attack andimpossible differential attack on20-round LBlock. （2） Camellia is a128bits block cipher, which was jointly developed by NTT and Mitsubishi in2000. In2002, it was selected as one of the CRYPTREC e-government recommended ciphers. In2003, it was recommended in NESSIE block cipher portfolio. In2005, it was adopted as an international standard by ISO/IEC. Camellia adopts Feistel structure with the key-dependent layers FL/FL-1inserted every6rounds. The goals for such a design are to provide non-regularity across rounds and to thwart future unknown attacks. In this dissertation, we analyze the security of various versions of Camellia against impossible differentia cryptanalysis from two aspects. First, we propose some7-round impossible differentials with one key-dependent layer, yet the previously longest impossible differential with one key-dependent layer is6rounds. Based on them, we attack11-round Camellia-192,11-round Camellia-256（from the first round to the eleventh round） and12-round Camellia-256, all of which contain the whitening layer and the key-dependent layer. Second, we further improve these results above and construct a set of differentials including at least one8-round impossible differential with two keyed layers, while the length of the longest known impossible differential of Camellia without the keyed layers is8rounds. Consequently, we show the key-dependent transformations inserted in Camellia cannot resist impossible differential attack efficiently. Based on this set of differentials, we propose a new cryptanalytic strategy to attack11-round Camellia-128,12-round Camellia-192,13-round Camellia-256,13-round Camelia-192without the whiten layer and14-round Camemlia-256without the whiten layer. To the best of our knowledge, our results are better than previous ones.（3） We successfully mount an impossible differential attack on7-round AES-128with low data complexity. Specifically, we construct some2-round impossible differentials. Based on them, we present impossible differential cryptanalysis of7-round AES-128with280chosen plaintexts,2126.57-round encryptions and269bits of memory. Compared with the best known result on impossible differential cryptanalysis of7-round AES-128, the data complexity of our attack is reduced by a factor of2-26.2.（4） Four-Cell was proposed by Choy et al., which adopts generalized Feistel-nonlinear feedback shift register. Its round function operates on two different fields GF（2） and GF（28）, which makes algebraic attack on Four-Cell difficult. In this dissertation, we generalize Four-Cell to derive a new block cipher E-Four-Cell by a vector conjugate transformation. The new block cipher E-Four-Cell operates in a field GF（28） and can be regarded as Four-Cell with a restricted message space and key space, thus enable algebraic attack on Four-Cell easy. （5） The MiFare Classic smart card is a logic encryption card with memory, which waswidely used in the transport system, the campus card system, the access control system andso on. In this dissertation, we first give the legitimate-reader-only attack on MiFare Classic,where the adversary only communicates with a legitimate reader. In a nested authenticationprotocol, we collect on the communication between the legitimate reader and a simulator inorder to recover the key of the second and subsequent sectors within negligible time, whilewe need estimate the time information between two consecutive authentications previously.Following this result, it is possible for the attackers to simulate or forge a legal card toauthenticate with a legitimate reader successfully. To avoid this weakness, the reader mustverify some information on the legal card at the beginning and it requires to be protected insome sense. Second, we study the security of some variants of Crypto1against knownattacks. Our results show that some variants whose inputs of the non-linear function areevenly selected from LFSR are still insecure.