Improving algorithm 2 in multidimensional (zero-correlation) linear cryptanalysis using \(\chi ^2\)-method

The multidimensional linear cryptanalysis and the multidimensional zero-correlation linear cryptanalysis have been widely used in the attacks on block ciphers. In the multidimensional linear cryptanalysis with \(\chi ^2\)-method and the multidimensional zero-correlation linear cryptanalysis, the statistics used to distinguish the right key and wrong keys are calculated from the probability distribution of multidimensional (zero-correlation) linear approximations. In this paper, we show that the statistics can be computed directly from the empirical correlations of multidimensional (zero-correlation) linear approximations for random plaintext set. In this way, the computation cost of the probability distribution can be removed. In the situation where FFT technique can be applied to calculate the correlations, our proposed computing method for the statistics can decrease the time complexity of multidimensional (zero-correlation) linear cryptanalysis. As an illustration, the Feistel network with bijective round functions consisting of the modular additions or XORs with subkeys and CAST-256 have been attacked with our revised multidimensional zero-correlation linear cryptanalysis. Our attacks on such kind of Feistel networks are the best according to the number of rounds and we improved the previous multidimensional zero-correlation attack on CAST-256 from 28 to 29 rounds. Compared with the best attack on 29-round CAST-256 with multiple zero-correlation linear cryptanalysis method, our attack leads to the same complexity but without any assumption of independence. Therefore our attack on CAST-256 is the best attack without any assumption.