Paper 2016/811

MILP-Aided Bit-Based Division Property for Primitives with Non-Bit-Permutation Linear Layers

Ling Sun and Wei Wang and Meiqin Wang

Abstract

At ASIACRYPT 2016, Xiang et al. applied MILP method to search integral distinguisher based on division property. This method handled the huge time and memory complexities which had constituted the main restriction of the bit-based division property proposed by Todo and Morri, and showed its strength through finding some longer integral distinguishers for various primitives. Although MILP-aided bit-based division property has given many interesting results for some ciphers, the linear layers of these cipher are simple bit-permutations. Thus, the feasibility of MILP method applying to ciphers with linear layers which are not bit-permutations was left as a future work. In this paper, we handle this problem. Following this way, MILP-aided bit-based division property can operate on more primitives. As an illustration, we apply MILP-aided bit-based division property to find integral distinguishers for AES, LED, Joltik-BC, PHOTON, Serpent, Noekeon, SM4, and SPONGENT-88. We can not find any integral distinguisher whose length is longer than four rounds for AES. But for LED and Joltik-BC, which are AES-like block ciphers, we obtain 6-round integral distinguishers. For PHOTON permutations, which are also AES-like permutations, we obtain some better integral distinguishers comparing with those provided in its design paper. Based on these observations, the security of these AES-like block ciphers may need to be reconsidered and directly copying AES-like security proofs for some attacks seems to be less reasonable. We also find 7-round integral distinguishers for Serpent and Noekeon, which attain 3.5 more rounds than the previous distinguishers found by Z'aba et al. at FSE 2008. For SM4, we find a 12-round integral distinguisher, which attains four more rounds than the previous distinguisher found by Liu et al. at ACISP 2007. A 16-round higher-order integral distinguisher for SPONGENT-88 is proposed and this newly found distinguisher attains two more rounds than the previously known distinguishers.