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)?

sato
  • 121
  • 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](https://security.stackexchange.com/questions/82389/calculate-time-taken-to-break-aes-key), [2](https://crypto.stackexchange.com/questions/1145/how-much-would-it-cost-in-u-s-dollars-to-brute-force-a-256-bit-key-in-a-year), [3](https://crypto.stackexchange.com/questions/24307/why-is-aes-unbreakable/24309) – Nelson Jan 14 '21 at 06:10
  • If you consider that you have used the [SHA-x](https://crypto.stackexchange.com/a/75241/18298), but note that proper password hashing algorithms will require much further gates than this. – kelalaka Jan 14 '21 at 07:22
  • 1
    See [Is using quantum computing to break passwords non-sense?](https://crypto.stackexchange.com/questions/70279/is-using-quantum-computing-to-break-passwords-non-sense) at [crypto.se]. – Steffen Ullrich Jan 14 '21 at 07: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 Jan 14 '21 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 Jan 15 '21 at 00:30

1 Answers1

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.

Sjoerd
  • 28,897
  • 12
  • 76
  • 102
  • Actuallt there is [Brassard et al.'s algorithm for hash algorithms](https://crypto.stackexchange.com/a/75241/18298) 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 Jan 14 '21 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 Jan 15 '21 at 07: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 https://twitter.com/jmgosney/status/714599158229786625 for supporting math) – Royce Williams Jan 16 '21 at 17:59