Paper 2021/1299

Towards Quantum Large-Scale Password Guessing on Real-World Distributions

Markus Dürmuth, Maximilian Golla, Philipp Markert, Alexander May, and Lars Schlieper

Abstract

Password-based authentication is a central tool for end-user security. As part of this, password hashing is used to ensure the security of passwords at rest. If quantum computers become available at sufficient size, they are able to significantly speed up the computation of preimages of hash functions. Using Grover's algorithm, at most, a square-root speedup can be achieved, and thus it is expected that quantum password guessing also admits a square-root speedup. However, password inputs are not uniformly distributed but highly biased. Moreover, typical password attacks do not only compromise a random user's password but address a large fraction of all users' passwords within a database of millions of users. In this work, we study those quantum large-scale password guessing attacks for the first time. In comparison to classical attacks, we still gain a square-root speedup in the quantum setting when attacking a constant fraction of all passwords, even considering strongly biased password distributions as they appear in real-world password breaches. We verify the accuracy of our theoretical predictions using the LinkedIn leak and derive specific recommendations for password hashing and password security for a quantum computer era.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. CANS 2021
Keywords
PasswordsQuantum ComputingHash FunctionZipf
Contact author(s)
lars schlieper @ rub de
History
2021-09-28: received
Short URL
https://ia.cr/2021/1299
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1299,
      author = {Markus Dürmuth and Maximilian Golla and Philipp Markert and Alexander May and Lars Schlieper},
      title = {Towards Quantum Large-Scale Password Guessing on Real-World Distributions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1299},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1299}},
      url = {https://eprint.iacr.org/2021/1299}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.