**Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3**

*Matthew Amy and Olivia Di Matteo and Vlad Gheorghiu and Michele Mosca and Alex Parent and John Schanck*

**Abstract: **We investigate the cost of Grover's quantum search algorithm when used in the
context of pre-image attacks on the SHA-2 and SHA-3 families of
hash functions. Our cost model assumes that the attack is run on a surface
code based fault-tolerant quantum computer. Our estimates rely on a time-area
metric that costs the number of logical qubits times the depth of the circuit
in units of surface code cycles. As a surface code cycle involves a
significant classical processing stage, our cost estimates allow for crude, but
direct, comparisons of classical and quantum algorithms.

We exhibit a circuit for a pre-image attack on SHA-256 that is approximately $2^{153.8}$ surface code cycles deep and requires approximately $2^{12.6}$ logical qubits. This yields an overall cost of $2^{166.4}$ logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately $2^{146.5}$ surface code cycles deep and requires approximately $2^{20}$ logical qubits for a total cost of, again, $2^{166.5}$ logical-qubit-cycles. Both attacks require on the order of $2^{128}$ queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as $275$ billion times more expensive than one would expect from the simple query analysis.

**Category / Keywords: **quantum cryptanalysis, hash functions, cost models

**Original Publication**** (in the same form): **SAC 2016

**Date: **received 13 Oct 2016, last revised 30 Nov 2016

**Contact author: **jschanck at uwaterloo ca

**Available format(s): **PDF | BibTeX Citation

**Note: **Added acknowledgements.

**Version: **20161130:163543 (All versions of this report)

**Short URL: **ia.cr/2016/992

[ Cryptology ePrint archive ]