At first glance: Assuming that the output of the password hashing function is large enough, quantum computers should have no effect on password encryption as on symmetric cryptography in general. Is that correct?

More precisely: Grover's search invokes an oracle instead of searching a dataset. Does this mean that dictionary attacks cannot be performed efficiently with quantum computers? Is there any other way in which quantum computers could be used for password cracking?

  • $\begingroup$ Dictionary attacks are one thing, brute force attacks on a limited input domain are another. Password variations could also be an interesting attack vector I guess. I can see the latter being sped up, but I'm not sure if I've seen any kind of paper on it. Then again, I haven't been actively looking for them. $\endgroup$ – Maarten Bodewes Oct 31 '19 at 14:40
  • $\begingroup$ Are you referring to password hashing / PKBDF to find a password for a particular hash? Because your title says password encryption, not password based encryption or password hashing. I'll add the word "based" as password based encryption is in the tags. $\endgroup$ – Maarten Bodewes Oct 31 '19 at 14:42

Currently we use slow key derivation functions. If a hypothetical quantom computer could run these as fast as a classical computer (Which is a huge If) grover's algorithm would allow searching over the equivalent of the squared root of the password space.

However even a sizeable quantom computer won't be able to do that. We will be seeing Shor's algorithm being used to attack RSA and DH before we see Grover's used to attack old 128 bit encryption. And that before it will be used against a password based key derivation function.

And I expect none of this soon.


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.