Security Analysis Of Block Ciphers And Stream Ciphers

Today is an Internet age.Different from the previous periods,people in today share a different lifestyle.We can do most thing using the network without going out of home.For example,shopping on Taobao,paying via Alipay and transfering by E-bank and so on.Life becomes easier and faster.However,every coin has two sides.It brings a big problem for the property safety and individual privacy with the development of network.Now,cryptography is an important technology to protect us.It much likes a firewall,and is a cornerstone of all activities on the network.Generally,symmetric ciphers are most used to encrypt data through the Internet,such as stream ciphers and block ciphers.So,it is very necessary to study and analyze the safety of current widely used block ciphers and stream ciphers.In this thesis,we first propose new statistical integral distinguisher(with multi-structure)model and apply them on ciphers.Secondly,based on MILP method,we consider the differential property and linear property of S-box into the search of impossible differentials and zero-correlation linear approximations for the first time,and propose a general automatic search method for impossible differentials and zero-correlation linear approximations of ARX ciphers.At last,we utilize impossible differential cryptanalysis to propose a analytic result on Lizard cipher under related-key setting.The detail results are as follows.Construct a new statistical integral distinguisher model and use this model to break full-round Skipjack's variant,improve the best attack on CAST-256 cipher and the best integral attack on IDEA.Integral attack is one of the most powerful cryptanalytic tools that has been widely used in the security analysis of block ciphers.Integral distinguishers are based on bal-anced properties holding with probability one,where one fixes a part of plaintext bits and takes all possible values for the other plaintext bits such that a specific part of the corresponding ciphertext gets balanced,i.e.,each possible partial value for the ciphertext occurs exactly the same times,to distinguish target cipher and random permutation.To obtain a distinguisher covering more rounds,an attacker will normally increase the data complexity by iterating through more plaintexts with a given structure under the strict limitation of the full codebook.The data complexity restrains the applications of integral cryptanalysis on many ciphers.In this thesis,in order to reduce the data complexity,we use the hypergeometric distribution and multinomial distribution to build different distributions for tar-get cipher and random permutation so as to distinguish them.Thus we construct statistical integral distinguisher model.This enables us to achieve significantly lower data complexity with our statistical integral distinguisher as compared to those of traditional integral distinguishers.With this model,we can propose the improved attacks on Skipjack's variant,CAST-256 cipher and IDEA.Skipjack is the first block cipher designed by NS A.This cipher is weak against impossible differential attack.In order to enhance the ability against truncated differential attacks including impossible differential attack,Knudsen et al.pro-posed Skipjack's variant Skipjack-BABABABA.In this thesis,we successfully attack the full-round Skipjack's variant Skipjack-BAB ABABA for the first time.CAST-256 is a block cipher designed by Adams at SAC'97.It is one of the AES candidate block ciphers.From its establishment,many attacks have been proposed,such as differential attack,linear attack,boomerang attack,zero-correlation linear attack and so on.In this thesis,we exploit the statistical integral distinguisher to attack the CAST-256 block cipher.As a result,we manage to mount a key recovery attack on 29-round CAST-256 with 296.8 chosen plaintexts,2219.4 encryptions and 273 bytes of memory.By trade-off between the time com-plexity and data complexity,the attack can be achieved by 283-9 chosen plaintexts,2244.4 encryptions and 266 bytes of memory.As far as wt know,these are the best attacks on CAST-256 in the single-key model without weak-key assumption so far.IDEA was designed by Lai and Massey in 1991 and is widely used in several security applications,such as IPSec and PGP.In this thesis,we exploit the statis-tical integral distinguisher to attack the IDEA block cipher.We find an integral distinguisher of IDEA block cipher,which is the longest integral distinguisher known to now.By taking advantage of this distinguisher,we achieve a key re-covery attack on 4.5-rolnd IDEA with 258.5 known plaintexts,2120.9 encryptions and 246.6 bytes of memory respectively.It is the best integral attack according to the number of rounds.Construct a statistical integral distinguisher with multi-structure model,and use this model to propose the best secret-key integral dis-tinguisher on AES and the best known-key distinguishers on AES(-like)ciphers.Statistical integral model has one limitation that we only consider one integral property on the output.However,in some settings,there are several integral properties at the same time on the output.In some other settings,the integral distinguisher needs many structures of data simultaneously.For the for-mer,we will waste some properties on the output,and for the latter,the original statistical integral distinguisher cannot handle it.In order to extend the statis-tical integral model to satisfy these settings,we construct a new statistical inte-gral distinguisher with multi-structure model.With this model,we improve the secret-key integral distinguisher on 5-round AES and propose the best known-key distinguishers on AES(-like)ciphers.Advanced Encryption Standard(AES),published by NIST,is widely used in data encryption algorithms,hash functions,authentication encryption schemes and so on.Studying distinguishing attacks on(reduced round)AES can help designers and cryptanalysts to evaluate the security of target ciphers.With this new model,we propose a secret-key distinguisher on 5-round AES with secret S-box under chosen-ciphertext mode.Its data,time and memory complexities are 2114 32 chosen ciphertexts,2110 encryptions and 233.32 blocks.This is the best integral distinguisher on AES with secret S-box under secret-key setting so far.Then we present improved known-key distinguishers on 8-round and full 10-round AES-128 with reduced complexities based on Gilbert's work at ASIACRYPT'14.These distinguishers are the best ones according to the time complexity.In addition,the wide trail strategy adopted by AES is widely used to design hash functions,such as the ISO standard hash function Whirlpool,the well-known lightweight hash function PHOTON,one of the five final SHA-3 candidate propos-als Gr(?)stl and so on.The compression functions of these ciphers are all designed based on AES-like block ciphers.The security of such hash function directly de-pends on the security of its internal permutations,i.e.that the security of AES-like ciphers under the known-key setting.Similar to the known-key distinguishers on AES,we can apply the statistical integral distinguisher with multi-structure model into the known-key distinguishers on AES-like ciphers and put forward the best known-key distinguishers for the permutations used in Whirlpool,Gr(?)stl and PHOTON,respectively.New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations Based on MILP Method.Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography.There are several automatic tools to search such trails for ciphers with S-boxes.These tools focus on the properties of linear layers,and idealize the underlying S-boxes.In reality,such S-box never exists.Hence,some of the possible differential trails under the idea.l world become impossible in reality,possibly resulting in impossible differential trails for more rounds.In this paper,we firstly take the differential and linear properties of non-linear components such as S-box into consideration and propose a new automatic tool to search impossible differential trails for ciphers with S-box.We then generalize the tool to modulo addition,and apply it to ARX ciphers.To demonstrate the usefulness of the tool,we apply it to HIGHT,SHACAL-2,LEA,LBlock,Salsa20 and Chaskey.As a result,it improves the best existing results of HIGHT,SHACAL-2,LEA and LBlock,and finds the first result on permutations of Salsa20 and Chaskey.Security Analysis of Lizard under Related-Key Setting.Lizard is yet another attempt of lightweight stream cipher designed for beyond-birthday security by Hamann et al.in IACR ToSC 2016.It takes as input a 120-bit key and a 64-bit initial value to form an internal state of 121 bits,and outputs up to 218 key-stream bits per Key-? pair.The security claims are 80 bits against key-recovery attacks and 60 bits security against distinguishing attacks.Based on the idea of collision findings by Banik et al.,we first extend one more step in the single key setting to propose one attack on 227 steps which is the best one in this setting.Then we propose the key recovery attack on 233 steps in the related-key setting,leaving Lizard a security margin of only 23 out of the total 256 steps.This improvement comes from an observation that,when the key difference could be chosen,the difference propagation of some bits could be extended for more steps with probability 1.However,the introduction of key difference also brings problem of uncertain differences of the internal state due to truncation,we overcome the problem by a technique named "slide-collision".It is also observed that,once a pair of internal collision of Lizard is found,264 more pairs of collisions can be generated without any additional query or computation,and this generally applies to the underlying FP(1)-mode used in the Lizard design.This observation also leads to selective forgery or output prediction:when one Key-IV pair of the collision is queried,the output of the other pair is known to be identical without any additional query.