학술논문
Towards quantum large-scale password guessing on real-world distributions.
Document Type
Proceedings Paper
Author
Dürmuth, Markus (D-BCHM-NDM) AMS Author Profile; Golla, Maximilian (D-MPISP) AMS Author Profile; Markert, Philipp (D-BCHM-NDM) AMS Author Profile; May, Alexander (D-BCHM-NDM) AMS Author Profile; Schlieper, Lars (D-BCHM-NDM) AMS Author Profile
Source
Subject
94 Information and communication, circuits -- 94A Communication, information
94A62Authentication and secret sharing
94A62
Language
English
Abstract
Summary: ``Password-based authentication is a central tool for end-usersecurity. As part of this, password hashing is used to ensure thesecurity of passwords at rest. If quantum computers become available atsufficient size, they are able to significantly speed up thecomputation of preimages of hash functions. Using Grover's algorithm,at most, a square-root speedup can be achieved, and thus it is expectedthat quantum password guessing also admits a square-root speedup.However, password inputs are not uniformly distributed but highlybiased. Moreover, typical password attacks do not only compromise arandom user's password but address a large fraction of all users'passwords within a database of millions of users.\par ``In this work, we study those quantum large-scale password guessingattacks for the first time. In comparison to classical attacks, westill gain a square-root speedup in the quantum setting when attackinga constant fraction of all passwords, even considering strongly biasedpassword distributions as they appear in real-world password breaches.We verify the accuracy of our theoretical predictions using theLinkedIn leak and derive specific recommendations for password hashingand password security for a quantum computer era.''