0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to Cryptography. Are you sure that this is the first time that two servers communicate? $\endgroup$ – kelalaka Apr 28 at 8:01
  • $\begingroup$ @kelalaka no, and I want to add some supplement. The key exchange method is Curve25519-sha256, is it special one of ECDH? $\endgroup$ – Anon Apr 28 at 8:22
  • $\begingroup$ You can add all your supplement into your question by clicking the edit button. $\endgroup$ – kelalaka Apr 28 at 8:26
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ TLS before 1.3 (or RFC7919) used server-specified, and often server-generated-perhaps-badly, or even tampered, DH group. Although in theory it allowed 'explicit' ECDH curve, no-one implemented anything but 'named' (X9/NIST) curves . SSH mostly used standard (Oakley+) groups for DH, and only standard curves for ECDH. $\endgroup$ – dave_thompson_085 Apr 29 at 5:01
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So there is any reason DH and ECDH don't pre install the static key, but Curve25519 does? $\endgroup$ – Anon Apr 28 at 9:08
  • $\begingroup$ Becuase DH and ECDH has too many parameters to choose from, there's at least 1 RFC listing several possible DH modulus targeting different security level, and several curves specified in SECG (secg.org) standards. In contrast, there's only 1 Curve25519 instance. $\endgroup$ – DannyNiu Apr 28 at 9:10
  • $\begingroup$ Of course, Curve25519 isn't the only curve that some may call "safe curve", there's also Curve448 which provides 224 bits security. These curves are safe in the sense that they have straightforward misuse-resistant implementation. $\endgroup$ – DannyNiu Apr 28 at 9:12
  • 1
    $\begingroup$ The generator is part of the group (or curve) and is not a key -- for either DH or ECDH. The result of exponentiating or scalar-multiplying the generator by a private number is the public key, either static/longterm or ephemeral depending on the key. $\endgroup$ – dave_thompson_085 Apr 29 at 4:57
0
$\begingroup$

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.

$\endgroup$

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.