27
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • 10
    $\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$ – CodesInChaos Mar 16 '13 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 '13 at 15:39
  • 9
    $\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$ – CodesInChaos Mar 16 '13 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$ – Paŭlo Ebermann Mar 16 '13 at 16:00
  • 4
    $\begingroup$ $2^{64}$ vs $2^{128}$ is not two times faster. $2^{128} = 2^{64} \times 2^{64}$ $\endgroup$ – pabouk Oct 12 '13 at 12:14
22
$\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.

| improve this answer | |
$\endgroup$
  • 16
    $\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$ – Matt Nordhoff Mar 16 '15 at 5:06
  • 1
    $\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 '15 at 8:38
  • 8
    $\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$ – Matt Nordhoff Apr 3 '15 at 9:02
  • 2
    $\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 '18 at 12:00
  • $\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 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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