Algebraic Meet-in-the-Middle Attack on LowMC
Algebraic Meet-in-the-Middle Attack on LowMC
复制标题
DOI：
10.1007/978-3-031-22963-3_8
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Fukang Liu;Gaoli Wang;W. Meier;Santanu Sarkar;Takanori Isobe
中科院分区：
文献类型：
--
作者：
Fukang Liu;Gaoli Wang;W. Meier;Santanu Sarkar;Takanori Isobe
利用部分非线性层的特点，提出了一种新的分析LowMC安全性的方法--代数式中间相遇(MITM)攻击，在现有的基础上降低了简单差分枚举攻击的存储复杂度。此外，虽然在CRYTO 2021中已经提出了一种从LowMC的差分轨迹中获取完整密钥的高效代数技术，但其时间复杂度仍然是密钥大小的指数级。在这项工作中，我们展示了当轨迹中有足够多的活动S盒时，如何将其缩减为恒定时间。利用上述新技术，进一步改进了在CRYPTO 2021上发布的对LowMC和LowMC-M的攻击，并且可以第一次破坏一些LowMC实例。我们的结果似乎表明，部分非线性层仍然没有被很好地理解。
By exploiting the feature of partial nonlinear layers, we propose a new technique called algebraic meet-in-the-middle (MITM) attack to analyze the security of LowMC, which 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. 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.