Paper 2022/1088

Tighter trail bounds for Xoodoo

Joan Daemen, Radboud University Nijmegen
Silvia Mella, Radboud University Nijmegen
Gilles Van Assche, STMicroelectronics (Belgium)

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.

Available format(s)
Attacks and cryptanalysis
Publication info
lightweight cryptography permutation-based cryptography differential cryptanalysis linear cryptanalysis trail bounds
Contact author(s)
joan daemen @ ru nl
silvia mella @ ru nl
gilles-iacr @ noekeon org
2022-08-25: approved
2022-08-22: received
See all versions
Short URL
No rights reserved


      author = {Joan Daemen and Silvia Mella and Gilles Van Assche},
      title = {Tighter trail bounds for Xoodoo},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1088},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.