DJB pointed out, correctly, that generic attacks against ciphers with 128-bit keys are distressingly close to being practical. Generic attacks against 256-bit ECDHE are wildly impractical. If you want to make it take comparable effort to break the key exchange as it takes to break the cipher, the cipher key needs to be bigger.
Can you give that a meaningful definition? I suspect you mean that it takes ~2^128 operations to break a single target ECDHE exchange. If so, that is both true and completely irrelevant to anything I said.
The key point here is that it does not take anywhere near 2^128 operations before you can decrypt a single AES-128 block out of a large corpus of captured ciphertexts. For that type of attack, 128 bit ciphers offer vastly less security than ECDHE on a 256-bit field.
If you're talking about batch attacks. They're a completely theoretical kind of attack, it does not apply to normal usages of AES. Sure, TLS makes it possible to theorize about them. Let me try:
Imagine that the NSA has collected 2^40 sessions using AES-128 on the internet. Let's imagine that they only want to steal session IDs being sent (if they want to eavesdrop on more data, it will be worse). From burp, I get that a simple GET request to Gmail is 2319 bytes, that's around 144 blocks of AES. Let's say a 100.
So in total, the NSA would have to store 2^40 * 128 * 100 bits, let's say around 2 petabytes.
Also I forgot, let's imagine that the first block of any of these sessions' first message is always the same thing. A GET request to the same address. We got extra lucky!
Now they have to perform 2^88 AES operations for each key guess, and hopefully they will start finding keys at this point. (It's more than all of the computing power of bitcoin btw.). And for each of these AES operations they also have to check in their 2 petabytes corpus for a match (I hope you way to do that).
Let's imagine that the NSA wants to do less computations of AES. They could have stored 2^50 sessions instead! And now they only have to perform 2^78 AES operations.
For this they would have to store around 2 exabytes. In 2010 the whole traffic of internet was estimated to be around 21 exabytes per month. So if the NSA would be to record sessions for a month, they would need to store 10% of the internet hopping that they would also be GET requests to Gmail.
Now we can theorize about the evolution of storage space, and computing power, and ... quantum computer. In which case ECDHE will fall before AES-128 does.
> From burp, I get that a simple GET request to Gmail is 2319 bytes, that's around 144 blocks of AES. Let's say a 100.
> So in total, the NSA would have to store 2^40 * 128 * 100 bits, let's say around 2 petabytes.
2 petabytes is no big deal for the NSA. Also, why would they store anywhere near this much per session? They can estimate which part of the stream matters and store that part if they want to.
> And for each of these AES operations they also have to check in their 2 petabytes corpus for a match (I hope you way to do that).
Bloom filter plus a large hash table?
The point is that crypto ought to be configured to be secure, with a large margin of error, against an adversary who controls the entire world's computational capacity and is willing to use highly theoretical attacks because achieving this level of security is not particularly difficult. AES-256 satisfies this criterion, as does ECDHE until a quantum computer shows up. AES-128 does not satisfy this criterion even though the existing attacks are barely practical even for a nation-state adversary.
256-bit keys may not even be quite good enough against a batch attack done with a quantum computer because a full Grover's algorithm run against the entire batch runs in ~sqrt(2^bits / batch size). If you assume a batch size of 2^96 (to give a nice margin of error) and you want a work factor of 2^128 for the adversary, that gives 352 bits.
ECDHE is, of course, completely dead once someone builds a quantum computer.
I think you're over estimating both the practicality of these attacks and the operations at the NSA. This just does not make sense to compute such an attack. Especially when they are other vulnerabilities, easier to find, and with much more efficient targeting. A debate about AES-128 vs AES-256 is useless when people are still using non-authenticated encryption, non cryptographic PRNGs, etc...
Quantum does affect this, but obviously the implications of quantum are way bigger than your block cipher choice.