Meet-in-the-Middle Attack on Primitives with Binary Matrix Linear Layer

Qingliang Hou; Kuntong Li; Guoyan Zhang; Yanzhao Shen; Qidi You; Xiaoyang Dong

Paper 2025/082

Meet-in-the-Middle Attack on Primitives with Binary Matrix Linear Layer

Qingliang Hou, School of Cyber Science and Technology, Shandong University, Qingdao, China

Kuntong Li, School of Cyber Science and Technology, Shandong University, Qingdao, China

Guoyan Zhang, School of Cyber Science and Technology, Shandong University, Qingdao, China, Shandong Institute of Blockchain, Jinan, China

Yanzhao Shen, Shandong Institute of Blockchain, Jinan, China

Qidi You, State Key Laboratory of Space-Ground Integrated Information Technology

Xiaoyang Dong, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China

Abstract

Meet-in-the-middle (MitM) is a powerful approach for the cryptanalysis of symmetric primitives. In recent years, MitM has led to many improved records about key recovery, preimage and collision attacks with the help of automated tools. However, most of the previous work target $\texttt{AES}$-like hashing where the linear layer is an MDS matrix. And we observe that their automatic model for MDS matrix is not suitable for primitives using a binary matrix as their linear layer. In this paper, we propose the $\texttt{n-XOR}$ model to describe the $\texttt{XOR}$ operation with an arbitrary number of inputs. And it can be applied to primitives with a binary matrix of arbitrary size. Then, we propose a check model to eliminate the possible inaccuracies caused by $\texttt{n-XOR}$. But the check model is limited by the input size (not greater than 4). Combined with the two new models, we find a MitM key recovery attack on 11-round $\texttt{Midori64}$. When the whitening keys are excluded, a MitM key recovery attack can be mounted on the 12-round $\texttt{Midori64}$. Compared with the previous best work, both of the above results have distinct advantages in terms of reducing memory and data complexity. At last, we apply the $\texttt{n-XOR}$ model to the hashing modes of primitives with large size binary matrix. The preimage attack on weakened $\texttt{camellia}-{\tt MMO}$ (without $FL/FL^{-1}$ and whitening layers) and $\texttt{Aria}-{\tt DM}$ are both improved by 1 round.

Note: This is a full version of the original publication.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Major revision. CT-RSA2025
Keywords: Meet-in-the-Middle Binary Matrix Key Recovery Preimage Midori64 Camellia Aria
Contact author(s): qinglianghou @ mail sdu edu cn
likuntong @ mail sdu edu cn
guoyanzhang @ sdu edu cn
shenyanzhao @ sdibc cn
xiaoyangdong @ tsinghua edu cn
History: 2025-01-21: revised; 2025-01-19: received; See all versions
Short URL: https://ia.cr/2025/082
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2025/082,
      author = {Qingliang Hou and Kuntong Li and Guoyan Zhang and Yanzhao Shen and Qidi You and Xiaoyang Dong},
      title = {Meet-in-the-Middle Attack on Primitives with Binary Matrix Linear Layer},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/082},
      year = {2025},
      url = {https://eprint.iacr.org/2025/082}
}