Cryptology ePrint Archive: Report 2021/1329

Trail Search with CRHS Equations

John Petter Indrøy and Håvard Raddum

Abstract: 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.

Category / Keywords: secret-key cryptography / differential cryptanalysis, linear cryptanalysis, CRHS equations

Date: received 1 Oct 2021, last revised 19 Nov 2021

Contact author: haavardr at simula no, johnpetter at simula no

Available format(s): PDF | BibTeX Citation

Version: 20211119:062324 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]