A New Approach to χ2 Cryptanalysis of Block Ciphers⋆

Abstract. The first contribution of this paper is a new approach to χ2 analyses of block ciphers in which plaintexts are chosen in a manner similar to that in a square/saturation attack. The consequence is a faster detection of χ2 correlation when compared to conventional χ2 cryptanalysis. The second contribution of the paper is the application of a technique similar to the aforementioned approach, but aided by linear cryptanalysis, on the RC6-family of block ciphers. Using this technique we (i) improve the previously best-known χ2 attacks on reduced-round RC6, and (ii) mount the first attacks on other RC6-like block ciphers- MRC6 and ERC6. The analyses of these fast primitives were also motivated by their low diffusion powers and, in the case of MRC6 and ERC6, their large block sizes that favour construction of hash functions. Our analysis indicates that up to 98 rounds of MRC6 and 44 rounds of ERC6 could be broken. We expect our technique to be applicable to other block ciphers also.