Automatic Quantum Multi-collision Distinguishers and Rebound Attacks with Triangulation Algorithm

In EUROCRYPT 2020, Hosoyamada and Sasaki found that differential paths with probability \(2^{-2n/3}\) can be useful in quantum collision attacks, v.s. \(2^{-n/2}\) for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikolić at CRYPTO 2009, and propose quantum multi-collision distinguishers. We use CP-tool to automatically search for the configurations for multi-collision distinguishers and rebound attacks by taking into account related-key/single-key differentials of the underlying block cipher. We apply our method to AES-like primitives including block ciphers AES, Rijndael, Saturnin and AES-hashing modes AES-DM and AES-HCF.