AES-CTR mode and the Biclique Attack

Question

The biclique attacks that break AES (Biclique Cryptanalysis of the full AES) appear to require decryption oracles to work, presumably because the key schedule of AES is weaker in the decryption direction, enabling better bicliques to be constructed starting from the ciphertext end. Which is to say, these attacks show that AES does not have 128 bits of security under the Chosen Ciphertext Attack (CCA) model.

But what about modes of operation that only require us to assume the underlying block cipher is a PRP rather than a SPRP, i.e. secure under the Chosen Plaintext Attack (CPA) model? For example, CTR mode. Does AES-128-CTR mode still have 128 bits of security not-withstanding the biclique attacks? Are there also biclique attacks on the full AES starting from the plaintext end?

Answer 1

I do not remember if we checked this explicitly, but my guess is that in the chosen-plaintext setting the biclique attack would still be faster than the exhaustive search, maybe by the factor of 2 compared with 4 in the chosen-ciphertext setting.

However, both results are pretty far from declaring AES broken in any sense. Such small gain over exhaustive search is admissible by virtually every mode of operation. For modes CBC, CTR, CFB, OFB the situation is even simpler: they claim 64-bit security only, because if the adversary is allowed to ask more than $2^{n/2}$ queries for $n$-bit blockcipher, various collision effects invalidate security proofs. Moreover, it becomes hard to state what sort of security should be provided beyond the birthday bound: should the cipher be indistinguishable from the random permutation or function, or the whole ciphertext (possibly gigabytes long) should have this property.

To summarize, the security claims of AES-CTR are not affected by biclique attacks at all, and probably will never be since the meet-in-the-middle attacks (which include bicliques) usually can not be faster than $2^{n/2}$.