MISTY1 is a 64-bit block cipher that has provable security against differential and linear cryptanalysis. MISTY1 is one of the algorithms selected in the European NESSIE project, and it has been recommended for Japanese e-Government ciphers by the CRYPTREC project. This paper reports a previously unknown higher order differential characteristic of 4-round MISTY1 with the FL functions. It also shows that a higher order differential attack that utilizes this newly discovered characteristic is successful against 6-round MISTY1 with the FL functions. This attack can recover a partial subkey with a data complexity of 253.7 and a computational complexity of 264.4, which is better than any previous cryptanalysis of MISTY1.

Linear cryptanalysis using sieve methods is a technique proposed by Takeda et al. in 1998 as an attack capable of breaking ciphers with smaller amounts of data than linear cryptanalysis (LC) by using data that satisfies linear sieve conditions. This paper shows that when considering the amount of data required for cryptanalysis in Takeda et al.'s proposed sieved linear cryptanalysis (S-LC), it is necessary to take into account the independence of keys relating to the linear mask (Linear key) and keys relating to the linear sieve mask (Sieve key) in rounds that are affected by these keys. If p is the probability that the linear approximate expression holds and p* is the probability after applying the linear sieve, then it has been shown that when the Linear keys are independent of the Sieve keys, then it is necessary to select the linear mask and linear sieve mask so that a larger value of p*-p is obtained. It is also shown that the amount of data needed for S-LC cannot be reduced below the amount of data needed for LC when the Linear key and Sieve key are not independent. In fixed sieve linear cryptanalysis, it is shown that the amount of data needed for cryptanalysis cannot be reduced regardless of the independence of the Linear key and Sieve key.