Automatic Search of Impossible Differentials and Zero-Correlation Linear Hulls for ARX Ciphers  

作　　者：Kai Zhang Jie Guan Bin Hu 

机构地区：[1]Zhengzhou Information Science and Technology Institute, Zhengzhou 450000, China

出　　处：《China Communications》2018年第2期54-66,共13页中国通信（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant No. 61572516, 61402523, 61202491, 61272041 and 61272488

摘　　要：In lightweight cryptographic primitives, round functions with only simple operations XOR, modular addition and rotation are widely used nowadays. This kind of ciphers is called ARX ciphers. For ARX ciphers, impossible differential cryptanalysis and zero-correlation linear cryptanalysis are among the most powerful attacks, and the key problems for these two attacks are discovering more and longer impossible differentials(IDs) and zero-correlation linear hulls(ZCLHs). However, finding new IDs and ZCLHs for ARX ciphers has been a manual work for a long time, which has been an obstacle in improving these two attacks. This paper proposes an automatic search method to improve the efficiency of finding new IDs and ZCLHs for ARX ciphers. In order to prove the efficiency of this new tool, we take HIGHT, LEA, SPECK three typical ARX algorithms as examples to explore their longer and new impossible differentials and zero-correlation linear hulls. To the best of our knowledge, this is the first application of automatic search method for ARX ciphers on finding new IDs and ZCLHs. For HIGHT, we find more 17 round IDs and multiple 17 round ZCLHs. This is the first discovery of 17 round ZCLHs for HIGHT. For LEA, we find extra four 10 round IDs and several 9 round ZCLHs. In the specification of LEA, the designers just identified three 10 round IDs and one 7round ZCLH. For SPECK, we find thousands of 6 round IDs and forty-four 6 round ZCLHs. Neither IDs nor ZCLHs of SPECK has been proposed before. The successful application of our new tool shows great potential in improving the impossible differential cryptanalysis and zero-correlation linear cryptanalysis on ARX ciphers..In lightweight cryptographic primi- tives, round functions with only simple opera- tions XOR, modular addition and rotation are widely used nowadays. This kind of ciphers is called ARX ciphers. For ARX ciphers, impos- sible differential cryptanalysis and zero-cor- relation linear cryptanalysis are among the most powerful attacks, and the key problems for these two attacks are discovering more and longer impossible differentials （IDs） and ze- ro-correlation linear hulls （ZCLHs）. However, finding new IDs and ZCLHs for ARX ciphers has been a manual work for a long time, which has been an obstacle in improving these two attacks. This paper proposes an automatic search method to improve the efficiency of finding new IDs and ZCLHs for ARX ciphers. In order to prove the efficiency of this new tool, we take HIGHT, LEA, SPECK three typ- ical ARX algorithms as examples to explore their longer and new impossible differentials and zero-correlation linear hulls. To the best of our knowledge, this is the first application of automatic search method for ARX ciphers on finding new IDs and ZCLHs. For HIGHT, we find more 17 round IDs and multiple 17 round ZCLHs. This is the first discovery of 17 round ZCLHs for HIGHT. For LEA, we find extra four 10 round IDs and several 9 round ZCL- Hs. In the specification of LEA, the designers just identified three 10 round IDs and one 7round ZCLH. For SPECK, we find thousands of 6 round IDs and forty-four 6 round ZCLHs. Neither IDs nor ZCLHs of SPECK has been proposed before. The successful application of our new tool shows great potential in improv- ing the impossible differential cryptanalysis and zero-correlation linear cryptanalysis on ARX ciphers..

关 键 词：automatic search tool impossibledifferential cryptanalysis zero-correlation lin-ear cryptanalysis ARX ciphers modes opera-tion 

分 类 号：TN918.1[电子电信—通信与信息系统]