Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- differential cryptanalysislinear cryptanalysisCRHS equations
- Contact author(s)
-
haavardr @ simula no
johnpetter @ simula no - History
- 2021-11-19: revised
- 2021-10-05: received
- See all versions
- Short URL
- https://ia.cr/2021/1329
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1329,
author = {John Petter Indrøy and Håvard Raddum},
title = {Trail Search with {CRHS} Equations},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1329},
year = {2021},
url = {https://eprint.iacr.org/2021/1329}
}
