Please note I am new to Cryptography in general. Sorry if I do not use the correct terminology/my question has some fundamental flaw.

Alice and Bob want to communicate securely over an insecure channel. They decide to use Ed25519 with both an identity key (IdkAlice & IdkBob) and an ephemeral key (EpkAlice & EpkBob) for forward secrecy. Then both compute

SK1 = ECDH( IdkAlice, IdkBob )
SK2 = ECDH( EpkAlice, EpkBob )

SKEY = SHA256( SK1 | SK2 )

and use SKEY as the key in some symmetric cipher.

My question is: How many bits of security is provided in this key exchange?

My assumption is that because Ed25519 provides ~128bits the attacker would need to try $2 \cdot 2^{128}$-times but I'm not sure. (Ignoring active attacks on the key exchange)


Provided that you use the all 256 bits of SKEY as key then the bit security of this scheme is about $\sqrt2\cdot2^{125}$.

The reason behind the $2^{125}$ as opposed to the security of $2^{128}$ is because, for curve25519, $2^{128}$ is just an approximation. If we use, as it is more commonly done, the number of "operation" for this calculation, then the number of point additions required by Pollard's rho is about $\sqrt{2^{251}}\simeq2^{125}$.

The reason behind the $\sqrt2$ factor instead of $2$ is due to the fact that Pollard's rho allows to compute batch discrete logarithms faster than what would be a two separate application of the algorithm. For details, see the section "Batch discrete logarithms" in the original curve25519 paper.


You are right about the $2 \cdot 2^{128} = 2^{129}$ part. You are wrong about them using Ed25519 - it's for digital signature, not for key exchange.

You should make both party sign an Epk which is x25519 or x448 with Idk which can be Ed25519 or Ed448. Or better yet use TLS or SSH.


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.