Paper 2022/019

Algebraic Meet-in-the-Middle Attack on LowMC

Fukang Liu, Santanu Sarkar, Gaoli Wang, Willi Meier, and Takanori Isobe

Abstract

We propose a conceptually intuitive technique called algebraic meet-in-the-middle (MITM) attack in this paper. Unlike common MITM attacks where some intermediate state values are stored, several sets of linear equations will be stored in the algebraic MITM attack. Moreover, at the matching phase, it is necessary to first perform some linear transformations on the to-be-matched intermediate state value and only partial state bit information is used for the match. Once a match is found, the corresponding linear equation system is retrieved and solved to recover the full necessary information. This new technique fits very well with LowMC, a popular and important design using partial nonlinear layers. Based on it, we can reduce the memory complexity of the simple difference enumeration attack over the state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. Specifically, the guess-and-determine strategy is no more adopted at the key-recovery phase. Instead, we recover the full key by directly solving an overdefined system of quadratic equations. With the above new techniques, the attacks on LowMC and LowMC-M published at CRYPTO 2021 are further improved and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.

Note: Fix some typos.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
LowMCLowMC-Malgebraic attacklinearizationkey recoverymeet-in-the-middle
Contact author(s)
liufukangs @ gmail com
takanori isobe @ ai u-hyogo ac jp
glwang @ sei ecnu edu cn
willimeier48 @ gmail com
santanu @ iitm ac in
History
2022-02-14: last of 5 revisions
2022-01-08: received
See all versions
Short URL
https://ia.cr/2022/019
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/019,
      author = {Fukang Liu and Santanu Sarkar and Gaoli Wang and Willi Meier and Takanori Isobe},
      title = {Algebraic Meet-in-the-Middle Attack on LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2022/019},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/019}},
      url = {https://eprint.iacr.org/2022/019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.