94

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?

Community
  • 1
BuvinJ
  • 1,003
  • 1
  • 8
  • 11
  • 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 Mar 06 '16 at 12:46
  • 1
    @Mok-KongShen, you err. Shor's algorithm cracks factoring in polynomial, as opposed to exponential, time. – user1717828 Mar 06 '16 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 Mar 06 '16 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 Mar 10 '16 at 17:53
  • It's rumored that quantum computers might be able to crack every AES encryption because it will be that good at finding prime numbers. But on the other hand it will allow for quantum cryptography which can be mathematically proven to be not crackable (because it utilizes one time keypad encryption). Bit this is very new technology. We thought that nuclear might be magical and help us propel into a new magical world where clean energy is cheap, we can heal illnesses with it, everyone will be happy, ... it's not like that. It's not like it but it was hyped. Quantum comouters are hyped atm too – BlueWizard Apr 04 '16 at 14:29
  • 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 Jun 30 '16 at 13:34
  • @dchest haha, whoops – BlueWizard Jul 01 '16 at 13:43

4 Answers4

115

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.

Cort Ammon
  • 9,216
  • 3
  • 26
  • 26
  • "It's never over." - What about quantum key distribution? – Kevin Mar 06 '16 at 04: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 Mar 06 '16 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 Mar 07 '16 at 09: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 Mar 07 '16 at 21:40
  • It's worth pointing out something often ignored in these kind of commentaries. P does not necessarily mean effectively solvable. It's better than exponential, eventually, but we only adopted it because it's mathematically convenient. If your best algorithm solves the problem in $n^100$ time, that's worse in practice than the exponential functions given above (say, for n<1000 or so) and far from practically solvable. – Richard Rast Mar 08 '16 at 03:43
  • @RichardRast Very good point. One of the outstanding questions is whether it is possible that all of the NP-complete problems just require a very large polynomial time to solve. However, the distinction is profound because we very often find ways to half or quarter state spaces with cryptography. For a function that takes exponential time, that's a minor weakening of one or two bits of data. For a polynomial, that can very rapidly demolish complexity. It doesn't mean those expensive P problems can be solved quickly, but it suggests they might. – Cort Ammon Mar 08 '16 at 05:28
  • @Yakk That's simply not true. Most of logic is not in NP. If P=NP then NEXPTIME=EXPTIME, but that's still exponential time, and the decision algorithm could be exponentially harder than writing the proof. You could say that finding a proof is in the same complexity class as writing the proof. - But you would be wrong, because P=NP does not imply RE=R. – Taemyr Mar 08 '16 at 09:14
  • @Taemyr Let X be a possibly true statement. If there is a relatively short proof of X that can be efficiently checked, then the truth-value of X is *in NP*. Basically, P=NP basically states that any reasonably short proof of any statement can be found almost as easily as checked. – Yakk Mar 08 '16 at 09:25
  • 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 Mar 08 '16 at 11:06
  • @taemyr "does this theorem have a proof less than 10^6*|theorem|^2 in size" is a problem in NP (the witness is the proof, we just have to check it). The polynomial used is arbitrary: as big or small as you want, they are all in NP. An efficient P=NP lets you find any short proof of any theorem, bounded by the efficiency of the P time NP algorithm. – Yakk Mar 08 '16 at 11:19
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.

Zanon
  • 109
  • 1
  • 8
HSN
  • 968
  • 5
  • 14
  • Out of curiosity, I computed how many operations 2^(128^0.5) is and got: 18,446,744,073,709,551,616. – BuvinJ Mar 06 '16 at 00:53
  • How can we estimate the time it would take to perform that many operations? (I'm not sure what kind of processing power we assume...) – BuvinJ Mar 06 '16 at 00:55
  • 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 Mar 06 '16 at 01:11
  • 2^90 = 1,237,940,039,285,380,274,899,124,224 – BuvinJ Mar 06 '16 at 01:16
  • 2^90 - 2^(128^0.5) = 1,237,940,020,838,636,201,189,572,608 – BuvinJ Mar 06 '16 at 01:18
  • So that's smaller to the extreme! Still I wonder how long it takes to use brute force with Gover's. Are we talking weeks? (Am I way off?)... – BuvinJ Mar 06 '16 at 01:21
  • 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 Mar 06 '16 at 01:27
  • Thank, HSN. I realized my question was vague, which is why I asked how we could even estimate what this many computations means in practical terms. Your anecdote about DES is very helpful! – BuvinJ Mar 06 '16 at 01:45
  • 5
    @BuvinJ (2^128)^0.5 and 2^(128^0.5) are very different numbers. – hobbs Mar 06 '16 at 07:44
  • Sorry. I wrote that comment incorrectly. The figure was correct though. 2^64 (the equivalent) = 18,446,744,073,709,551,616 – BuvinJ Mar 06 '16 at 14:31
  • *it would take you to search 2^128 keys which will require minimum 2^128 operations* -- no, it requires *at most* 2^128 operations. For a lucky enough user, a brute force algorithm can guess a key with just one try – Andrea Corbellini Mar 06 '16 at 17:14
  • @AndreaCorbellini I believe we call that "a person who has the key", i.e. the scheme has already been broken by social engineering or other non-cryptographic attacks. – Mario Carneiro Mar 06 '16 at 22:04
  • @Mario Carneiro No, the key can be anywhere in the space of 2^128 keys. It's unlikely that the correct key is the last key that would be checked. Therefore, the search takes *at most* 2^128 operations. – Millie Smith Mar 06 '16 at 22:34
  • @MillieSmith I know. My point is that anyone who claims to have "gotten lucky" by guessing the key on the first try is lying. (Unless there are many many independent attempts, such as in the lottery; that doesn't apply here because there aren't enough people in the world.) Practically speaking, I wouldn't trust anyone who guesses the answer with less than O(n^(1/2)) guesses of an O(n) brute-force search. – Mario Carneiro Mar 06 '16 at 22:48
  • I was hoping for a time estimate loosely based on the maximum number of iterations. As in, a qc could break such an encryption within X amount of time in a worse case scenario. I just want to know if we are on practical scales, or even human scales. In my original question, I provided a link from the thread that inspired this one, which detailed how impractical cracking AES was with traditional computers based on time, the amount of energy required, etc... It seems the qc may provide a real world solution. – BuvinJ Mar 07 '16 at 00:03
  • 22 hours for 2^56 works out to approximately 235 days for 2^64, on 1999 hardware. Factor in the ~8 iterations of Moore's Law that have occurred since then and you're basically back to where you started. If those numbers really do hold, 128-bit AES is already worthless even without quantum computing. – aroth Mar 07 '16 at 02:07
  • @BuvinJ Check out http://security.stackexchange.com/questions/116566/use-multiple-computers-for-faster-brute-force, as well as https://www.reddit.com/r/theydidthemath/comments/1x50xl/time_and_energy_required_to_bruteforce_a_aes256/. – Jason C Mar 07 '16 at 02:40
  • Thanks, @Jason C. Unfortunately, everyone is doing the 2^256 time and energy needs. I was wondering how much smaller the 2^128 or 2^64 figures would work out to, to see if qc helps. I could plug in these smaller figures to their math, but my own time and energy constraints lead me to just ask instead! – BuvinJ Mar 07 '16 at 03:27
  • Interesting point @aroth. Not to go off on a tangent, but has Moore's "law" actually held true in that time span? I don't think it has for house hold PCs. – BuvinJ Mar 07 '16 at 03:30
  • @BuvinJ The irony is, it would've been faster and easier for you to just do some quick math than type all your questions about it here. You know, you can type math expressions directly into the Google search box to get the results, e.g. [that reddit post](http://bit.ly/1LKOH9L). – Jason C Mar 07 '16 at 03:34
  • @BuvinJ - You're right, it has slowed a bit (though hasn't stopped yet). If you check the release dates on Intel's consumer-level processors (including Xeon models), in 1999 their largest chip had 28 million transistors. In 2015 it was 5.8 billion transistors. That's an increase of ~200x, or more than 7 (but not quite 8) iterations of Moore's law. So it would appear that you are indeed looking at needing only 1-2 days on modern hardware to break 128-bit AES. – aroth Mar 07 '16 at 03:40
  • 1
    @Jason C It made sense when I first asked. Now, that irony is growing ever more apparent! – BuvinJ Mar 07 '16 at 03:42
  • @aroth Thanks for figures. I guess the bottom line shows that 128 AES is not too powerful now. And it seems that means 256-bit AES could be cracked within 2 days if we have qc involved? – BuvinJ Mar 07 '16 at 03:46
  • @BuvinJ Don't know about that. I think the impact of QC was less in terms of 'it's faster than traditional computing by a factor of X across the board' and more in terms of 'the time complexity of some QC algorithms is orders of magnitude less than the time complexity of an equivalent traditional computing algorithm'? If so, cracking 256-bit AES would come down more to whether or not there are good QC algorithms available for attacking AES in general than it does to how well AES is holding up against traditional brute-force attacks. – aroth Mar 07 '16 at 03:52
  • 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 Mar 07 '16 at 09:02
  • @Cthulhu - Yes, I was counting using Grover's algorithm, which I didn't originally notice was a QC-only algorithm. – aroth Mar 07 '16 at 09:06
  • Compare [Amount of simple operations that is safely out of reach for all humanity?](http://security.stackexchange.com/q/6141/2138) – user Mar 07 '16 at 09:22
  • AES-256 is AES-128 in quantum computing. [AES-512](https://crypto.stackexchange.com/questions/20253/why-we-cant-implement-aes-512-key-size) does not exist yet. – Dominic Cerisano Jul 20 '17 at 20:17
-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.

Count Iblis
  • 228
  • 1
  • 5
  • 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 Mar 06 '16 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 Mar 10 '16 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 Apr 08 '18 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.

Dominic Cerisano
  • 115
  • 3
  • how is this different from the accepted answer? you appear to be saying the same thing? – schroeder Jul 23 '17 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. – Dominic Cerisano Jul 23 '17 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 Jul 23 '17 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. – Dominic Cerisano Jul 24 '17 at 00: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 Jul 24 '17 at 15:06
  • Sub exponential increases in computing strength are easily met with minor increases to key length. The increased QC strength is fundamentally derived from superconductivity, already at zero resistance. Also, not the same answer, and this is the fourth time I have had to say it, which is annoying. My earlier answers involved information security professionals being relocated to the far side of the moon, and were not well received. – Dominic Cerisano Aug 07 '17 at 23:00
  • Downvote because this answer seems predicated on the layman's view that QCs run the same algorithms as CCs, but faster. In reality, quantum algorithms to attack block ciphers (ex. Grover's) are fundamentally different from classical attack algorithms (ex. Sweet32). The exponential speedup comes from the algorithm taking advantage of quantum mechanical effects not present in CCs, not because a QC is "faster". This answer is perpetuating misconceptions about quantum computers. – Mike Ounsworth Jul 30 '18 at 20:39
  • Calling 'bullshit' is not an argument. You obviously did not read the supporting references to my answer. Don't be lazy. – Dominic Cerisano Jul 30 '18 at 21:26