Paper 2022/135

Do NOT Misuse the Markov Cipher Assumption - Automatic Search for Differential and Impossible Differential Characteristics in ARX Ciphers

Zheng Xu, Yongqiang Li, Lin Jiao, Mingsheng Wang, and Willi Meier

Abstract

Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the Markov cipher assumption. Secondly, we propose an automatic search tool for differential characteristics with more precise probabilities in ARX ciphers. We find that some differential characteristics that used to be valid become impossible, and some probabilities that used to be underestimated increase. In applications, for CHAM-64/128 (one of the underlying block ciphers in COMET, one of 32 second-round candidates in NIST’s lightweight cryptography standardization process), we find that there is no valid $39$-round differential characteristic with a probability of $2^{-63}$ computed using previous methods, and we correct the probabilities to $2^{-64}$ and $2^{-64}$ instead of $2^{-65}$ and $2^{-65}$ computed using previous methods for two 39-round differential characteristics starting from the $1$-st round, respectively; however, if we search for differential characteristics starting from the $5$-th round, the two differential characteristics are invalid, which means that the round constants can affect the security of ARX ciphers against differential cryptanalysis; for Alzette with $c = \tt{0xb7e15162}$ (one of the S-boxes in SPARKLE, one of 10 finalists in NIST’s lightweight cryptography standardization process), we correct the probabilities to $0$ and $2^{-22}$ instead of $2^{-23}$ and $2^{-23}$ computed using previous methods for two 4-round differential characteristics, respectively; for XTEA, we correct the probabilities to $0$ and $2^{-49}$ instead of $2^{-58}$ and $2^{-56}$ computed using previous methods for two 10-round differential characteristics, respectively. Moreover, for Alzette with $c = \tt{0xb7e15162}$, XTEA, the $\tt{quarterround}$ function of Salsa20, and the round function of Chaskey, we find some invalid DCs that Leurent’s ARX Toolkit cannot detect. Thirdly, we propose a SAT-based automatic search tool for impossible differential characteristics in ARX ciphers. We find some distinguishers ignored by previous methods. In applications, for CHAM-64/128, we find five $20$-round and nineteen $19$-round impossible differential characteristics starting from the $3$-rd round for the first time. However, if we search for impossible differential characteristics starting from the $1$-st round, we cannot find any $20$-round impossible differential characteristic, which means that the round constants can affect the security of ARX ciphers against impossible differential cryptanalysis. Moreover, we find more impossible differential characteristics for 18-round, 16-round, 14-round, and 12-round CHAM-64/128, respectively. According to our results, the differential (resp. impossible differential) attack constructed by the previous methods of placing a DC (resp. an ID) anywhere in a block cipher may be invalid.