Learn back-end development by writing real code

ยป Is AES-256 Quantum Resistant?

Is AES-256 Quantum Resistant?

By Lane Wagner on Sep 10, 2020

Curated backend podcasts, videos and articles. All free.

Want to improve your backend development skills? Subscribe to get a copy of The Boot.dev Beat in your inbox each month. It's a newsletter packed with the best content for new backend devs.

With quantum computers getting more powerful each year, many worry about the safety of modern encryption standards. As quantum computers improve in performance and the number of qubits used for calculations increases, current cryptosystems are under threat. AES-256 is one of the most powerful symmetric ciphers, but will it remain secure in a post-quantum world?

๐ What will break post-quantum?

Many asymmetric encryption algorithms have been mathematically proven to be broken by quantum computers using Shor’s algorithm. Shor’s algorithm solves the following problem:

Given an integer N, find its prime factors.

Because algorithms like RSA rely heavily on the fact that normal computers can’t find prime factors quickly, they have remained secure for years. With quantum computers breaking that assumption, then it may be time to find new standards.

The following are examples of encryption that Shor’s algorithm can break:

๐ Symmetric Encryption

Symmetric encryption, or more specifically AES-256, is believed to be quantum-resistant. That means that quantum computers are not expected to be able to reduce the attack time enough to be effective if the key sizes are large enough.

Grover’s algorithm can reduce the brute force attack time to its square root. So for AES-128 the attack time becomes reduced to 2^64 (not very secure), while AES-256 becomes reduced to 2^128 which is still considered very secure.

๐ A Caveat

It is important to remember that 256-bit keys derived from passwords actually can have less than 256-bits of entropy. If the owner of the key generated it from a weak password an attacker can try deriving keys from common passwords instead of trying random 256-bit numbers.

For example, instead of randomly trying

1. azpV4CYbAwQUP4BaJJJNDBxEUkghMF8x2Sd4Q7ihD04=
2. mtOXPNln432smP3pd3rVLw9rpGGkVsiqRhUFLXy/KBw=
3. ..

An attacker could try the following: