基于SAT方法进一步加速差分特征的搜索

Further accelerating the search of differential characteristics based on the SAT method

回顾了孙等使用Matsui边界条件加速差分特征搜索的方法,为了进一步提高搜索效率,改进了Matsui边界条件以及利用Matsui边界条件加速差分特征自动化搜索的方法,并提出了一种改进的方法来搜索分组密码的最优差分特征。研究了线程数和询问条件的加速效果并提出了选择线程数以及询问条件的策略。使用STP和CryptoMiniSat分别搜索概率为2^(-24)、2^(-25)、2^(-26)的8轮SPECK96差分特征以及概率为2^(-39)的11轮HIGHT差分特征,并比较了在不同线程数和询问条件下求解SAT/SMT问题的耗时。研究发现线程数对搜索差分特征的耗时影响较大,而询问条件对搜索差分特征的耗时影响较小,从而提出了一种如何选择线程数和询问条件的策略。根据所提策略,使用改进的边界条件和方法搜索HIGHT的11轮最优差分特征,并首次获得了HIGHT的11轮最优差分特征的紧致概率,即2^(-45)。现有的11轮HIGHT最优差分特征概率的最紧致边界是P_(Opt)^(11)≥2^(-45)。这就意味着,利用现有11轮HIGHT最优差分特征概率的最紧致边界无法给出11轮HIGHT抗差分分析安全性的精确评估。因此,所提策略的结果是目前已知的最优结果。

Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics was reviewed.Matsui’s boundary conditions and Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics were improved for better search efficiency.Then an improved method to search for the optimal differential characteristics in block ciphers was proposed.Besides,the accelerating effects of the number of threads and the query condition were investigated,and a strategy for choosing the number of threads and the query condition were proposed.STP and CryptoMiniSat were used to search for 8-round SPECK96 differential characteristics with probabilities of 2^(-24),2^(-25),2^(-26)and 11-round HIGHT differential characteristics with a probability of 2^(-39),then the time-consuming of solving SAT/SMT problems under different number of threads and query conditions were compared.It was found that the number of threads has a great effect on the time consumption of searching for differential characteristics,while the query condition may have little effect on the time consumption of searching for differential characteristics.Then,a strategy on how to select the number of threads and the query condition was proposed.Furthermore,it was found that STP can affect the overall efficiency of the search.According to the proposed strategy,the 11-round optimal differential characteristics of HIGHT were searched by using the improved bounding conditions and improved method.A tight bound for the probability of the 11-round optimal differential characteristics of HIGHT was obtained for the first time,i.e.2^(-45).To the best of our knowledge,the existing tightest bound of the optimal 11-round HIGHT is P_(Opt)^(11)≥2^(-45).This means that using the existing tightest bound of the optimal 11-round HIGHT cannot give an accurate evaluation of the security of 11-round HIGHT against differential cryptanalysis.Therefore,the result is the best-known result.