36

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:

Improve this question
6
  • 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, 2020 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, 2020 at 9: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, 2020 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, 2020 at 10:39
  • 1
    Related: crypto.stackexchange.com/questions/1145/…. See answer by ir01.
    – mti2935
    Jan 10, 2021 at 14:56

2 Answers 2

Reset to default
54

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 θ(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.

(While some kinds of 256 bit keys can be cracked using Shor's algorithm, I would consider that more of an attack on the algorithm rather than brain dead bruteforce.)

Improve this answer
14
  • 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.
    – user163495
    Dec 11, 2020 at 13:21
  • 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, 2020 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, 2020 at 15:47
  • 3
    @johndoe See Threefish. It supports 256, 512 and even 1024 bit key sizes.
    – nobody
    Dec 11, 2020 at 20:59
  • 3
    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, 2020 at 0:07
12

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!

Improve this answer
2
  • 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, 2020 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, 2020 at 21:12

You must log in to answer this question.

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