International Association for Cryptologic Research

International Association
for Cryptologic Research


Tighter Trail Bounds for Xoodoo

Silvia Mella , Radboud University, Nijmegen, The Netherlands
Joan Daemen , Radboud University, Nijmegen, The Netherlands
Gilles Van Assche , STMicroelectronics, Diegem, Belgium
DOI: 10.46586/tosc.v2023.i4.187-214
Search ePrint
Search Google
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 using the trail core tree search technique, with a dedicated tool (XooTools) that scans the space of all r-round trails with weight below a given threshold Tr. The search space grows exponentially with the value of Tr and XooTools appeared to have reached its limit, requiring huge amounts of CPU time 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 and as such 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. As a byproduct we found families of trails that have predictable weight once extended to more rounds and use them to compute upper bounds for the minimum weight of trails for arbitrary numbers of rounds.
  title={Tighter Trail Bounds for Xoodoo},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={023 No. 4},
  author={Silvia Mella and Joan Daemen and Gilles Van Assche},