Are there limits (or, what are the limits) to our understanding of AES's resistance to known plaintext attacks?

Question

Let's assume the same message is encrypted many times, each time with a different IV but the same key. Do we reach a point where just knowing what that message is gives us a plausible attack by which we can discover the key?

The closest thing I see to this is a side channel attack mentioned on the Wikipedia page requiring over 200 million chosen plaintexts, and presumably side-channels can be closed as they are discovered, negating this particular weakness.

Aside from that, it seems that it might be unwise to re-encode the same message many times, if a weakness were to be found then such a scenario might be the first to be exploited, but I was just wondering if there was anything we were currently aware of along those lines.

Answer 1

A perfect block cipher is modeled as a pseudorandom permutation. For blocks of n bits, there are 2ⁿ! possible permutations; a perfect block cipher is as if the key was a random uniform selection of one permutation among all these. For a PRP, knowing many plaintext/ciphertext pairs (m, E(m)) gives you exactly zero information on the encryption of blocks m' which are not part of the known pairs.

Right now, the best attack we know which may distinguish AES from a PRP is the so-called biclique attack, which has a cost only very slightly lower than basic brute force on the key (cost is theoretically about 2^126.1, compared to 2¹²⁷ for brute force -- needless to say, the attack cannot be actually tried with existing technology, so we are not absolutely sure that it works as advertised, though that is plausible).

Assuming that AES is indeed as good a PRP as we can get, usual encryption modes can be shown to be "secure" as long as you haven't processed more than 2⁶⁴ blocks with the same key. That's the point where, statistically, the PRP begins to be differentiated from a PRF. It translates to about 300 millions of terabytes, which is kind of large. AES has been defined to use 128-bit blocks, and not 64-bit blocks like 3DES, precisely so that we do not run into that kind of problem.

To sum up: in practice, you don't have to fear reusing the same key again and again, as long as you do it correctly (e.g. CBC mode requires random uniform unpredictable IV).