93

This is a spin off from: Use multiple computers for faster brute force

Here's at least one source which says that quantum computers are on the way to being able to break RSA in the not too distant future. I am not a security expert, and don't know the difference between that and AES, but might this throw a monkey wrench into this idea that it's impossible to crack these modern encryption mechanisms?

MIT's new 5-atom quantum computer could make today's encryption obsolete

Perhaps some of you who are more knowledgeable on the subject could weigh in?

Improve this question
7
  • 1
    If I don't err from what I read from literatures, quantum computers could only reduce the block length (and key length) "effectively" to one half of the nominal values. Thus I recently pointed out a simply way to do that doubling for a given block cipher in order to counterbalance the potential risk of adversary's having quantum computers available. See s13.zetaboards.com/Crypto/topic/7504586/1/
    – Mok-Kong Shen
    Commented Mar 6, 2016 at 12:46
  • 1
    @Mok-KongShen, you err. Shor's algorithm cracks factoring in polynomial, as opposed to exponential, time.
    – user1717828
    Commented Mar 6, 2016 at 17:47
  • 6
    @user1717828 that's why you use eliptic curves and not prime factorization. But that has nothing to do with AES.
    – JDługosz
    Commented Mar 6, 2016 at 17:58
  • 1
    @JDługosz Elliptic Curves get their strength from the discrete log problem, which is also broken by Shor's in poly-time. Not to mention that ECC has much shorter key lengths, making ECC more vulnerable to quantum computers than RSA is.
    – Mike Ounsworth
    Commented Mar 10, 2016 at 17:53
  • 1
    @JonasDralle your comment is completely wrong. AES is not crackable by quantum computer, it doesn't use prime numbers (you're thinking of RSA). QKC (which uses OTP) doesn't need quantum computer and many implementations are broken despite "mathematical proofs". It also doesn't replace classic ciphers for many purposes.
    – dchest
    Commented Jun 30, 2016 at 13:34

4 Answers 4

Reset to default
116

Quantum computing will change the encryption game, but it is not yet clear how much it will change. It's not clear because we are not yet certain what sorts of problems quantum computers can solve. As mentioned, RSA is dramatically weakened by quantum computing because the factoring of primes can be done in polynomial time using Shor's Algorithm. However, not all cryptographic routines are known to be as weak vs. quantum computing.

You may have heard of P (polynomial time), NP (nondeterministic polynomial time -- problems that given the right answer can be checked in polynomial time), and NP-Complete (the hardest NP problems). Prime factorization of large composite numbers is known to be an NP problem and is thought by many to not be P problem. That means a conventional computer would most likely¹ need super-polynomial time (at best sub-exponential time like GNFS) to do the factorization and RSA encryption depends on this. NP-complete is a slightly more demanding class of problem. Any instance of an NP problem can be reduced to an instance of an NP-complete problem. (This is true even if the NP problem is another NP-complete problem.) This means if you ever found a polynomial time solution for an NP-complete problem, you would have a polynomial time solution for every NP problem. If you did so using a classical computer, you would have proven P = NP.

Quantum computers have their own complexity class. BQP is the class of problems that can be [statistically] solved by a quantum computer in polynomial time. It is known that factorization is in BQP, because we have Shor's algorithm. What is yet unknown is whether BQP contains NP-complete or not. It is currently theorized that it does not, meaning there are NP-complete problems that still take exponential time, even with a quantum computer, but the mathematicians are still crunching away at that theory.

Integer factorization sits in an interesting middle ground. We know it is part of BQP (because we found Shor's algorithm). We also know that it is a problem within NP (it is NP because the factorization can be proven in polynomial time just by multiplying the numbers back together). What we don't yet know is whether it is P, NP-but-not-P, or NP-complete. Nobody has been able to prove it one way or another. It could actually be a P problem, solvable with a classical computer in polynomial time, making it very weak for encryption purposes. It could be a NP-complete problem, which given that we know it is in BQP, would imply that quantum computers can solve any NP problem in polynomial time, which would be a major blow to cryptography in general.

Many upcoming encryption algorithms are starting to use other problems besides prime factorization as their root. In particular, a set of problems based on lattices are thought to be particularly hard to break using quantum computers. If all NP problems are part of BQP, this won't help any, but we're still figuring that detail out to this day.

As it turns out, AES is not affected by Shor's algorithm. Grover's algorithm allows brute-forcing an n-bit key in O(2n/2) time instead of the O(2n) time required by classical computers. Therefore, an 128-bit AES key could be brute forced in O(264) time by a sufficiently powerful quantum computer that can do Grover's algorithm with 128+ qubits for 2^64 time.

¹ The wise and challenging commenters below are picking away at the imprecision in my wording. Technically it is not known whether NP problems requires exponential time or not. It is possible that the NP class of problems and the P class of problems are the same. However, most mathematicians believe it is much more likely that P != NP, simply because so far it doesn't look like it. If we want to talk in betting terms, just look at how much you could make answering the question. if you prove P and NP are distinct, you can earn the Clay prize of a million dollars, and maybe get a cushy job offer for being so smart. If you prove they are the same, I would expect the NSA to be willing to pay quite a lot more for you to be silent about your discovery, and instead hand over your papers to their mathematicians.

If you are very interested in the topic of quantum computing and encryption, I highly recommend reading up on the different complexity classes such as P and NP. They're worth your time.

Improve this answer
10
  • "It's never over." - What about quantum key distribution?
    – Kevin
    Commented Mar 6, 2016 at 4:38
  • 20
    While Shor's algorithm(s) don't affect AES, Grover's algorithm certainly does. This can however be mitigated by using AES-256 instead of AES-128.
    – SEJPM
    Commented Mar 6, 2016 at 10:53
  • 6
    The tl:dr for the above is: We think Quantum computation will halve the effective keylength of AES and other symmetric algorithms. So double your AES keylength, and you are good to go. (AES-256 is probably good enough unless you need to protect high value assets for decades.) On the other hand, quantum computation completely screws RSA and Elliptic curve asymmetric algorithms. There are other algorithms that we think are OK, but we aren't sure (yet). Get ready for much bigger keys in future.
    – Martin Bonner supports Monica
    Commented Mar 7, 2016 at 9:36
  • 2
    If you have a practical P algorithm for a problem in NP, the implications are much larger than "cryptography breaks". Any proof you can write down becomes easy to find. Any proof. Most of logic collapses into tautology (anything problem whose solution we can possibly understand) and inaccessible problems (problems whose solutions are so complex we cannot understand them). This includes constructive proof, so it covers questions like "is there an algorithm so solve X?": any algorithm that can be shown correct becomes easy to discover. NSA isn't rich enough.
    – Yakk
    Commented Mar 7, 2016 at 21:40
  • 1
    @Yakk Point the first please show that "most of logic" has relatively short proofs. Point the second, it's meaningless to talk about complexity of a single problem. The fact that X has a short proof does not mean that every problem in the language has a short proof. What you can say is that if every member X of a language L has a witness W that can be verified in time polynomial to the length of W, and W has length bounded by some function f(X) from the length of X, then P=NP implies that deciding L is in O(f(X)*p(X)) with polynomial p. Note that e.g. first order logic has no such f.
    – Taemyr
    Commented Mar 8, 2016 at 11:06
13

It's not impossible to crack any of those algorithms. The problem is not whether you can brute force AES or not, it's about how much time it would take and whether if it is feasible or not.

If you want to crack AES with brute force using normal computers, it would take you to search 2^128 keys which will require minimum 2^128 operations.

On the other hand, using quantum computer and search algorithm such as Grover's algorithm you will be able to go through the same number of keys in (2^128)^0.5 operations.

Improve this answer
28
  • 3
    As far as i know , when you are calculating the complexity of an algorithm, you measure it in terms of number of operations you will have to do and the input's size. not the computation power. and in cryptography it's usually said that the key is secure if it takes more that 2^90 operations to break it . Now trying to break 128 bit AES with the mentioned above algorithm will require the number which you got from your calculations . Which if you tried to convert to 2^x form, you will find that it's smaller that 2^90 (you can tell that by subtracting the number you got from 2^90)
    – HSN
    Commented Mar 6, 2016 at 1:11
  • 2
    (2^128)^0.5 = 2^64 which is close to DES' key size (2^56) so it's not secure. Now how much time do you need ? it's really hard to answer that question since there are many variables . Your computation power , the program which you are using to brute force , the platform which you're using, the language which you wrote your password cracker with . And here we are not taking into account whether you will be designing your cracker to be software based or hardware based . however, take into account that DES with 56 bits key size got broken in around 22 hours in 1999 !!!
    – HSN
    Commented Mar 6, 2016 at 1:27
  • 5
    @BuvinJ (2^128)^0.5 and 2^(128^0.5) are very different numbers.
    – hobbs
    Commented Mar 6, 2016 at 7:44
  • 1
    @Jason C It made sense when I first asked. Now, that irony is growing ever more apparent!
    – BuvinJ
    Commented Mar 7, 2016 at 3:42
  • 2
    @aroth You are wrong abount AES-128. 2^128 would require 72 more moore's law iterations then 2^56, unless you're counting quantum computer among the modern hardware already.
    – Cthulhu
    Commented Mar 7, 2016 at 9:02
-2

One has to note here that quantum computers can be used to implement security protocols that are much better than what can be done using only classical computing. So, the real problem is at its root that the more advanced technology (in case of this question this is the hypothetical case of quantum computing becoming available) is not available to everyone.

Improve this answer
3
  • Well real quantum computers that can maintain the type of quantum coherence to factor large integers or do discrete logs over finite fields (incl elliptic curves) aren't available to anyone (unless secret unpublished quantum computing research has made huge advances -- talking decades -- ahead of published research).
    – dr jimbob
    Commented Mar 6, 2016 at 21:02
  • 4
    Sorry, I have to downvote this. A) Apart from Quantum Key Distribution, I'm not aware of any proposed quantum security protocols - can you include some links in your answer? and B) Large-scale quantum computers are estimated to cost $1 billion USD, and to require a dedicated nuclear power plant, so the real real problem is that not everyone has $1 billion USD to spend on encryption, and a nuclear plant in their backyard.
    – Mike Ounsworth
    Commented Mar 10, 2016 at 18:10
  • 3
    @MikeOunsworth Even QKD isn't related to "quantum computers", since it doesn't require quantum computation, just the properties of quantum physics (entanglement, etc). No need to even have a single qubit.
    – forest
    Commented Apr 8, 2018 at 22:38
-2

No. AES is considered Post-Quantum Cryptography that will not be rendered obsolete by Quantum Computing (QC resistant).

It might be helpful to consider encryption strength inversely proportional to computing strength.

Encryption strength is classically measured by key length. Exponential increases in encryption strength are achieved by doubling key length. For example, AES-256 is exponentially stronger than AES-128.

The current understanding is that QC could represent an exponential increase in computing strength over classical computing. This would cut classical encryption strength by half.

So, strong encryption would require double key length to neutralize QC computing strength.

This would be the worst case scenario. If QC strength is only sub-exponentially stronger, lesser increases in key length would sufficient to neutralize any advantage.

The minimum recommended key length for strong encryption should then increase from 90 to 180 bits.

RESULT: At worst, AES-256 would be reduced from ludicrously strong to ridiculously strong, and AES-128 would no longer be considered strong.

Keep in mind this staggering result is only achieved by comparing room temperature classical computing (CC) strength to supercooled QC strength.

Supercooling CC devices also increases computing strength. Superconductive QC devices already operate at near-zero Kelvin, the critical limit of increasing computing strength by physical means.


enter image description here

Also CC inherently supports a high degree of scalability via parallelism, whereas extant QC only supports constrained parallelism at best.

Improve this answer
8
  • how is this different from the accepted answer? you appear to be saying the same thing?
    – schroeder ♦
    Commented Jul 23, 2017 at 21:32
  • The accepted answer does not definitively answer the question, but rather merely invites speculation, and offers no conclusions. It is really just another question, and I have answered both.
    – Birkensox
    Commented Jul 23, 2017 at 22:02
  • 2
    You say: The current understanding is that QC can make classical ciphers run exponentially faster. But that is really only the understanding among laymen. In case of the best known algorithms for factoring the quantum algorithm is exponentially faster than the classical algorithm. But for many other classes of problems you only get a quadratic speedup. And that's a huge difference. Quadratic speedup in breaking crypto means we need to make it ever so slightly stronger. Exponential speedup would mean the end of crypto as we know it.
    – kasperd
    Commented Jul 23, 2017 at 22:30
  • I stand by my claim that doubling key length increases encryption strength exponentially and so neutralizes any exponential increase in computing strength. So, I must say your statement about the "end of crypto" seems mere sophistry for laymen. My answer covers the worst case of an exponential speed up, which covers quadratic speed ups. BTW I think you meant to say superpolynomial, also covered.
    – Birkensox
    Commented Jul 24, 2017 at 0:49
  • If brute-forcing a key with classical computers requires searching through N possible keys O(N) work, then with Grover's algorithm it takes O(sqrt(N)) work. This is a quadratic speedup. An exponential speedup would be something like going from O(N) to O(lg N) or going from O(2^x) to O(x). Also, it's annoying when you delete your answer with critical comments, only to then repost the same answer seconds later. This is the fourth time, you've posted this identical answer; you can edit your answers -- editing is preferred as it leaves the edit and comment history.
    – dr jimbob
    Commented Jul 24, 2017 at 15:06

You must log in to answer this question.

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