# Is AES-256 a post-quantum secure cipher or not?

We know Grover's algorithm speedup brute-force attacks two time 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?

-
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. – CodesInChaos Mar 16 '13 at 15:33
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. – CodesInChaos Mar 16 '13 at 15:43
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). – Paŭlo Ebermann Mar 16 '13 at 16:00
@CodesInChaos could you post your first comment as an answer? – Maarten Bodewes Mar 17 '13 at 15:26
$2^{64}$ vs $2^{128}$ is not two times faster. $2^{128} = 2^{64} \times 2^{64}$ – pabouk Oct 12 '13 at 12:14

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 a 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 medium term secure against a quantum attack, however AES-128 is broken, and AES-192 isn't looking too good.

With the advances in computational power (doubling every 18 months, etc.), no set keysize is safe indefinitely. The use of Grover is just a one of gigantic leap.

I would still class AES as quantum resistant so long as the best known attack is still some form of 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.

-
"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. – Matt Nordhoff Mar 16 at 5:06
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. – Richard Apr 3 at 8:38
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. – Matt Nordhoff Apr 3 at 9:02