International Association
for Cryptologic Research

This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.

FRIET is a duplex-based authenticated encryption scheme proposed at EUROCRYPT 2020. It follows a novel design approach for built-in countermeasures against fault attacks. By a judicious choice of components, the designers propose the permutation FRIET-PC that can be used to build an authenticated encryption cipher denoted as FRIET-AE. And FRIET-AE provides a 128-bit security claim for integrity and confidentiality. In this paper, we research the propagation of pairs of differences and liner masks through the round function of FRIET-PC. For the full-round FRIET-PC, we can construct a differential distinguisher whose probability is 1 and a linear distinguisher whose absolute value of correlation is 1. Moreover, we use the differential distinguisher with probability 1 to construct a set consisting of valid tags and ciphertexts which are not created by legal users. This breaks FRIET-AE’s security claim for integrity and confidentiality. As far as we know, this is the first practical attack that threatens the security of FRIET-AE.

Division property proposed by Todo at EUROCRYPT 2015 is a generalized integral property. Then, conventional bit-based division property (CBDP) and bitbased division property using three subsets (BDPT) were proposed by Todo and Morii at FSE 2016. At ASIACRYPT 2016, Xiang et al. extended Mixed Integer Linear Programming (MILP) method to search integral distinguishers based on CBDP. And at ASIACRYPT 2019, Wang et al. proposed an MILP-aided method of searching integral distinguishers based on BDPT. Although BDPT is powerful in searching integral distinguishers, the accuracy is not perfect.For block cipher SPECK32, as the block size is only 32 bits, we can experimentally observe the behaviors of all the plaintexts under a fixed key. By testing 210 random secret keys, we experimentally find a better integral distinguisher of 6-round SPECK32 with 30 active bits. But this experimental integral distinguisher cannot be proved by existing methods. So there still exists a gap between the proved distinguisher and the experimental one.To fill the gap, we explore secret keys in searching integral distinguishers based on BDPT. We put forward a situation where “Xor with The Secret Key” operation can be bypassed. Based on the new BDPT propagation rule, an improved automatic algorithm of searching integral distinguishers is proposed. For SPECK32, our improved algorithm can find the 6-round integral distinguisher with 230 chosen plaintexts. The gap between the proved distinguisher and the experimental one is filled. Moreover, we apply this improved method to search the integral distinguishers of SPECK, KATAN/KTANTAN, SIMON, SIMECK, SIMON(102), PRESENT and RECTANGLE block ciphers. The integral distinguishers found by our improved method are better than or consistent with the previous longest distinguishers.

Division property is a generalized integral property proposed by Todo at EUROCRYPT 2015, and then conventional bit-based division property (CBDP) and bit-based division property using three subsets (BDPT) were proposed by Todo and Morii at FSE 2016. At the very beginning, the two kinds of bit-based division properties once couldn’t be applied to ciphers with large block size just because of the huge time and memory complexity. At ASIACRYPT 2016, Xiang et al. extended Mixed Integer Linear Programming (MILP) method to search integral distinguishers based on CBDP. BDPT can find more accurate integral distinguishers than CBDP, but it couldn’t be modeled efficiently.This paper focuses on the feasibility of searching integral distinguishers based on BDPT. We propose the pruning techniques and fast propagation of BDPT for the first time. Based on these, an MILP-aided method for the propagation of BDPT is proposed. Then, we apply this method to some block ciphers. For SIMON64, PRESENT, and RECTANGLE, we find more balanced bits than the previous longest distinguishers. For LBlock, we find a better 16-round integral distinguisher with less active bits. For other block ciphers, our results are in accordance with the previous longest distinguishers.Cube attack is an important cryptanalytic technique against symmetric cryptosystems, especially for stream ciphers. And the most important step in cube attack is superpoly recovery. Inspired by the CBDP based cube attack proposed by Todo at CRYPTO 2017, we propose a method which uses BDPT to recover the superpoly in cube attack. We apply this new method to round-reduced Trivium. To be specific, the time complexity of recovering the superpoly of 832-round Trivium at CRYPTO 2017 is reduced from $$2^{77}$$ to practical, and the time complexity of recovering the superpoly of 839-round Trivium at CRYPTO 2018 is reduced from $$2^{79}$$ to practical. Then, we propose a theoretical attack which can recover the superpoly of Trivium up to 841 round.