This paper proposes novel calculuses of linearizing attack that can be applied to higher order differential attack. Higher order differential attack is a powerful and versatile attack on block ciphers. It can be roughly summarized as follows: (1) Derive an attack equation to estimate the key by using the higher order differential properties of the target cipher, (2) Determine the key by solving an attack equation. Linearizing attack is an effective method of solving attack equations. It linearizes an attack equation and determines the key by solving a system of linearized equations using approaches such as the Gauss-Jordan method. We enhance the derivation algorithm of the coefficient matrix for linearizing attack to reduce computational cost (fast calculus 1). Furthermore, we eliminate most of the unknown variables in the linearized equations by making the coefficient column vectors 0 (fast calculus 2). We apply these algorithms to an attack of the five-round variant of KASUMI and show that the attack complexity is equivalent to 228.9 chosen plaintexts and 231.2 KASUMI encryptions.

Integral cryptanalysis is one of the most powerful attacks on symmetric key block ciphers. Attackers preliminarily search integral characteristics of a target cipher and use them to perform the key recovery attack. Todo proposed a novel technique named the bit-based division property to find integral characteristics. Xiang et al. extended the Mixed Integer Linear Programming (MILP) method to search integral characteristics of lightweight block ciphers based on the bit-based division property. In this paper, we apply these techniques to the symmetric key block cipher KASUMI which was developed by modifying MISTY1. As a result, we found new 4.5-round characteristics of KASUMI for the first time. We show that 7-round KASUMI is attackable with 263 data and 2120 encryptions.