  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.
