Research On Automatic Search For Differential Trails In ARX Ciphers

ARX is a common design in ciphers,using modular addition,rotation and exclusive-OR to implement non-linear,mixture and expansion.ARX is most used in block ciphers and hash functions,like TEA,XTEA,SPECK,MD5,SHA-1 and SM3.Unlike block ciphers with substitution boxes(S-boxes),e.g,DES,it's infeasible to find high-probability differential trail of ARX ciphers by counting plain and cipher pairs with current computing ability.Therefore,differential trail probability analysis is much more complex in ARX ciphers than that in S-boxes based ciphers,and automatic search is the main method in differential analysis of ARX ciphers so far.By researching existing algorithm of automatic search for differential trails in ARX ciphers,the thesis proposes the following methods to improve the automatic search algorithm:(1)Sorted partial differential distribution table(pDDT).Using pDDT sorted by probability can cut off branches in advance.(2)Depth first search(DFS).Using DFS to update probability threshold in time can reduce computation of temporary pDDT.(3)GPU paralleling computing.Using GPU parallelism to improve the performance of computation of temporary pDDT.The experiment shows these methods can optimize the search performance,especially the first two,which can eliminate lots of branches in advance and make a great improvement in the search time performance since search time increases exponentially with the rounds increasing.