Title: Finding differential trails on ChaCha by means of state functions

Authors: Emanuele Bellini; Juan Grados; Rusydi H. Makarim; Carlo Sanna

Addresses: Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE ' Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE ' Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE ' GNSAGA of INdAM and of CrypTO, The Group of Cryptography and Number Theory of Politecnico di Torino, Politecnico di Torino, Torino, Italy

Abstract: We provide fast algorithms to compute the exact additive and XOR differential probabilities of ChaCha20 half quarter-round H and, under an independence assumption, an approximation of the differential probabilities of the full quarter-round. We give experimental evidence of the correctness of our approximation, and show that the independence assumption holds better for the XOR differential probability than the additive differential probability. We then propose an efficient greedy strategy to maximise differential characteristics for the full quarter-round, and use it to determine explicit differential trails for the ChaCha permutation. We also provide an MILP model to search for differential trails in ChaCha and compare its performance and effectiveness with our method. We believe these results might bring new insights in the differential cryptanalysis of ChaCha20 and of similar ARX ciphers.

Keywords: ChaCha20; differential cryptanalysis; additive differential probability; XOR differential probability; state functions.

DOI: 10.1504/IJACT.2024.138416

International Journal of Applied Cryptography, 2024 Vol.4 No.3/4, pp.156 - 175

Accepted: 08 Mar 2023
Published online: 03 May 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article