Meet-in-the-Middle Attack on Primitives with Binary Matrix Linear Layer
摘要
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 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 n-XOR model to describe the 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 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 Midori64. When the whitening keys are excluded, a MitM key recovery attack can be mounted on the 12-round 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 n-XOR model to the hashing modes of primitives with large size binary matrix. The preimage attack on weakened Camellia-MMO (without \(FL/FL^{-1}\) and whitening layers) and Aria-DM are both improved by 1 round.