Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 8 down vote accepted

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}$.

share|improve this answer
They can claim only birthday bound security in terms of number/length of queries to the oracle. But how about in terms of time complexity? i.e. if exhaustive search were the fastest attack we could say an attacker spending at most $t$ time could only distinguish AES from a random permutation with advantage $\epsilon = 2^{t-128}$. Are you saying the PRP security of AES is approx. $2^{t-127}$? – J.D. Nov 6 '13 at 21:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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