34

Assuming quantum computing continues to improve and continues to perform like this:

... quantum computer completes 2.5-billion-year task in minutes

is it reasonable to expect that 256 bit encryption will be possible to brute force at some point in the future, and if so, what estimates (preferably from large tech companies, security companies, academics, or government organisations) are available as to when that may start to occur?

Notes

  • Obviously estimates would be extremely difficult to make, and probably depend heavily on a few key assumptions (and even then it could happen much earlier or much later than predicted), but despite the difficulty of such predictions, some rules of thumb (e.g. Moore's Law) have performed reasonably well given the difficulty of such predictions.

  • Since the US Government considers 256 bit encryption safe enough to not be broken (by any one outside the US) for a time scale long enough to protect US security interests (last paragraph), we can assume it's a fairly long way away.

Background:

stevec
  • 1,214
  • 1
  • 7
  • 16
  • 3
    I'd like to add that today no key is being brute forced anymore, they are being cracked by weaknesses in their implementations, other attacks(i.e. birthday attack) or by other means like social engineering(i.e. phising). Cannot be brute forced for another 200 years != safe today. – Chrᴉz remembers Monica Dec 11 '20 at 15:18
  • 9
    Just a caveat regarding your quote “quantum computer completes 2.5-billion-year task in minutes”. It doesn’t mean that a quantum computer can speed up *any* computation that much, or even *most* computations — we don’t expect that at all, even in theory. What it means is that there are *certain kinds* of problems which are much better suited to quantum than classical computing, where we can expect this kind of massive speedup. There are a lot more problems (like cracking crypto) where we expect some speedup, but not nearly as much as this. – PLL Dec 12 '20 at 09:12
  • Since you said *brute-forced*, there's a simple hard answer of "never". The definition of brute force is trying each key value, and 2^256 is far too large to do that. As the answers note, if you have additional structure so you don't have to brute-force, then it's more complicated but the answer is still "probably never". – R.. GitHub STOP HELPING ICE Dec 12 '20 at 22:10
  • 4
    @PLL : indeed. I would guess that if we carefully designed a problem to be difficult for a quantum computer and easy for a classical one, we could come up with a headline like *"quantum computer solves one-minute problem in six months"* – vsz Dec 13 '20 at 10:39
  • My bet is we get quantum computers right after fusion power. – Dmitry Grigoryev Dec 14 '20 at 12:31
  • 1
    Related: 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. See answer by ir01. – mti2935 Jan 10 '21 at 14:56

2 Answers2

52

Most Probably Never

Of the currently known quantum algorithms, Grover's algorithm is the one which directly affects symmetric ciphers the most. Essentially, for a cipher that a classical computer can bruteforce in time N, a quantum computer can bruteforce it in time square root of N. This means that a 256 bit cipher (which would take at most O(2256) compexity to bruteforce on a classical computer) could be bruteforced in O(2128) on a quantum computer.

Bruteforcing even a 128 bit key is limited by the laws of physics. As this excellent answer explains, the amount of energy required to bruteforce a 128 bit key is ridiculously large (all the world's resources for 10 years straight, just for cracking one key). So, absent any other significant breakthroughs, bruteforcing a 256 bit key is out of question. In fact, Grover's algorithm has been shown to be optimal, so any further breakthroughs are extremely unlikely.

nobody
  • 11,251
  • 1
  • 41
  • 60
  • 5
    It should be added that, since 256-bit symmetric ciphers will most likely never be broken by brute force anyways (at least with our current understanding of physics), there is also no demand for 512-bit or even 1024-bit ciphers. –  Dec 11 '20 at 13:21
  • 2
    I am not so sure, where this square root is coming from. The calculating capacity of the quantum computers is roughly equivalent to the exponent of their qbit size. That makes log, and not square, likely. – peterh Dec 11 '20 at 14:34
  • 10
    @peterh-ReinstateMonica the squareroot comes from the performance of Grover's algorithm (which allows a search over N^2 entries in O(N) time; given Oracle access to the cipher, Grover's is essentially (within a constant factor) of optimal; hence any Quantum algorithm that breaks the cipher faster than that must rely on the internal structure of the cipher. – poncho Dec 11 '20 at 15:12
  • 5
    @peterh-ReinstateMonica "Calculating capacity" is a fuzzy way to put it. A quantum computer with N qubits may require O(2^N) bits to classically represent its complete state. However, that doesn't mean it necessarily gets an exponential speedup in terms of useful computation. – David Dec 11 '20 at 15:47
  • I still want a 512 bit symmetric cipher, just for the sake of having it. – john doe Dec 11 '20 at 20:29
  • 3
    @johndoe See [Threefish](https://en.wikipedia.org/wiki/Threefish). It supports 256, 512 and even 1024 bit key sizes. – nobody Dec 11 '20 at 20:59
  • 2
    Note that the question did not specify symmetric encryption anywhere. The answer is very different for public key encryption, where Shor's algorithm is exponentially faster than classical algorithms – thegreatemu Dec 12 '20 at 00:07
  • It's somewhat obnoxious when analyses of stuff like this are based on modern physics/computation when discussing timespans of arbitrary length. Is there some widespread misconception that physics is essentially complete? – Nat Dec 12 '20 at 08:40
  • Actually, sorry if that was a tad negative. What I'd suggest is moving away from **"_Most Probably Never_"**, as claims about security against an attacker in 100 years from now, much less 1000 years from now, are absurd. – Nat Dec 12 '20 at 08:57
  • 2
    @Nat If I was assuming that physics is complete, I would have said a hard **Never**. Notice in my second last line I said, *"absent any other significant breakthroughs*. The thing is, given our current understanding of physics, it can't be broken no matter how efficient our computers become. If any new discoveries are made which overturn our fundamental understanding of physics, we will almost definitely have more than ample time to respond (just see how long we've been working on quantum computers, its been ~40 years and were still not really there) – nobody Dec 12 '20 at 09:11
  • @nobody: I appreciate that; your qualification was correct. What I meant to call attention to was the tone in the header and some of the lines that struck me as suggesting that a significant breakthrough was something of an alternative possibility rather than the almost-certain scenario, e.g. **"_any further breakthroughs are extremely unlikely_"**. That said, I agree that this probably isn't much of an issue for most modern use-cases, e.g. secure online messaging. – Nat Dec 12 '20 at 09:21
  • If cracking a 128-bit encryption would take `all the world's resources for 10 years straight, just for cracking one key`, then why do current best practices mandate 256-bit encryption? – obe Dec 12 '20 at 17:01
  • 1
    @obe Because quantum computers effectively reduce the security of a 128 bit symmetric cipher to that of a 64 bit cipher, and that of a 256 bit to a 128 bit cipher. A 128 bit cipher is perfectly secure against bruteforce today, but won't be once large quantum computers become practical – nobody Dec 12 '20 at 17:13
  • 2
    @obe Because that is 10 years straight when trying to BRUTE FORCE. Many known attacks on "broken" cyphers work by reducing the effective key strength. For example 40 bit CSS encryption had weaknesses that reduces the effectiveness to about 16bits, meaning that DVDs can easily be cracked by any PC capable of playing a DVD. Had they choosen a longer key length (illegal at the time), these attacks might still be infeasible to implement. – Aron Dec 13 '20 at 07:22
11

You did not explain the name of 256-bit encryption it can be AES, ChaCha20, RSA encryption, DLog, or...

Shor's algorithm

Peter Shor's algorithm will crush the RSA encryption if we assume that you meant the 256-bit key security for RSA is approximated as 15560-bit modulus, a table key be found at keylength.com where there are various approaches.

Shor's algorithm will also crush the DLog in ECC therefore, the ECDHE and ECC signatures like Ed25519 will be gone.

The below table from;

enter image description here

Grover's algrithm

Grover's algrithm search on the unstructured data is asymptotically optimal and has complexity Ω(√n). With AES-256 that will make √n . There is one interesting issue here and mostly not talked about; the setup and the running cost of the setup. Even the break of the AES-128 is not known to be practical with Grovers' method;

Grover's attack for AES-128 is in 264 time however that requires approximately 264 successive AES evaluations. This may not be achievable in a reasonable time. with a similar argument, we can talk about that AES-192 and AES-256 certainly not achievable.

The below table from;

enter image description here

One can run a k parallel Grover algorithm that will only speed up √k not k or quadratic, that is another difference from classical parallel search like done for DES.

Therefore we can say that Grover's attack is not a practical attack even to AES-128. The attack time is still quadratic and the required gates are not practical and it can be around 286 for AES-128.

As a result, we can say that Grover's algorithm assesses classical cryptographic schemes' security parameters against quantum attacks. There are more cryptographic scheme those have resistance to Quantum attacks and NIST already has Post Quantum Cryptography Project that is currently 3rd stage.

For AES-128 there are more practical attacks, like the multi-target attack and side-channel attacks that include the cache attacks.

If you want to be secure use AES-256!

kelalaka
  • 5,409
  • 4
  • 24
  • 47
  • 1
    +1 for the interesting bit of information that AES might require time 2^86. But about the part that 2^64 may not be achievable in reasonable time, are you sure that's also the case for state sponsored adversaries? – nobody Dec 11 '20 at 21:08
  • 1
    You may need to run the machine 2^64 times. It is not like a for-loop. The setup time and extracting the result, all must be count in. – kelalaka Dec 11 '20 at 21:12