Why is 128-bit AES Insecure for a Quantum Computer, But 256-bit Is Not?

Why is 128-bit AES Insecure for a Quantum Computer, But 256-bit Is Not?

If I have an unsorted database with 10 billion words, and I want to search for one of the words. With a normal search, it would take an average of 5,000,000,000 tries to find (half the space). But with a quantum computer using Grover’s algorithm [1, 2], we will only need 100,000 searches on average — and which is the square root of the number of search terms:

This is a core reason that search engine companies, such as Google, would love to build a quantum computer. The other reason is to crack cryptography. While you should know that all of our public key encryption methods will be cracked using Shor’s method [3], what about symmetric key encryption?

Cracking 128-bit keys with brute force

Now, let’s apply to symmetric key encryption. If we have a 128-bit key, we have 2¹²⁸ encryption different keys. If we test for the key strength (entropy), we will get:

>>> math.log10(2**128/2)/math.log10(2)
127.0

In this way, we have a 127-bit strength. At the current time, all of the Bitcoin miners in World would be able to crack around 70 bits, so we have a large leeway in brute forcing 128-bit AES.

But what effect will a quantum computer have on cracking 128-bit symmetric encryption?? Well, if we have a 128-bit key, the number of possible keys are:

115792089237316195423570985008687907853269984665640564039457584007913129639936

and which is 2¹²⁸. If we now have to search for 2¹²⁸ with Grover’s method, the number of searches for the key will be:

>>> math.sqrt(2**128)
9.223372036854776e+18

So, what is the equivalent key size? For this, we can compute from the square root of 2¹²⁸ to find:

>>> math.log10(math.sqrt(2**128))/math.log10(2)
64.0

This means that the equivalent key size for a 128-bit key is only 64 bits, and which is well below a 72-bit limit that is at the limits of cracking.

Cracking 256-bit keys with brute force

If we now try a 256-bit key we get:

>>> math.log10(math.sqrt(2**256))/math.log10(2)
128.0

And, so, 128-bit AES and ChaCha20 is at risk, and where we must upgrade our encryption to 256 bits.

Conclusions

And, so, 128-bit AES and ChaCha20 encryption are both at risk, so now is the time to migrate your encryption to 256-bit.

References

[1] Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212–219).

[2] Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical review letters, 79(2), 325.

[3] Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124–134). Ieee.