Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
We know Grover's algorithm speedup brute-force attacks two times faster in block ciphers (e.g brute-forcing 128-bit keys take $2^{64}$ operations, not $2^{128}$).
That explains why we are using 256-bit keys to encrypt top secrets. But latest practical attack on AES shows brute-forcing AES-256 take $2^{100}$ operations.
Does this attack work with Grover's search to make AES cipher quantum unresistant?
Biclique cryptanalysis is the current best-known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks, as they should never occur in the wild. They are symptomatic of poor implementation and contrary to the recommended use of AES.
The best known theoretical attack is Grover's quantum search algorithm. As you pointed out, this allows us to search an unsorted database of $n$ entries in $\sqrt{n}$ operations. As such, AES-256 is secure for a medium-term against a quantum attack, however, AES-128 can be broken, and AES-192 isn't looking that good.
With the advances in computational power (doubling every 18 months), and the development of quantum computers, no set keysize is safe indefinitely. The use of Grover is just one of the gigantic leaps.
I would still class AES as quantum resistant, so long as the best-known attack is still some form of an exhaustive search of the keyspace.
As for your question about using different attacks: Combining attacks rarely works as you need all of your attacks to reveal exclusive bits of the key. Given that the best attack on AES doesn't even reveal 2, you will be hard pushed to make a reasonable attack like this.
We know Grover's algorithm speedup brute-force attacks two times faster in block ciphers (e.g brute-forcing 128-bit keys take 264 operations, not $2^{128}$).
This is the advertisement of the Lov K. Grover's algorithm. Yes, it reduces the key search into $\mathcal{O}(\sqrt{2^n})$ instead of the $\mathcal{O}(2^n)$. What is generally not mentioned is the number of successive evaluations; it is $\mathcal{O}(\sqrt{2^n})$, too. What do we know about the successive calls? Almost nothing since nothing was built yet. We can only estimate it even with some good numbers like assuming that one can prepare-and-run the machine in one nanosecond. Then for AES-128, it will take $\approx 585$ years.
| AES-128 | AES-192 | AES-256 | |
|---|---|---|---|
| complexity | $2^{64}$ | $2^{96}$ | $2^{128}$ |
| approx-time | $\approx 583$ years | $\approx 583\cdot 2^{32}$ years | $\approx 583\cdot 2^{64}$ years |
Grover's algorithm can also be parallelized, the gain, however, is not quadratic as one expected. For running $k$ machine one gets $\sqrt{k}$ speed ups. Therefore if one runs $10^6$ Grover's machine in parallel they can break AES-128 for less than one year.
So as of current, it is not easy to call AES-128 is not quantum-safe. The practical problems that scientists and engineers are working on must be solved to break AES-128 in a meaningful time. In the end, we expect that it will be broken, actually, any block cipher with a 128-bit key is broken, there is nothing specific to AES.
On the other hand, AES-128 has other major problems than Grover's algorithm like multi-target, or small block size for proper random IV guarantees for GCM.
Is AES-256 a post-quantum secure cipher or not?
It is and it will be always secure. Therefore AES-256 is the golden standard in the industry with only 40% performance penalty when compared to AES-128. Always use AES-256 with a good mode of operation for your target security.
That explains why we are using 256-bit keys to encrypt top secrets. But latest practical attack on AES shows brute-forcing AES-256 take $2^{100}$ operations.
This attack is a related-key attack and not practical in the sense of what is done to RC4 with related-key attack.
This is also misleading since the attack requires $2^{99.5}$-time and $2^{99.5}$-data complexity. Though the collective Bitcoin Miners can reach $\approx 2^{93}$ SHA-256d in a year, they don't store the data. This is the major problem of the attack. Since we cannot store this amount in memory, we have to consider the bottleneck of the data access, too.
As a practice matter, one selects the AES key either
The attacker has no means to control the selected key. And, it will be very surprising that any of these can aid the related-key attacker. We can say this is not a key recovery attack.
As a side note: the designers of AES mentioned about related key attack on the second version of their book (2020) and they say that due to related-key attack AES is not a Hermetic Cipher, however, this is not a problem since AES is not going to be used in the hash designs.
