Cryptology ePrint Archive: Report 2016/992

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