Paper 2016/992

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

Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, 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.

Note: Added acknowledgements.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. SAC 2016
Keywords
quantum cryptanalysishash functionscost models
Contact author(s)
jschanck @ uwaterloo ca
History
2016-11-30: revised
2016-10-17: received
See all versions
Short URL
https://ia.cr/2016/992
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/992,
      author = {Matthew Amy and Olivia Di Matteo and Vlad Gheorghiu and Michele Mosca and Alex Parent and John Schanck},
      title = {Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3},
      howpublished = {Cryptology ePrint Archive, Paper 2016/992},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/992}},
      url = {https://eprint.iacr.org/2016/992}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.