Paper 2021/703

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

Abstract

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{\'c} 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.