Research On The Meet-in-the-Middle And Impossible Differential Cryptanalytic Techniques And Applications

Block ciphers are cores of many cryptosystems,which are widely applied to political,diplomacy and commerce.Thus the security of block ciphers attracts many attentions.Meet-in-the-middle and impossible differential cryptanalysis are two important cryptanalytic methods,which are shown to be very efficient to many block ciphers.In this paper,we focus on these two cryptanalytic methods,and the main works are as follows.Research on the meet-in-the-middle cryptanalytic method:1.Feistel structure is widely applied in the designs of block ciphers.Thus the security of Feistel structure attracts many attentions.This paper studied the security of one kind Feistel structure against the meet-in-the-middle attack,which had been used in the designs of SIMON and Simeck block ciphers.For convenience,we call this Feistel structure as Feistel-2~*structure.Based on the feature of Feistel-2~*structure,we introduce the"differential function reduction"technique.Based on this technique,we can reduce the number of key bits used to compute the internal state of Feistel-2~*structure.Thus,it can reduce the complexity of the meet-in-the-middle attack on Feistel-2~*structure.Then,we gave two kinds of meet-in-the-middle attacks on Feistel-2~*structure.The first one is a attack with low data complexity,which requires only few chosen plaintexts.The second one consumes more data,but can break more rounds.Based on our results,we showed that a secure Feistel-2~*block cipher should iterate 4m+4 rounds at least,where m is the ratio of key size to block size.2.The construction of truncated differential is a key point in the truncated differential cryptanalysis.Based on the meet-in-the-middle technique,we studied the relation between the probability of the truncated differential of SP structure and its diffusion layer.A method to construct truncated differential of SP structure was proposed.Based on this method,we constructed the first 5-round truncated differential distinguishers of mCrypton and CRYPTON V1.0,respectively.Exploiting the 5-round truncated differential distinguishers,the key-bridging technique and time-and-memory trade-off technique;we presented the first 8 round attack on mCrypton-64,and improved the former best truncated differential attack on CRYPTON V1.0 by one round.Research on the impossible differential cryptanalytic method:3.SKINNY is a family of tweakable lightweight block cipher proposed in CRYPTO'16,which can be used to memory encryption and generation of short tags.This paper studied the security of the SKINNY family of block ciphers against the impossible differential attack.By analyzing the key schedule of SKINNY,some relations among the subkeys were gotten.Based on these relations,we can reduce the number of subkeys required to guess during the impossible differential attack on SKINNY.Furthermore,we introduced the“greedy matching strategy”.Combining this strategy with the early-abort technique,the time complexity of the online phase of impossible differential attack can be reduced.Based on these techniques,we improved the former differential attack on SKINNY by one round.When the ratio of key size to block size equals to 1,2 and 3,our attacks can break out 17,19 and 21 rounds of SKINNY,respectively.4.QARMA is a family of tweakable lightweight block cipher proposed in 2016,which has been used by the ARMv8 architecture to support a software protection feature.This paper studied the security of the QARMA family of block ciphers against the impossible differential attack.By studying the difference diffusion behavior of QARMA,we constructed the first6-round impossible differential of QARMA.Exploiting the 6-round impossible differential and the time-and-memory trade off technique,we presented 10-round impossible differential attack on QARMA.Furthermore,if allowed with more data,our attack can break out 11 rounds of QARMA,which is currently the best result with respect to the attacked rounds.Our result shows that the claim that 8-round QARMA can resist impossible differential attack made by the designer is invalid.5.Since the impossible differential attack is very efficient against many block ciphers,the security of block ciphers against impossible differential attracts many attentions.Feistel-SP structure is widely applied in the designs of block ciphers.If the matrix P of the Feistel-SP structure is a permutation matrix,then we call the Feistel-SP structure as the Feistel~*-SP structure.In this paper,the security of the Feistel~*-SP structure against the impossible differential cryptanalysis was studied.First,based on the characteristic matrixes of the Feistel~*-SP structure,we introduced a new method to compute the output difference of the Feistel~*-SP structure,which was called the characteristic matrix method.Then based on this method,we estimated the upper bound on the rounds that the longest impossible differential could cover for the Feistel~*-SP structure.It is shown that the upper bound is determined by the diffusion order of the characteristic matrixes.The small the diffusion order of the characteristic matrixes are,the better the diffusion capability of the Feistel-SP structure would achieve.Based on the links between impossible differential and zero correlation linear hull,we project our results to zero correlation linear hull.6.We showed that if the characteristic matrices of a generalized Feistel structure are primitive matrix,then the characteristic matrix method can also apply to this kind Feistel structures.For example,the CAST-256 generalized Feistel structure and the Type-II generalized Feistel structure.At last,we applied the characteristic matrix method to LBlock and TWINE block ciphers,since the round functions of LBlock and TWINE can be viewed as the Feistel~*-SP structure.We proved that,if the properties of S-boxes are not considered,then the number rounds of impossible differentials or zero correlation linear hulls of the above two ciphers will not exceed 14.