Is the curve25519 algorithm a special(implementation) one of ECDH?

Question

It's the first time for me to learn about Key Exchange Protocol. And I thought that in both ECDH and DH there is a necessary step to share some public infomation(the common parameters) to each sides such as the SSH2_MSG_KEXDH_GEX_REQUEST to get g.

But in my machines, the 2 sides decided to use curve25519 to exchange the key.And When I using WireShark to capture the packages. I only find 2 steps between the c-s key exchange when using curve25519.

1. Diffie-Hellman Key Exchange Init(30) (with DH client e)

2. Diffie-Hellman Key Exchange Reply(31) (with DH server f and the signature H)

So I tried to look up the rfc,

The key exchange procedure is similar to the ECDH method described in chapter 4 of [RFC5656], though with a different wire encoding used for public values and the final shared secret. Public ephemeral keys are encoded for transmission as standard SSH strings.

So here is my question:

Is the curve25519 algorithm a special(implementation) one of ECDH? And why it need no common params for both sides to config?

Answer 1

Is the curve25519 algorithm a special (implementation) one of ECDH?

X25519 is a particular Diffie–Hellman function built out of the elliptic curve Curve25519, originally described in the Curve25519 paper.^* Specifically, it is a function from two 32-byte inputs to one 32-byte output with the Diffie–Hellman properties that make it useful for key agreement: $f(a, f(b, u)) = f(b, f(a, u))$.

And why it need no common params for both sides to config?

Here's one possible way to do design a protocol that does key agreement over the internet.

• 1. Protocol designer chooses a secure DH function like X25519^* that has been thoroughly vetted by the public cryptography community.
  2. Client and server do DH handshake.
     • Note an adversary may be modifying the DH handshake over the wire.
  3. Client and server authenticate DH handshake with long-term identity keys.

Here's another possible way to design a protocol that does key agreement over the internet.

• 1. Protocol designer defers question of what secure DH function to use and makes it configurable.
  2. Client and server software implementors provide umpteen different configuration knobs with inscrutable names like ecdhk283 and accept arbitrary group parameters (like $g$ and $p$ for finite-field DH over $\mathbb Z/p\mathbb Z$, or $a$, $p$, and $p$ for elliptic-curve DH in $y^2 = x^3 + a x + b$ over $\mathbb F_p$).
  3. Client and server operators bumble around in the dark trying to decide which acronym soup to configure their ECDH cipher suites with.
  4. Client and server talk over the network in an attempt to negotiate a choice of cipher suite and curve.
     • Note an adversary may be modifying the cipher suite and curve negotiation over the wire, and may suggest curves (or finite-field DH groups) that don't even make any sense.
  5. Client and server act on the choice of curve and do a DH handshake.
     • Note an adversary may be modifying the DH handshake over the wire.
  6. Client and server authenticate DH handshake with long-term identity keys.

Which way do you think provides adversaries with more room to screw you up?

If it's not obvious, check out FREAK and logjam!

The second way was used for a long time by TLS and SSH; now modern consensus, after decades of experience, is that it is too dangerous, and even for finite-field DH, TLS 1.3 doesn't allow dynamic group negotiation. It is a lot of work to validate curves, and much easier to implement them securely and efficiently if you don't allow arbitrary fields and parameters—and it is essentially impossible to dynamically validate finite-field DH groups securely.

---

_{^* A note on terminology: These days, Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\mathbb F_p$ where $p = 2^{255} - 19$, while X25519 means a specific Diffie–Hellman function based on scalar multiplication using only $x$ coordinates on Curve25519, roughly $\operatorname{X25519}(n, u) = x([n] x^{-1}(u))$—i.e., if $u$ is the $x$ coordinate of a point $P$ on Curve25519, then $\operatorname{X25519}(n, u)$ is the $x$ coordinate of the scalar multiple $[n]P$ on Curve25519. The Curve25519 paper was written before this terminology was settled, and uses the name ‘Curve25519’ to refer to the DH function.}

Answer 2

I haven't learned details of Curve25519, but the most important reason there's no exchange of $g$ the generator, is that it's already a specified parameter of Curve25519.

In any discrete-logarithm cryptography setup, there needs to be at least 2 elements:

• a group (modulus in DH, curve in ECDH), and

• a generator (a number in DH, or a point in ECDH).

The reason you don't see $g$ exchanged is probably because both parties already know its value.

So I tried to look up the rfc,

The key exchange procedure is similar to the ECDH method described in chapter 4 of [RFC5656], though with a different wire encoding used for public values and the final shared secret. Public ephemeral keys are encoded for transmission as standard SSH strings.

As you see, it says "ephemeral", that means the static key (which is the generator $g$) is not exchanged here, but instead "pre-installed".

Question in the comment: Why don't DH and ECDH "pre-install" static key (public parameters)

Because there's too many to choose from. There's at least 1 IETF RFC listing several parameters for DH, and SECG standards specifies several curves of various security levels and forms.

It's not to say that Curve25519 is alone by itself - there's the Curve448 (224-bit security), which is also what some may call "safe curve".

Curve25519 is developed by Daniel J. Bernstein, who is known for advocating security-by-design. And Curve448-Goldilocks is developed by Mike Hamburg of Rambus Cryptography Research.

Both of these two curves specify parameter as part of their implementation to avoid inconsistencies and help in improving implementation quality.

Answer 3

For standard SSH, most non-EC DH keyexchange (aka classic, integer, modp, or $Z_p$) and all ECDH keyexchange use predefined groups which include the integer g in DH or point G in (X9.63-style) ECDH. The group is defined by the keyexchange method name selected by the KEXINIT (type 20) message exchange.

Methods diffie-hellman-group-exchange-{sha1,sha256} ([KEX]DH_GEX) in RFC4419, and the little-used variant gss-gex-* in RFC4462, are the only standard ones that transmit group parameters, and they are only defined for DH not ECDH.

The draft you link follows this practice, although the Bernstein ECDH method used for X25519 and X448 actually uses only the X-coordinate, not the full point.