搜索最优差分和线性迹的高效方法:应用于NOEKEON和Serpent算法OA

The ability to resist differential cryptanalysis and linear cryptanalysis serves as two core metrics for evaluating the security of symmetric-key primitives.A variety of automated search tools are available for searching the best differential and linear trails for primitives.Nevertheless,these tools often exhibit inefficiency or lack generality when applied to primitives with linear layers that incorporate XOR operations.To address this problem,this study proposes an efficient and general search tool specifically designed to deal with such primitives.The Matsui's algorithm based on search patterns is enhanced by employing a memorized iterative search strategy,which significantly reduces redundant computations by effectively leveraging previous search results.The entire search process is divided into two phases:the extension of search patterns phase and the search for two-round search patterns phase.In the extension of search patterns phase,the pruning process is accelerated by leveraging the property of the linear layers of ciphers and introducing stability mask technique.In the search for two-round search patterns phase,the narrowest point technique is employed to reduce the initial search space,further enhancing the efficiency of the algorithm by integrating difference patterns and linear mask patterns.Applying the improved tool to two SPN primitives NOEKEON and Serpent,their tightest security bounds against differential and linear cryptanalysis are provided.For NOEKEON,the best differential trails up to 9 rounds and the best linear trails up to 16(full)rounds are obtained.In particular,for the first time,an 8-round best differential trail with a probability of 2-126 suitable for differential attack is identified.For Serpent,the best differential trails up to 5 rounds and the best linear trails up to 9 rounds are obtained.It is proved for the first time that the upper bound of the maximum differential probability for 10-round Serpent is 2-129,and the upper bound of the maximum linear correlation for 12-round Serpent is 2-68.