After ECDH with Curve25519, is it pointless to use anything stronger than AES-128?

Question

Is the following reasoning correct:

After ECDH with Curve25519, the resulting shared secret will be an EC public key with a bit strength of 128 bits.

This public key would then be hashed (let's say with SHA-2-256) to produce a key of length 256 bits for use in symmetric encryption. This symmetric key would have a bit strength of slightly less than 128 bits (because the hash operation reduces the bit strength very slightly).

Therefore using AES-256 with this 256 bit hash as a symmetric key would be a waste of time, and the 256 bit hash should be truncated to 128 bits and AES-128 used for the purposes of symmetric encryption. AES-128 would be 40% faster than AES-256, and there would be no advantage to using AES-256 over AES-128.

Answer 1

The reasoning is wrong, because the scaling of attacks on AES is qualitatively different from the scaling of attacks on X25519.

A successful multi-target attack on a system using AES-128—that is, an attack that recovers one of many keys—can cost much less than $2^{128}$ evaluations of AES-128. Specifically, using Oechslin's rainbow tables, and on a machine parallelized $p \geq n^2$ ways, the expected cost of recovering the first of $n$ keys is $2^{128}/n$, the expected time is that of $2^{128}/np$ sequential evaluations of AES-128. The expected cost of breaking all of the $n$ keys is still close to $2^{128}$, but in a real network of users, compromising one of them may be enough to compromise many of them.

In contrast, a successful attack on X25519 is expected to cost at least about $2^{128}$ bit operations using the best known strategy, even if it is a multi-target attack. The expected cost of recovering all of $n$ keys is about $2^{128}\sqrt{n}$ bit operations, so there is an advantage to batch multi-target attacks, but the cost to recover the first one is still an insurmountable $2^{128}$ bit operations.

If you say that AES-128 has a ‘128-bit security level’, then you should consider X25519 to have a much higher security level. But I don't think that's reasonable. Rather, I think it is reasonable to say X25519 has a ‘128-bit security level’ and AES-128 has a much lower security level.

If you must use AES, then use AES-256 unless you have an overwhelming budgetary constraint preventing you from doing so. If you don't need to do economics, don't let the adversary do economics either.

Consider using the simpler faster safer Salsa20 or ChaCha if what you really need is an IND-CPA cipher and you were going to use AES-CTR or AES-CBC or something instead. Consider using authenticated encryption unless you have a reason not to—really, consider using NaCl crypto_secretbox, just like NaCl crypto_box uses internally with the outcome of an X25519 key agreement.