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
- uniform randomly
- as result o a key exchange like DHKE then a cryptographic hash function is applied, or
- form a password with a password-based key derivation function like PBKDF2, Scrypt, and Argon2.
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.