Welcome to the resource topic for 2022/019
Title:
Algebraic Meet-in-the-Middle Attack on LowMC
Authors: Fukang Liu, Santanu Sarkar, Gaoli Wang, Willi Meier, 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.
ePrint: https://eprint.iacr.org/2022/019
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .