|Authors||H. Raddum and P. Zajac|
|Title||MRHS solver based on linear algebra and exhaustive search|
|Publication Type||Journal Article|
|Year of Publication||2018|
|Journal||Journal of Mathematical Cryptology|
|Keywords||algebraic cryptanalysis, LowMC, MRHS|
We show how to build a binary matrix from the MRHS representation of a symmetric-key cipher. The matrix contains the cipher represented as an equation system and can be used to assess a cipher’s resistance against algebraic attacks. We give an algorithm for solving the system and compute its complexity. The complexity is normally close to exhaustive search on the variables representing the user-selected key. Finally, we show that for some variants of LowMC, the joined MRHS matrix representation can be used to speed up regular encryption in addition to exhaustive key search.