2
$\begingroup$

It's hard to say exact QC specs, but let's assume we have decent a quantum computer using Grover's algorithm that is able to half AES-128 keyspace to that of AES-64.

How long will a bruteforce attack take on a AES-64 protected key? What about AES-128 or AES-256? Also, would we be able to increase to AES-512 and still maintain the same level of security?

Since the keyspace is halved, does it also introduce any other possible vulnerabilities to attack vectors (in addition to any attacks that can be done on a QC)?

$\endgroup$
  • 5
    $\begingroup$ AES-64 is not well defined. The standard does not describe an AES version with a 64-bit key. In the best possible world, the brute force attack will take $2^{63}$ decryption test to find out the key. And this is far below the minimum security level required as today. I do not know how the Grover's algorithm couple with other attacks, but we can imagine that you should take the best known present attack and halve the complexity. $\endgroup$ – ddddavidee May 9 '16 at 7:19
  • 1
    $\begingroup$ Does this answer your question? $\endgroup$ – otus May 9 '16 at 9:18
  • 3
    $\begingroup$ Also, see arxiv.org/pdf/1512.04965.pdf for an argument that breaking AES-128 with a Quantum Computer is a lot harder than breaking a 64 bit cipher with a conventional one; both are technically $O(2^{64})$, however in the Quantum case, the $O$ notation conceals a rather large constant... $\endgroup$ – poncho May 9 '16 at 17:05
1
$\begingroup$

The main complexity of attacks using a quantum computer with Grover's attack is explained here. I'll use the remainder of the answer to indicate some possible misconceptions in your question.

It's hard to say exact QC specs, but let's assume we have decent a quantum computer using Grover's algorithm that is able to half AES-128 keyspace to that of AES-64.

Quantum computing won't change the dynamics of the cipher itself. Although the complexity of the attack may be altered, it won't magically change AES-128 into AES-64.

How long will a bruteforce attack take on a AES-64 protected key? What about AES-128 or AES-256? Also, would we be able to increase to AES-512 and still maintain the same level of security?

Neither AES-64 or AES-512 is well defined. With AES the number of rounds and the key schedule are both dependent on the key size. It's therefore wrong to even talk about AES-64 and AES-512 as you wouldn't know the number of rounds or key schedule, and the security of a cipher depends on those parameters.

Since the keyspace is halved, does it also introduce any other possible vulnerabilities to attack vectors (in addition to any attacks that can be done on a QC)?

I don't see how it would be able to do that. This would only be the case if additional attack vectors or a better understanding is retrieved from a GC attack. That doesn't seem all too likely.


AES-256 is considered safe against quantum computing attacks; a security margin of 128 bits is considered unbreakable. So there is not much need for AES-512 as currently foreseen.

In general - especially for symmetric algorithms - an increase of key size, block size, internal state and/or output size does seem to satisfy most crypt-analists with regards to attacks based on quantum computing. Instead of just increasing the key size it would probably be wise to use a larger block size and internal state as well (you could use one of the SHA-3 finalists such as Keccak/Keyak or Skein/Threefish as base).

$\endgroup$

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.