### 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.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Differential cryptanalysisDifferential probabilityImpossible differentialARXSAT solver
Contact author(s)
xuzheng @ iie ac cn
History
Short URL
https://ia.cr/2022/135

CC BY

BibTeX

@misc{cryptoeprint:2022/135,
author = {Zheng Xu and Yongqiang Li and Lin Jiao and Mingsheng Wang and Willi Meier},
title = {Do NOT Misuse the Markov Cipher Assumption - Automatic Search for Differential and Impossible Differential Characteristics in ARX Ciphers},
howpublished = {Cryptology ePrint Archive, Paper 2022/135},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/135}},
url = {https://eprint.iacr.org/2022/135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.