40
$\begingroup$

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?

$\endgroup$
7
  • 12
    $\begingroup$ Calling a related key attack on AES "practical" isn't really true. The way AES is supposed to be used is with a random key. So this attack can't be used against any "normal" AES use. $\endgroup$ Mar 16, 2013 at 15:33
  • $\begingroup$ @CodesInChaos the attack claim is practical. as we only use random keys in real life so if some attack don't break random keys then we can't call it an attack. $\endgroup$
    – AES256
    Mar 16, 2013 at 15:39
  • 11
    $\begingroup$ The attack you link does not work when you use AES with a random key in a normal way. If you only need AES to be a pseudo-random-permutation (PRP), then it's no attack at all. AES was primarily designed as a PRP, resistance to related key attacks was only a secondary goal(if it was a goal at all). It is only an attack if you use AES in an unusual way where the attacker has control over the key. For example if you try building a hash function from AES, this attack might become an issue. $\endgroup$ Mar 16, 2013 at 15:43
  • 1
    $\begingroup$ Please note that this "practical attack" should not be classified as brute force ... since it is (in the cases where it applies) better than brute force (simple key search). $\endgroup$ Mar 16, 2013 at 16:00
  • 12
    $\begingroup$ $2^{64}$ vs $2^{128}$ is not two times faster. $2^{128} = 2^{64} \times 2^{64}$ $\endgroup$ Oct 12, 2013 at 12:14

2 Answers 2

36
$\begingroup$

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.

$\endgroup$
6
  • 26
    $\begingroup$ "no set keysize is safe indefinitely" Yes, some key sizes are. I don't see anyone building a quantum computer the size of Jupiter or a classical computer larger than the universe any time soon. $\endgroup$ Mar 16, 2015 at 5:06
  • 3
    $\begingroup$ Similarly, I don't see anyone building a computer capable of storing and using a key that would require such a large computer to crack any time soon. $\endgroup$
    – Richard
    Apr 3, 2015 at 8:38
  • 11
    $\begingroup$ I was referring to 256 bit keys, though I was also using total WAGs, and I misstated the issue: it's more about energy available for computation than physical size. $\endgroup$ Apr 3, 2015 at 9:02
  • 4
    $\begingroup$ Lets bring AES-256 down to a level where brute forcing is possible, e.g. lets assume we can break $2^{80}$ strength keys. Then we only have 1724057483474124965653140405544097831571081512456552448 months to wait until we have sufficient computer power. Even the fountain of youth will be destroyed by that time. $\endgroup$
    – Maarten Bodewes
    Feb 28, 2018 at 12:00
  • 1
    $\begingroup$ @Richard: a 640-bit symmetric key would be pointless, but entirely practical. A quantum computer the size of the universe won't be able to find it from plaintext/ciphertext pairs by any known method; absent a break of the encryption algorithm. $\endgroup$
    – fgrieu
    Jan 20, 2020 at 13:30
12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.