Paper 2018/764

Generating Graphs Packed with Paths

Mathias Hall-Andersen and Philip S. Vejre


When designing a new symmetric-key primitive, the designer must show resistance to known attacks. Perhaps most prominent amongst these are linear and differential cryptanalysis. However, it is notoriously difficult to accurately demonstrate e.g. a block cipher's resistance to these attacks, and thus most designers resort to deriving bounds on the linear correlations and differential probabilities of their design. On the other side of the spectrum, the cryptanalyst is interested in accurately assessing the strength of a linear or differential attack. While several tools have been developed to search for optimal linear and differential trails, e.g. MILP and SAT based methods, only few approaches specifically try to find as many trails of a single approximation or differential as possible. This can result in an overestimate of a cipher's resistance to linear and differential attacks, as was for example the case for PRESENT. In this work, we present a new algorithm for linear and differential trail search. The algorithm represents the problem of estimating approximations and differentials as the problem of finding many long paths through a multistage graph. We demonstrate that this approach allows us to find a very large number of good trails for each approximation or differential. Moreover, we show how the algorithm can be used to efficiently estimate the key dependent correlation distribution of a linear approximation, facilitating advanced linear attacks. We apply the algorithm to 17 different ciphers, and present new and improved results on several of these.

Note: Typos

Available format(s)
Publication info
Published by the IACR in FSE 2019
Linear cryptanalysisDifferential cryptanalysisLinear ApproximationsDifferentialsTrail searchCorrelation distributionsGraph theory
Contact author(s)
psve @ dtu dk
2018-08-27: last of 2 revisions
2018-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mathias Hall-Andersen and Philip S.  Vejre},
      title = {Generating Graphs Packed with Paths},
      howpublished = {Cryptology ePrint Archive, Paper 2018/764},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.