Paper 2022/1088

Tighter trail bounds for Xoodoo

Joan Daemen, Radboud University Nijmegen
Silvia Mella, Radboud University Nijmegen
Gilles Van Assche, STMicroelectronics (Belgium)
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
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
History
2022-08-25: approved
2022-08-22: received
See all versions
Short URL
https://ia.cr/2022/1088
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1088,
      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{https://eprint.iacr.org/2022/1088}},
      url = {https://eprint.iacr.org/2022/1088}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.