Paper 2018/111

MRHS Solver Based on Linear Algebra and Exhaustive Search

Håvard Raddum and Pavol Zajac

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Algebraic cryptanalysisMRHSLowMC
Contact author(s)
pavol zajac @ stuba sk
History
2018-01-30: received
Short URL
https://ia.cr/2018/111
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/111,
      author = {Håvard Raddum and Pavol Zajac},
      title = {MRHS Solver Based on Linear Algebra and Exhaustive Search},
      howpublished = {Cryptology ePrint Archive, Paper 2018/111},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/111}},
      url = {https://eprint.iacr.org/2018/111}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.