AuthorsJ. P. Indrøy, N. Costes and H. Raddum
TitleBoolean Polynomials, BDDs and CRHS Equations – Connecting the Dots with CryptaPath
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2020
Conference NameSelected Areas in Cryptography
Publisher Springer
Keywordsalgebraic cryptanalysis, binary decision diagram, block cipher, equation system, Open Source, tool

When new symmetric-key ciphers and hash functions are proposed they are expected to document resilience against a number of known attacks. Good, easy to use tools may help designers in this process and give improved cryptanalysis. In this paper we introduce CryptaPath, a tool for doing algebraic cryptanalysis which utilizes Compressed Right- Hand Side (CRHS) equations to attack SPN ciphers and sponge construc- tions. It requires no previous knowledge of CRHS equations to be used, only a reference implementation of a primitive.
The connections between CRHS equations, binary decision diagrams and Boolean polynomials have not been described earlier in literature. A comprehensive treatment of these relationships is made before we explain how CryptaPath works. We then describe the process of solving CRHS equation systems while introducing a new operation, dropping variables.

Citation Key27709

Contact person