Maximums of the Additive Differential Probability of Exclusive-Or

Abstract

At FSE 2004, Lipmaa et al. studied the additive differential probability adp^⊕(α,β → γ) of exclusive-or where differences α,β,γ ∈ Fⁿ₂ are expressed using addition modulo 2ⁿ. This probability is used in the analysis of symmetric-key primitives that combine XOR and modular addition, such as the increasingly popular Addition-Rotation-XOR (ARX) constructions. The focus of this paper is on maximal differentials, which are helpful when constructing differential trails. We provide the missing proof for Theorem 3 of the FSE 2004 paper, which states that max_α,_βadp^⊕(α,β → γ) = adp^⊕(0,γ → γ) for all γ. Furthermore, we prove that there always exist either two or eight distinct pairs α,β such that adp^⊕( α,β → γ) = adp^⊕(0,γ → γ), and we obtain recurrence formulas for calculating adp^⊕. To gain insight into the range of possible differential probabilities, we also study other properties such as the minimum value of adp^⊕(0,γ → γ), and we find all γ that satisfy this minimum value.