AuthorsH. Raddum and P. Zajac
TitleMRHS solver based on linear algebra and exhaustive search
AfilliationCryptography
Project(s)Department of Cryptography
StatusPublished
Publication TypeJournal Article
Year of Publication2018
JournalJournal of Mathematical Cryptology
Volume12
Issue3
Pagination143-157
Date Published09/2018
PublisherDe Gruyter
ISSN1862-2976
Keywordsalgebraic cryptanalysis, LowMC, MRHS
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.

URLhttps://www.degruyter.com/view/j/jmc.2018.12.issue-3/jmc-2017-0005/jmc-2017-0005.xml?format=INT
DOI10.1515/jmc-2017-0005
Citation Key26351

Contact person