Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound

In this paper we spot light on dedicated quantum collision attacks on concrete hash functions, which has not received much attention so far. In the classical setting, the generic complexity to find collisions of an n-bit hash function is minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O(2^{n/2})$documentO(2n/2), thus classical collision attacks based on differential cryptanalysis such as rebound attacks build differential trails with probability higher than minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2^{-n/2}$document2-n/2. By the same analogy, generic quantum algorithms such as the BHT algorithm find collisions with complexity minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$O(2^{n/3})$documentO(2n/3). With quantum algorithms, a pair of messages satisfying a differential trail with probability p can be generated with complexity minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$p^{-1/2}$documentp-1/2. Hence, in the quantum setting, some differential trails with probability up to minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2^{-2n/3}$document2-2n/3 that cannot be exploited in the classical setting may be exploited to mount a collision attack in the quantum setting. In particular, the number of attacked rounds may increase. In this paper, we attack two international hash function standards: AES-MMO and Whirlpool. For AES-MMO, we present a 7-round differential trail with probability minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2^{-80}$document2-80 and use it to find collisions with a quantum version of the rebound attack, while only 6 rounds can be attacked in the classical setting. For Whirlpool, we mount a collision attack based on a 6-round differential trail from a classical rebound distinguisher with a complexity higher than the birthday bound. This improves the best classical attack on 5 rounds by 1. We also show that those trails are optimal in our approach. Our results have two important implications. First, there seems to exist a common belief that classically secure hash functions will remain secure against quantum adversaries. Indeed, several second-round candidates in the NIST post-quantum competition use existing hash functions, say SHA-3, as quantum secure ones. Our results disprove this common belief. Second, our observation suggests that differential trail search should not stop with probability minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2^{-n/2}$document2-n/2 but should consider up to minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2^{-2n/3}$document2-2n/3. Hence it deserves to revisit the previous differential trail search activities.