I’ve recently read a number of (layman’s) articles on quantum mechanics and quantum computing, and keep seeing examples along the lines of “Quantum computing can crack passwords quickly by trying all combinations at once”. The example goes on to show that rather than passing in an N-bit value, an N-qubit value is passed in which is effectively all combinations due to its superposition state. The value is then collapsed to the state which was successful; i.e. giving the correct password.

The problem I have with this example, is it assumes that our `ValidatePassword`

function accepts a qubit array as an input; which I suspect people would know better than to do.

Is this example just an oversimplification to demonstrate something which tries many possibilities at once; or is there a real potential security concern with the advent of quantum computers?

4

Is this example just an oversimplification to demonstrate something which tries many possibilities at once; or is there a real potential security concern with the advent of quantum computers?

It’s primarily just an oversimplification, but there’s a real security concern there, too.

The problem I have with this example, is it assumes that our

`ValidatePassword`

function accepts a qubit array as an input; which I suspect people would know better than to do.

For web servers across the Internet, this is spot on. You can’t send qubits over the Internet, so there’s no way to send this “quantum superposition of passwords” to the server.

The problem arises when I have an algorithm that somehow lets me test whether or not any given password is correct. Suppose, for example, that I’ve broken into the website’s database and found a salted password hash. Now I can check whether or not a password is correct by salting and hashing it and comparing it against the hash I found.

Suppose that it takes 1 millisecond to test a password, and there are 1,000,000,000,000,000,000 possible passwords. With classical computing, if I wanted to try out every possible password, it would take me 1,000,000,000,000,000,000 milliseconds, which is over 30 million years.

With quantum computing, things are different. Can I just try all of the passwords at once, and then “collapse to the successful value”, thereby figuring out the password in mere seconds? No, it’s not that simple.

What I can do is use Grover’s algorithm. Now, Grover’s algorithm is complicated and I don’t know how it works. But I do know what it *does*.

With Grover’s algorithm, you start with a quantum superposition. Then you do “the Grover iteration” a bunch of times. Doing one Grover iteration involves performing the password testing algorithm once, along with a little bit of other stuff. The number of times that you have to do the Grover iteration is approximately equal to the square root of the number of possible passwords, or 1,000,000,000. Why do you have to do it that many times? I don’t know. Then you do some more stuff, and somehow, Grover’s algorithm tells you what the answer is.

So how fast can we crack the password? Well, suppose that our quantum computer can perform the password testing algorithm in 1 millisecond, just like a classical computer can. (In reality, it will probably be slower, because making a fast quantum computer is harder than making a fast classical computer.) Then the amount of time it will take you to crack the password is about 1,000,000,000 milliseconds, or about 12 days. Not bad.

What’s the upshot of all this? Quantum computing doesn’t simply allow you to “try everything at once”, but it does make brute-force searching a whole lot faster.

7

Quantum computing doesn’t crack passwords; it cracks *encryption.*

The problem with the currently popular [encryption] algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor’s algorithm.

https://en.wikipedia.org/wiki/Post-quantum_cryptography

Articles like this one are fundamentally misguided; they give the public the impression that all password systems will break when the first usable quantum computer is created. That’s just not the case. By the article’s own admission, it’s not about passwords, but about encryption, which only affects people using encryption.

Of course, if you manage to be successful at intercepting a person’s login attempt over a secure connection using a quantum computer to break the connection’s encryption, then naturally you now have their login credentials, but that’s not quite the same thing as “cracking passwords.”

1