1

Suppose that I have a password that is n-digits long. Each digit can take m values. So the number of permutations will be m^n. I wanted to know how much time it would take a quantum computer to crack this password.

Is there a specific algorithm to this? If quantum computers are actually commercialized, am I (or literally everyone) in feasible danger (of having our passwords stolen)?

Improve this question
5
  • There's no "algorithm" because it is just straight up math. Quantum Computers are not "magic", they just do more, so they're just faster in the simplest sense. Here are some other SE answers to get you up to speed: 1, 2, 3
    – Nelson
    Commented Jan 14, 2021 at 6:10
  • If you consider that you have used the SHA-x, but note that proper password hashing algorithms will require much further gates than this.
    – kelalaka
    Commented Jan 14, 2021 at 7:22
  • 1
    See Is using quantum computing to break passwords non-sense? at Cryptography.
    – Steffen Ullrich
    Commented Jan 14, 2021 at 7:31
  • 1
    @Nelson quantum computers aren't magic but they also aren't faster in the simplest sense. They are, in fact, very slow in the simplest sense because it will be a long time before they have as much computing power as a classic computer (if ever)
    – Conor Mancone
    Commented Jan 14, 2021 at 11:44
  • @ConorMancone I'll admit I need to brush up on my understanding of what a quantum computer really does. I've come across some very inaccurate definition from very high profile (non-technical) sources. IMO, quantum computing is specialized enough that general IT people probably don't have a good grasp of what it is, nevermind the general population.
    – Nelson
    Commented Jan 15, 2021 at 0:30

1 Answer 1

Reset to default
3

Where a traditional brute force would take m^n computations, a quantum computer would use √(m^n) computations, using Grover's algorithm. Using a password that is twice as long, or using twice as many bits in symmetric encryption give adequate protection against quantum computers.

For asymmetric algorithms, this is different. Using Shor's algorithm, RSA completely falls apart on quantum computers. We would need post-quantum algorithms to have secure asymmetric encryption.

As you can see, quantum computers allow algorithms that wouldn't be possible on classical computers. This enables them to solve problems faster. Quantum computers are not faster classical computers, they are fundamentally different.

Improve this answer
3
  • Actuallt there is Brassard et al.'s algorithm for hash algorithms and NIST-based PQC security level on that. Though we don't use unsalted and pure hash algorithms, the search can be faster a little than Grover's.
    – kelalaka
    Commented Jan 14, 2021 at 12:55
  • One of my passwords has 94^13 permutations. sqrt(94^13) is approximately 10^29.5. That's too large. For perspective, the Earth has roughly 10^18 grains of sand.
    – sato
    Commented Jan 15, 2021 at 7:16
  • @Mastermind817, If a password is poorly hashed (such as with MD5), 10^18 permutations can be exhausted by publicly rentable infrastructure (equivalent to 60 GTX 1080s) in 11 days for under $2000. 10^18 grains of sand on earth isn't daunting when an attacker can inexpensively perform 10^12 calculations per second. In other words, 94^13 is pretty reasonable password strength against most feasible threat models, and is not what I would call "too large". (Something like 94^20, by contrast, is overkill - see twitter.com/jmgosney/status/714599158229786625 for supporting math)
    – Royce Williams
    Commented Jan 16, 2021 at 17:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .