Making sure that our primitives are not susceptible to differential or linear cryptanalysis has been a constant target for us. In this scope, differential and linear trails specify how differences or linear masks propagate through the rounds, so we want to ensure that the only trails that exist are those that are too costly to exploit. Concretely, we are looking for lower bounds on the weight of trails, for a given number of rounds. The higher the weight, the greater the data and/or computation complexity of attacks based on them, so simply put, if no trail of low weight exist, then we are safe.

Bounds on trails do not give guarantees of security, but they can help determine the resistance against some specific attacks. For instance, in the Farfalle construction (used by Xoofff and Kravatte), the expected data complexity to generate internal collisions is directly linked to bounds on the weight of differential trails, see Section 6.3.2 of [Daemen et al., The design of Xoodoo and Xoofff, ToSC 2018].

Bounds on trails do not give guarantees of security as differential and linear attacks are broader than just exploiting trails. For instance, a differential over several rounds (i.e., specifying only the input and output differences) can span many differential trails (i.e., take many different internal differences); this effect is called clustering. Nevertheless, the design strategy of Xoodoo, similar to that of Keccak, is unaligned, and this helps reduce clustering. We studied this and other effects in our recent paper [Bordes et al., Thinking Outside the Superbox, CRYPTO 2021].

Proving lower bounds on trails in unaligned primitives requires the computer-aided exploration of all possible trails. The publication of Xoodoo came with our initial bounds, and we further improved them and reported them in the documentation of Xoodyak. Recently, we revived this effort and further extended our complete search for all 3-round trails up to weight 52 (instead of 50), allowing us to prove that a 6-round trail has weight at least 108 (instead of 104). This is the case for both differential and linear trails.

The completeness of the search for all 3-round trails is now confirmed up to weight 50 thanks to an independent search effort based on SAT solvers, XoodooSat, implemented by Huina Li and Weidong Qiu of Shanghai Jiao Tong University. Actually, they reported to us that two trails of weight 48 were missing, and this was caused by a bug in our program XooTools. After fixing it, we could confirm that XooTools and XoodooSat had produced exactly the same set of trails, independently!

To conclude, we summarize our current trail bounds in Xoodoo in the following table.