3

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?

  • 2
    It just means it's able to send everything at basically the same time even though these are X requests. Still these are individual requests. You can't just pass an array of passwords and hope for the validation to see 'oh it's an array lets try with everything then'. Yes there are security concerns, but many applications already prevent that by letting your X tries before blocking an account. Good luck sending your qubit-N passwords. – Steve Chamaillard Oct 4 '16 at 20:23
  • It's too early to say. They break some existing algorithms, they may break others, but they may also be used to deploy new algorithms that neither system can effectively break. – whatsisname Oct 4 '16 at 20:32
  • 1
    Security StackExchange may be a better place to ask. Anyway, this is less about login situations where you have to enter a password. It's about encrypted connections like https where you have a package and want to decrypt its content. So you don't depend on some server to 'validate' anything for you (and could easily block too many attempts). You work with the encrypted data and let the quantum computer find the key which can all happen on your local machine (plus the quantum machine). Once cracked you are now free to run man in the middle stuff. – thorsten müller Oct 4 '16 at 20:35
  • Part of the problem you have is assuming that the attackers are doing anything at all with your ValidatePassword function. Very few attackers will sit there and throw random password attempts at your login screen (or equivalent), hoping to eventually break in. That's too easy to beat, just put a time delay between attempts. Real attacks tend to involve getting a toehold inside the network via some other means, then stealing the password file. Then they just need to find passwords that hash to the same hashes in the password file, which they can do at their leisure on their own computers. – 8bittree Oct 4 '16 at 20:41
8

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.

  • How do you intend to test all 1,000,000,000,000,000,000 possible passwords when you're allowed 5 attempts before you're locked out? – Robert Harvey Oct 4 '16 at 20:53
  • 4
    @RobertHarvey By having broken into the website's database and found a salted password hash that I can test locally as much as I want. – Tanner Swett Oct 4 '16 at 20:56
  • 1
    I would suggest that, if the website has already been compromised in this fashion, you probably don't need a quantum computer to wreak havoc. – Robert Harvey Oct 4 '16 at 20:56
  • 1
    @RobertHarvey: this is not a hypothetical scenario, see thenextweb.com/apps/2016/08/31/… – Doc Brown Oct 4 '16 at 21:10
  • @DocBrown: Naturally. No quantum computer required. – Robert Harvey Oct 4 '16 at 21:48
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
    AFAIK, it also only mainly asymmetric encryption. Most symmetric encryption only needs key lengths doubled, because of Grover's algorithm. So it breaks TLS (which relies on asymmetric encryption) but it doesn't break any kind of manually-set-up point-to-point secure link. – immibis Oct 5 '16 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.