9

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?

gnat
  • 21,442
  • 29
  • 112
  • 288
JohnLBevan
  • 425
  • 2
  • 4
  • 13
  • 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 04 '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 04 '16 at 20:32
  • 2
    [Security StackExchange](http://security.stackexchange.com/questions) 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 04 '16 at 20:35
  • 1
    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 04 '16 at 20:41

2 Answers2

13

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.

Tanner Swett
  • 1,359
  • 8
  • 15
  • 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 04 '16 at 20:53
  • 5
    @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 04 '16 at 20:56
  • 2
    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 04 '16 at 20:56
  • 3
    @RobertHarvey: this is not a hypothetical scenario, see http://thenextweb.com/apps/2016/08/31/68-million-dropbox-passwords-stolen-by-hackers/#gref – Doc Brown Oct 04 '16 at 21:10
  • @DocBrown: Naturally. No quantum computer required. – Robert Harvey Oct 04 '16 at 21:48
  • @RobertHarvey: the article says those 68 million passwords were encrypted, and I guess a usable quantum computer would make it feasible to get them decrypted in a reasonable amount of time. So your doubts this kind of compromisation could become a real world problem was caught up by reality some only some weeks before. – Doc Brown Oct 05 '16 at 05:48
  • @RobertHarvey one example is you might have a password-encrypted file to decrypt, such as a cryptocurrency wallet private key. – rplevy Jun 29 '17 at 06:46
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."

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
  • 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. – user253751 Oct 05 '16 at 00:18