Welcome to the resource topic for 2022/135
Title:
Do NOT Misuse the Markov Cipher Assumption - Automatic Search for Differential and Impossible Differential Characteristics in ARX Ciphers
Authors: Zheng Xu, Yongqiang Li, Lin Jiao, Mingsheng Wang, 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.
ePrint: https://eprint.iacr.org/2022/135
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .