2
$\begingroup$

I'm reading and implementing this tutorial, the author explains everything pretty clearly, the only thing I'm missing is how he decides which trail to use (pg. 12). I understand that one should prefer trails with the least amount of active S-Box and maximize the bias of the trail (in fact, finding the optimal trail seems to be the most important step when trying to apply linear cryptanalysis to a symmetric encryption algorithm).

It seems to me like some sort of dynamic programming problem, but I wonder if there is a general algorithm to solve the problem of finding the optimal trail (or at least, a series of candidate trails).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

People use Matsui's "Best Path Search Algorithm" which is indeed a dynamic programming approach. The resource costs hard to anticipate and so branch and bound variations are employed in practice.

A skeletal outline can be found on slides 14-17 of Matsui's retrospective talk on linear cryptanalysis at Asicrypt 2018.

A more formal description and some variants can be found in Ji, Zhang and Ding's 2019 paper "Improving Matsui’s Search Algorithm for the Best Differential/Linear Trails and its Applications for DES, DESL and GIFT"

Improve this answer
$\endgroup$
1
$\begingroup$

Matsui's method is the classical one, but nowadays the trend is towards MILP/SAT/SMT-based search. The correctness of the trail and its link with the transition probability is encoded into the system and is then optimized to minimize the total probability (for SAT/SMT binary search can be used, for MILP the optimization is native).

Some examples (most of the research is for differential attacks though, but it typically translated to linear attacks):

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I thinks this answer needs some links to those... $\endgroup$
    – kelalaka
    Feb 27, 2022 at 12:23
  • 1
    $\begingroup$ SAT=satisfiability, MILP = mixed integer linear programming, SMT? Please don't use undefined acryonyms that are not so common and reduce an answer's usefullness $\endgroup$
    – kodlu
    Feb 28, 2022 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.