I understand the concept of 'trying all possibilities at once' but can anyone explain this with respect to the fact that my PC only accepts one password at a time? There's no input field that accepts all these possibilities and the same goes for the passphrase field in encryption... Why should we be afraid of quantum computers while being on conventional computer systems?

  • 3
    $\begingroup$ Why would you need to submit a candidate password to your computer in order to crack it? All you have to do is extract the hash and attack it offline. That way, you aren't limited by the speed of the target's computer. $\endgroup$ – forest May 4 '19 at 0:25
  • 2
    $\begingroup$ When a character on TV presses a box against an LCD next to a lock door, uses the word "quantum", and walks in a second later, it's not a realistic portrayal of quantum computing. When a pop-sci communicator or pseudo-scientist or uncle says "every possibility at once" they are misrepresenting things. If the word "quantum" is used, even by otherwise trustworthy people, it's practically certain that either the source is misinformed or they're lying. [Cliche about anyone saying they get quantum physics, doesn't.] $\endgroup$ – Future Security May 4 '19 at 4:00

Well, the best answer I can think of is by referring you to Scott Aaronson's wonderful blog.

Quoting the very header of the blog:

If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

So no, a quantum computer would not try to input all passwords simultaneously to the password checker: as you correctly guessed, this would be nonsense. But a quantum computer can still use the intriguing properties of quantum mechanics to perform some computations which we have no idea how to do using a classical computer, such as using Shor's algorithm to factor a big number in polynomial time, which allows for example to break the RSA cryptosystem. So, if you are on a conventional computer system, you encrypt your password (or any other sensitive data) with RSA, and send it over the network, then you should be afraid if there are (scalable, etc) quantum computers available - for anyone with such a computer will just break the ciphertext in a short amount of time, recovering the sensitive information you had hidden inside. If the password is kept locally and an adversary tries to guess it to log to some service, then a quantum computer will not help him.

  • $\begingroup$ Can a quantum comuter find a hash (or hash-collision) faster than a classical computer? $\endgroup$ – AleksanderRas May 3 '19 at 14:52
  • 7
    $\begingroup$ They can break preimage resistance in $2^{n/2}$ steps instead of $2^{n}$, using an algorithm known as Grover search; they can also break collision-resistance in $2^{n/3}$ steps instead of $2^{n/2}$, although the latter claim is a theoretical hardness result which has been criticized as not so realistic, e.g. here. See for example my answer here. $\endgroup$ – Geoffroy Couteau May 3 '19 at 15:04
  • 1
    $\begingroup$ Re. quote: Everything you've said is good, yet $2^{n/2}$ is not oodles different to $2^{n}$ on the complexity menu. They're both $O^{kn}$ish. And similarity with a drunken squint $2^{n/3}$ looks like $2^{n/2}$. Non of which seems like a quantum epiphany. Yet now there's a big push to post quantum cryptography suggesting the danger is worse than the above solution complexities suggest... $\endgroup$ – Paul Uszak May 5 '19 at 21:57
  • 1
    $\begingroup$ Yup, you got it perfectly right: although it gives a nontrivial speedup over a classical computer for attacking hash functions, there is nothing fearsome in the advantage a quantum computer gives here - just increase the key size a bit to compensate for this mild speedup and you are good. This is why one usually estimates that quantum computers, as far as we know, are not a major threat for symmetric crypto (e.g. AES, SHA). $\endgroup$ – Geoffroy Couteau May 5 '19 at 22:26
  • 2
    $\begingroup$ Where the danger is worse, and this is the reason behind the big and necessary push for post quantum crypto, is when we look at asymmetric cryptography: public key encryption, key exchange, and the like. There, the necessary additional structure of these primitives make them much more sensitive to the additional power of quantum computers. For RSA and ElGamal, for example, quantum computers give a polynomial algorithm fully breaking them - a much more impressive speedup than against hash functions and block ciphers. This is because of the deep structural differences between these primitives. $\endgroup$ – Geoffroy Couteau May 5 '19 at 22:30

Considering quantum computing to break passwords in the online setup would be nonsense. In that setup, passwords are sent to a classical system testing the password. That seems to be the question's scenario.

In the offline setup, the information that allows testing if a password is accepted or not is assumed to have leaked to the attacker (e.g. because the file or database holding password hashes has leaked). Finding the password is a combinatorial problem, and it can't be summarily dismissed that quantum computing could help. With many ifs, it could be that breaking a password requires $O(2^k)$ work for a classical computer, but $O(2^{k/2})$ for a quantum computer, and that it makes the difference between infeasible and feasible. For example, a quantum computer conceivably could help find a password with a given MD5 (a 128-bit hash which used to be a common way to hash passwords), even if the password was very complex (20 letters/digits). However

  • Today's quantum computers are of no help at solving the kind of exact problems involved in symmetric cryptography, including reversing hashes like MD5. It remain hypothetical that this will ever improve markedly. This issue plagues the quantum computer claiming quantum supremacy, which really is only good at some narrow class of problems tolerating approximation, and which supremacy at that is disputed.
  • Modern password hashes are deeply iterative, some using large memory states, and it is even more hypothetical that quantum computers will become useful in attacking that.

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.