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
-
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} }