AuthorsJ. P. Indrøy, N. Costes and H. Raddum
EditorsD. O., J. M. J. Jacobson and O. C.
TitleBoolean Polynomials, BDDs and CRHS Equations – Connecting the Dots with CryptaPath
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2021
Conference NameSelected Areas in Cryptography
Date Published07/2021
Publisher Springer
Place PublishedCham
ISBN Number978-3-030-81651-3
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 constructions. 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