11
$\begingroup$

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 AES256 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 AES128 used for the purposes of symmetric encryption. AES128 would be 40% faster than AES256, and there would be no advantage to using AES256 over AES128.

$\endgroup$
  • 1
    $\begingroup$ Even ignoring the multi-target attacks pointed out in the below answer, AES256 also has four more rounds than AES128 (14 rounds rather than 10), which gives it a bit of a better security margin. $\endgroup$ – forest Feb 19 at 0:13
14
$\begingroup$

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, the expected cost of recovering one of $n$ keys is $2^{128}/n$, and on a machine parallelized $n^2$ ways, the expected time is that of $2^{128}/n^3$ 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.

$\endgroup$
  • 3
    $\begingroup$ And definitely use an AEAD system, even if it's just encrypt-then-MAC. ChaCha20-Poly1305 is fine. AES-GCM is fine. ChaCha20 alone.... not so fine. $\endgroup$ – SAI Peregrinus Jun 4 '18 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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