Paper 2021/1329

Trail Search with CRHS Equations

John Petter Indrøy and Håvard Raddum


Evaluating a block cipher’s strength against differential or linear cryptanalysis can be a difficult task. Several approaches for finding the best differential or linear trails in a cipher have been proposed, such as using mixed integer linear programming or SAT solvers. Recently a different approach was suggested, modelling the problem as a staged, acyclic graph and exploiting the large number of paths the graph contains. This paper follows up on the graph-based approach and models the prob- lem via compressed right-hand side equations. The graph we build contains paths which represent differential or linear trails in a cipher with few active S-boxes. Our method incorporates control over the memory usage, and the time complexity scales linearly with the number of rounds of the cipher being analysed. The proposed method is made available as a tool, and using it we are able to find differential trails for the Klein and Prince ciphers with higher probabilities than previously published.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
differential cryptanalysislinear cryptanalysisCRHS equations
Contact author(s)
haavardr @ simula no
johnpetter @ simula no
2021-11-19: revised
2021-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {John Petter Indrøy and Håvard Raddum},
      title = {Trail Search with CRHS Equations},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1329},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.