How Does Quantum Impact Password Attacks?

Yeah, quantum computers are likely to be able to crack passwords from every angle.

[Note: This post has not undergone my normal edition process and may contain more typos and grammatical errors than usual.]

Many of us have heard how when quantum computers become “sufficiently capable” most of today’s encryption systems relying on traditional asymmetric encryption (e.g., RSA, Diffie-Hellman, ECC, etc.) will become compromised. If you haven’t, feel free to read any of my articles on the subject including this recent one: https://www.dhirubhai.net/pulse/have-you-started-your-post-quantum-cryptography-inventory-grimes .

A very common question I get is “How will quantum computers impact our passwords?”

That’s a great question. This article is the answer. I’m going to start a little bit broader and then get into the specific question most people are asking which is “How long or strong does my password need to be to safe against quantum computer attacks?”

[Big caveat: I could be wrong about what I’m saying below. There isn’t a lot of literature on this issue…this may be the first…and I’m taking my best guesses. I don’t have a Ph.D. in quantum physics. I’m not a quantum scientist. I’m just a regular guy trying to apply what I know of quantum physics, computers, and algorithms, and apply them to password attacks. I may be wrong and I’ll be the first to admit I made a mistake if someone corrects me. But I've tried to be thoughtful on the issues.]

First realize that most password attacks (e.g., social engineering, password theft, unauthorized password reset, etc.) don’t care about the strength of your password. Very strong or super weak the attacks just get them or bypass them. Quantum computers and protection are very unlikely to impact the majority of these types of password attack threats.

Quantum Attacks on Asymmetric Authentication System Protections

Most authentication systems are protected by a combination of asymmetric and symmetric cryptography. When sufficiently capable quantum computers are available, the asymmetric protections will likely be compromisable if the attacker has sufficient quantum capability and can access those protections. ?So, ask yourself if the asymmetric protections of your authentication system are readily accessible to an attacker, and if so, enable quantum-resistant (i.e., “post-quantum”) mitigations. You need to thoughtfully consider this problem, do the research around your authentication system, and then take the appropriate mitigations if needed. These protections include:

·????????Physical isolation

·????????Increasing symmetric and hash key sizes

·????????Replacing asymmetric ciphers, keys, and digital signatures, with post-quantum cryptography alternatives

·????????Using QKD

·????????Using hybrid solutions

·????????Using quantum-enabled protections

For more information on how to respond to quantum threats against cryptography in general, please read the Cloud Security Alliance’s Practical Preparations in a Post-Quantum World (https://cloudsecurityalliance.org/artifacts/practical-preparations-for-the-post-quantum-world/).

Quantum Attacks on Symmetric Authentication System Protections

Most authentication systems use symmetric encryption (e.g., AES, etc.) and cryptographic hashes (e.g., NT, SHA-2, PBKDF2, BCRYPT, etc.). Grover’s algorithm (https://en.wikipedia.org/wiki/Grover%27s_algorithm ) allows sufficiently capable quantum computers to halve the effective length of the protective power of symmetric ciphers and hashes. This means that once sufficiently capable quantum computers are available, the protection of your existing symmetric cipher keys and hashes will be equivalent to keys and hashes one-half the size. So, if you use AES-256-bit symmetric encryption, its effective protection would be equivalent to AES-128-bit after sufficiently capable quantum computers are available.

Note: Grover’s algorithm doesn’t just effectively halve the keyspace protection of symmetric ciphers and hashes. It’s worse than that. Halving the keyspace of a symmetric cipher or hash would mean removing just a single bit (i.e., AES-256 would become AES-255). Each additional bit of a symmetric key or hash doubles the potential protective keyspace. Grover’s algorithm provides a quadratic speed up, which equates to the key size’s effective protection being halved. This is far more than simply losing half the potential attack keyspace.

To get the equivalent protection from a symmetric key or hash after sufficiently capable quantum computers are available, you would have to double the key size. So, if you’re using AES-256-bit, you’d need to move to AES-512-bit. If you’re using SHA-2-256-bit hashes, you’d need to move to SHA-2-512, and so on.

The good news is that as long as you’re using AES-256-bit or SHA-2-256-bit already, you probably don’t need to worry. The National Institutes of Standards and Technology (NIST) has determined that anyone already using those ciphers and hashes with 256-bits of protection are already sufficiently protected against predicted quantum attacks (at least until someone improves on Grover’s algorithm).

Windows NT hashes are not as strong as SHA-2-256-bit hashes. As an example, according to this study (https://t.co/NKYIrKwUDb ), SHA-2 hashes are over 13 times more protective than NT hashes, so adjust your protection calculations. This will come into play in the next and final section.

Quantum Computers Impact on Password Guessing and Cracking

Most people who are asking me how quantum computers will likely impact passwords are really asking, “How much longer and stronger do I need to make my password due to password guessing or cracking attacks by quantum computers?”

Password guessing and password hash cracking are two different types of password attacks, and they require different password policy requirements to be mitigated. Password hash cracking requires stronger passwords to mitigate successful attacks. I will cover both now.

Quantum Password Guessing

Password guessing is when an adversary guesses at a victim’s password via an online/local login screen where the victim themselves could otherwise log in with their login name and password combination to authenticate to a program or system. The attacker can guess as many times as they like, manually or using an automated tool, but is limited by the online/local login screen invalid login mitigations, authentication processing speed and bandwidth. Common mitigations include password construction policies, account lockout policies, login attempt throttling, password expiration, checks for weak passwords, invalid login event monitoring and requiring multifactor authentication.

In general, quantum computers will likely not radically change the success rate of password guessing attacks, because the limitation of how fast a quantum-enabled attacker can guess at a particular online logon prompt isn’t changed by quantum computers at all and there is no (at this time) quantum algorithm that magically makes password guessing attacks faster. If you gave both conventional and quantum computers equal access to a password guessing logon attack, the speed at which they can guess a password is not different. And in most authentication systems without appropriate password guessing mitigations (e.g., account lockout, rate limiting, etc.) would not allow a quantum computer to guess faster than a non-quantum computer.

But here is the big IF. There is strong evidence to suggest that quantum-enabled computers can process far more inputs to enable them to make far better decisions or guesses even if given the same inputs as given to a conventional computer. A sufficiently capable quantum computer can more easily solve many problems with trillions of potential outcomes. Or at least that is the promise. It is with this idea that most quantum scientists believe that quantum-enabled computers will be far more likely to better figure out human behavior. This will benefit any skill where figuring out human behavior more accurately will improve the system or service. For example, investment types are excited that quantum computers will allow them to make better financial decisions and better game the market based upon better predicted human investment behavior.

Well, better predicting human behavior also applies to password guessing attacks. The best automated password guessing attacks don’t guess randomly or sequentially (e.g., aa, ab, ac, ad, etc.). Today, most automated password guessing attacks attempt to figure out the most likely passwords that a human will use at a particular logon instance (based on the required password policy) and use those guesses first versus the less likely passwords. For instance, most people don’t use q’s or z’s in their passwords, so any passwords with q’s or z’s would be tried after passwords that didn’t contain them. Today, most user’s “complex” passwords use a “root” word in the password that is a word or words based upon their native tongue; the first character of the password is an uppercase consonant followed by a lowercase vowel, and if any numbers or symbols are required they are usually at the end. In fact, 80% of passwords contain the same 17-characters even though 94-different characters are available on the standard US keyboard. Predicting what passwords a human may use is an “art of password guessing” hacking. Hackers who are better at guessing what types of passwords a victim is more likely to use are more likely to successfully guess the password than a hacker (or system) that doesn’t.

Quantum-enabled computers are expected to be better at predicting human behavior, and thus a quantum-enabled password guessing computer (perhaps using quantum-enabled AI) could be expected to successfully guess a victim’s password (unless that password is fully random) given the same number of allowed attempts. Future potential victims can protect their passwords by making them fully random, stronger, and/or less predictable.

Quantum Password Hash Cracking

Password hash cracking is where an attacker has somehow previously obtained a victim’s password hash (most passwords are usually stored in their cryptographic hash forms in today’s operating systems and many/most applications). When this occurs, the attacker can guess at the password’s hash using what is known as an offline password hash cracking attack (also commonly known as a rainbow table attack, although there are some differences) as fast as their hardware/software combination allows. There are no artificial defender guessing mitigations, like account lockout and rate throttling, to stop the attacker from guessing as fast as they can.

This can be very fast. Today, some password hash cracking “rigs” are capable of guessing many tens of trillions of times a second. Would your password withstand someone guessing at it tens of trillions of times a second? Most aren’t.

As covered above, sufficiently capable quantum computers using Grover’s algorithm can be expected to halve the protective power of hashes. Thus, a rudimentary response is that defenders would need to double the size of their password hash keys and/or passwords to get the same effective protection. So, if you have a 12-character password today, you’d need a 24-character password to get the same protective protection. If your password hash is created using a 256-bit cryptographic hash today, you’d need a 512-bit cryptographic hash to gain the same effective protection once sufficiently capable quantum computers are available. You will get the same effective protection by doubling the size of your password.

Note: As covered above, different hashes have different inherent protective capabilities against guessing attacks. SHA-2, PBKDF2, and BCRYPT hashes are more protective than Windows NT hashes. But if you’re using the same cryptographic hash in both pre-quantum and post-quantum scenarios, you’ll need to double your key size or password length to gain the same effective protection.

Note: This analysis also isn’t taking into account password hash collisions where the underlying cryptographic hash has the same hash for different passwords. Most hashes will have “collisions” even if the passwords are different. Chances of collisions increase as password size increases.

We also have to bring back the potential guessing improvements. The best password hash crackers also attempt to guess using more likely passwords first as well. Thus, a quantum-enabled computer that is able to better predict human password selection behavior can be expected to do password hash cracking faster as well on all human-created passwords (that are not fully random).

Summary

So, it can be expected that both password guessing and password hash cracking will be improved by sufficiently capable quantum computers. At the very least, defenders will need to double their symmetric encryption protections, password hash key sizes, and passwords, to get the same effective protections, and this is before considering the impact of sufficiently capable quantum computers being better able to predict human-created passwords.

Password system administrators will need to make sure their systems include post-quantum mitigations to prevent successful quantum attacks. Users will need double the size of any of their human-created passwords (if not fully random) to get the same effective protection.

Of course, no one wants to create double-sized passwords. Instead, users should use phishing-resistant multifactor authentication (MFA) or strong passwordless solutions where they can to protect valuable data and systems and use a password manager to create and use long (as possible) perfectly random passwords that are unique for each system they logon to. When a defender cannot use phishing-resistant MFA or a password manager and must create their own passwords, those passwords need to at least double the current strength to get the same effective protection. And as quantum computers become more capable of predicting human behavior, even those stronger passwords (or passphrases) will become increasingly susceptible to quantum attacks.

In closing, what impact will sufficiently capable quantum computers have on passwords? I think it’s another strong reason why passwords need to go away even though they seem likely to be with us another decade or more.