Paper 2022/1088

Tighter trail bounds for Xoodoo

Abstract

Determining bounds on the differential probability of differential trails and the squared correlation contribution of linear trails forms an important part of the security evaluation of a permutation. For Xoodoo such bounds were proven with a dedicated tool (XooTools), that scans the space of all r-round trails with weight below a given threshold $T_r$. The search space grows exponentially with the value of $T_r$ and XooTools appeared to have reached its limit, requiring huge amounts of CPU to push the bounds a little further. The bottleneck was the phase called trail extension where short trails are extended to more rounds, especially in the backward direction. In this work, we present a number of techniques that allowed us to make extension much more efficient ant that allowed us to increase the bounds significantly. Notably, we prove that the minimum weight of any 4-round trail is 80, the minimum weight of any 6-round trail is at least 132 and the minimum weight of any 12-round trail is at least 264, both for differential and linear trails.