Finding differential trails on ChaCha by means of state functions

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.