Cryptology ePrint Archive: Report 2021/1299

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

Markus Dürmuth and Maximilian Golla and Philipp Markert and 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.

Category / Keywords: Passwords, Quantum Computing, Hash Function, Zipf

Original Publication (in the same form): CANS 2021

Date: received 27 Sep 2021

Contact author: lars schlieper at rub de

Available format(s): PDF | BibTeX Citation

Version: 20210928:181709 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]