You are looking at a specific version 20200219:164657 of this paper. See the latest version.

Paper 2020/213

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

Akinori Hosoyamada and Yu Sasaki

Abstract

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 $O(2^{n/2})$, thus classical collision attacks based on differential cryptanalysis such as rebound attacks build differential trails with probability higher than $2^{-n/2}$. By the same analogy, generic quantum algorithms such as the BHT algorithm find collisions with complexity $O(2^{n/3})$. With quantum algorithms, a pair of messages satisfying a differential trail with probability $p$ can be generated with complexity $p^{-1/2}$. Hence, in the quantum setting, some differential trails with probability up to $2^{-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 $2^{-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 $2^{-n/2}$ but should consider up to $2^{-2n/3}$. Hence it deserves to revisit the previous differential trail search activities.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
symmetric key cryptographyhash functioncryptanalysiscollisionquantum attackAES-MMOWhirlpoolrebound attack
Contact author(s)
akinori hosoyamada bh @ hco ntt co jp
History
2020-02-19: received
Short URL
https://ia.cr/2020/213
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.