The 32nd-order differential attack on MISTY1 without FL functions

We found a 32nd-order differential characteristic of MISTY1 without FL functions, which makes the differential of upper 7 bit of 64-bit output of the 5th round be zero. By using this characteristic and a linearization technique, we show that 6-round MISTY1 without FL functions can be attacked with 2^35.5 of chosen plaintexts and 2^34.3 of computations of FO function. We demonstrate this 6-round attack by a computer simulation. CPU time for the simulation is 2 hours and 35 minutes. This attack reduces the plaintexts to 2^-3.5 and the computations to 2^-14.9 compared to conventional 6-round attack. We also show that 7-round MISTY1 without FL functions can be attacked with 2^36.5 of the plaintexts and 2^112.0 of the computations by using a combination of the 6-round attack and exhaustive search. This 7-round attack reduces the computations to 2^-13.1 although the plaintexts increase 2^24.6 times. These drastic reductions of the computational costs come from counting up the number of occurrences of ciphertexts, and omitting the ciphertexts occurring even number of times from computation.