> What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2^128 of matching any particular user key, but the attack ends up merging costs across a batch of 2^40 user keys, amplifying the effectiveness of each guess by a factor 2^40

If the attacker has collected 2^40 instances of some known plaintext, such as "GET / HTTP/1.1\r\n", encrypted under 2^40 unknown AES-128 keys (and it doesn't matter how those keys were generated), then the attacker can generate a key randomly, encrypt the known plaintext under that key, and see if it matches any of the target ciphertexts. The chance of guessing one of the 2^40 keys successfully this way is 1/2^(128-40) = 1/2^88. This means that attacking one of the keys requires far less than the 2^128 operations that one might expect would be required to attack AES-128. DJB argues that this makes AES-128 ill-matched with elliptic curves that provide a 128-bit security level, thus motivating a cipher with 256 bit keys instead, such as AES-256 or ChaCha20.

In practice, the first 32 bits of the GCM nonce used by TLS are derived during the handshake, so the attacker has to do 2^32 more computations (since there are 2^32 different ways a known plaintext could be encrypted with a given key). So perhaps AES-128 is actually fine with TLS. But the point still stands that there is a justification for preferring AES-256 over AES-128.

The point there is that batching helps the attacker finding the first AES key by a factor of m, m being the number of keys being attacked, but it doesn't really help finding the first ECC key---although it does help with the cost of finding the second, third, etc a bit. So for example, the effective multi-key security of AES-128, given 2^32 different keys (read: sessions), is 2^96.

See for example [1] for a formalization of multi-key security in the symmetric encryption setting.

[1] https://eprint.iacr.org/2015/101