Paper 2016/811

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

Ling Sun, Wei Wang, and Meiqin Wang

Abstract

Division property is a general integral property introduced by Todo at EUROCRYPT 2015. Recently, at ASIACRYPT 2016, Xiang et al. applied the Mixed Integer Linear Programming (MILP) method to search bit-based division property, and handled the complexity which restricted the application of bit-based division property proposed by Todo and Morii at FSE 2016. However, their MILP-aided search was only applied to some lightweight block ciphers whose linear layers were limited to bit-permutations, and the feasibility of MILP-aided bit-based division property for ciphers with non-bit-permutation linear layers was an open problem. This paper comes out with the affirmative answer. First, we transform the complicated linear layers to their primitive representations, which only involves Copy and XOR operations. Then, the original Copy and XOR models are respectively generalized to deal with more output branches and input elements, and these generalized models are adopted to depict the primitive representations. Accordingly, the MILP-aided bit-based division property can be applied to much more primitives with complicated linear layers. As an illustration, we first evaluate the bit-based division propertyies of some word-oriented block ciphers including Midori64, LED, Joltik-BC, and AES. For Midori64, we obtain a 7-round integral distinguisher, which achieves one more round than the previous results. At the same time, the data requirements of some existing distinguishers are also reduced. We decrease the number of required chosen plaintexts of 4-round and 5-round integral distinguishers for LED and Joltik-BC by half. As to AES, our searching experiments show that integral distinguishers, which are based on the bit-based division property, covering more than four rounds probably do not exist. Then, the bit-based division properties of some bit-oriented block ciphers, such as Serpent and Noekeon, are considered. The data complexities of their distinguishers for short rounds are improved. Moreover, we evaluate the bit-based division properties of the internal permutations involved in some hash functions, e.g., SPONGENT and PHOTON. An 18-round zero-sum distinguisher for SPONGENT-88 is proposed, which achieves four more rounds than the previous ones. We also provide 20-round and 21-round zero-sum distinguishers for SPONGENT-128 and SPONGENT-160, respectively. For most PHOTON permutations $P_{t}$ with 4-bit cell, the data requirements for the 4-round distinguishers are reduced by half. Besides, the length of $P_{256}$'s distinguisher is extended by one round. Furthermore, for $P_{288}$ using 8-bit S-boxes, we improve the data complexities of their integral distinguishers significantly.

Note: A new version of this paper is updated.