Ruhr-Uni-Bochum

Codebreakers Quantum Computers?

Quantum computers are expected to transform processes in industry and society in the future. A research team consisting of the Cluster of Excellence CASA and the Max Planck Institute for Security and Privacy has for the first time taken an interdisciplinary look at the impact of this technology on password security. They now presented their results at CANS in Vienna.

Copyright: MPI, Maximilian Golla

The race to harness quantum technology is in full progress. In the summer of 2021, the first commercial quantum computer in Europe, in Ehningen near Stuttgart, was inaugurated. IBM and Google are also researching the technology intensively. However, the closer quantum computers come to a realistic reach, the more tangible the threats to IT security become.

Rapid computing power

Quantum computers can solve problems where conventional computers fail. This is due to their information unit. Classical bits, with which normal computers calculate, can only assume the values 0 or 1. In the quantum computer, qubits do this computing work: its processor, which uses the laws of quantum mechanics, works with qubits that are able to accept both values simultaneously. This new computing power can be used in fields such as medicine, for example, to develop new pharmaceuticals. At the same time, the power of quantum computers poses a whole new set of risks to previously common cryptographic techniques. For example, attackers in possession of a powerful quantum computer could access certain encrypted communications, such as online banking.

How quantum computers impact the security of our passwords, has not yet been analyzed in detail. In a first-time interdisciplinary collaboration between the CASA Hubs A (Future Cryptography) and D (Usability) at Ruhr-Universität Bochum and the Max Planck Institute for Security and Privacy, Markus Dürmuth, Maximilian Golla, Philipp Markert, Alexander May, and Lars Schlieper have investigated the impact of quantum technology on password security. They presented their results at this year's CANS (International Conference on Cryptology and Network Security) in Vienna from December 14-16.

Threat to password-based authentication

The researchers tested how attackers can use a specific algorithm to guess passwords. They differentiated between an attack on a single fixed user and a large-scale attack on a whole password database, such as those used by large online services or companies. Attacks on user accounts are often easy to carry out because users usually use the same or simple passwords for numerous online accounts, such as simple number sequences or predictable patterns. Attackers like to exploit this behavior and therefore guess particularly popular passwords first. The simulations of the research team are also based on this observation.

Due to their construction, quantum computers have the advantage that they can guess randomly chosen cryptographic codes faster. The Grover algorithm is responsible for this. Whether this guessing advantage can also be transferred to passwords chosen by humans was previously unclear, since the algorithm expects randomly chosen values. However, users do not choose passwords randomly, but often according to preferences and memorability. In their results, the research team was now able to confirm that user-chosen passwords can also be guessed in far fewer attempts with quantum computers than with conventional computers. Access to the passwords in a protected password database is therefore much faster.

Still a dream of the future?

Even if it will be several years before large enough quantum computers are used, one thing is clear: new protection mechanisms will be required. Passwords would have to be at least twice as long to protect users from quantum computer attackers. However, passwords consisting of 16 randomly selected characters are no longer memorable. The research team therefore recommends the use of a password manager that generates a sufficiently long and random password for each online account and stores it securely.

Funding

This research was funded by the State of North Rhine-Westphalia in the context of the research group "Human Centered Systems Security" and the German Research Foundation in the context of the Cluster of Excellence "Cyber Security in the Age of Large-Scale Adversaries", CASA (EXC 2092 – 390781972).

Original publication

Markus Dürmuth, Maximilian Golla, Philipp Markert, Alexander May, Lars Schlieper: Towards Quantum Large-Scale Password Guessing on Real-World Distributions. International Conference on Cryptology and Network Security (CANS '21), 2021, Wien, Paper Download 

Press contact

Lars Schlieper
Chair for Cryptology and IT Security
Horst Görtz Institute for IT Security
Ruhr-Universität Bochum
Germany
Phone: +49 234 32 24540
Email: lars.schlieper(at)rub.de

Dr. Maximilian Golla
Max Planck Institute for Cyber Security and Privacy
Germany
Phone: +49 234 32 28667
Email: maximilian.golla(at)csp.mpg.de

Author: Barbara-Henrika Alfing

General note: In case of using gender-assigning attributes we include all those who consider themselves in this gender regardless of their own biological sex.