A Method to Bound the Number of Active S-Boxes for a Kind of AES-Like Structure

Abstract

Due to the strong security and high performance of the AES block cipher, many hash functions take AES-like structures as building blocks. To evaluate the security of these AES-like structures against differential cryptanalysis, giving the lower bounds on the number of active S-boxes in a differential trail, is an important perspective. However, the original ‘wide-trail strategy’ for AES becomes less effective to get tight bounds for these AES-like structures, because of the different state dimensions (⁠$\mathit{M}\mathbf{\times }{\mathit{M}}^{\mathbf{2}}$⁠, instead of $\mathit{M}\mathbf{\times }\mathit{M}$⁠) and different round functions from AES. In this paper, we focus on a kind of AES-like structure with state dimensions $\mathit{M}\mathbf{\times }{\mathit{M}}^{\mathbf{2}}$⁠, diffusion-optimal permutations and MixColumns transformations using MDS matrices. Inspired by the ‘wide-trail strategy’, we propose a theoretical method to count active S-boxes, by which we prove that there are at least $\mathit{r}{\mathit{B}}_{\mathit{d}}({\mathit{B}}_{\mathit{d}}\mathbf{-}\mathbf{1)}$ active S-boxes in any $\mathbf{2}\mathit{r}(\mathit{r}\mathbf{\ge }\mathbf{3)}$ rounds of such an AES-like structure, where ${\mathit{B}}_{\mathit{d}}$ is the differential branch number of the MixColumns transformation and equals to $\mathit{M}\mathbf{+}\mathbf{1}$⁠. What’s more, this lower bound can be achieved by some diffusion layers. As examples, we apply our method to the LANE hash function and 3D block cipher, optimal lower bounds are both got.