Subject: Curve25519/448 key agreement for SSH

From: Simon Josefsson <[email-masked]>
Date: Mon, 09 Nov 2015 16:07:11 +0100

Aris and me have prepared a document describing key agreement using the
CFRG curves for Secure Shell.  As you know, [email-masked]
is already implemented by libssh, OpenSSH, Dropbear, and some others.
This is about putting the description of that into IETF format, and to
add the Curve448 hedge variant chosen by CFRG.  It might not be detailed
enough for independent implementation, but we hope to get there.  Any
review and feedback is welcome.

https://tools.ietf.org/html/draft-josefsson-ssh-curves

/Simon

PS. There is https://tools.ietf.org/html/draft-bjh21-ssh-ed25519 but
that talks about Ed25519 signatures.  The document above is about key
agreement.

---

From: Damien Miller <[email-masked]>
Date: Tue, 10 Nov 2015 19:52:25 +1100 (AEDT)

Thanks for writing this up. Some feedback:

> 2.  Key Exchange Methods
> 
>    The key exchange procedure is identical to the one described RFC 5656
>    chapter 4 of [RFC5656].  Public ephemeral keys are transmitted over
>    SSH encapsulated into standard SSH strings.

RFC5656 describes multiple key exchange procedures (ECDH and ECMQV),
so s/the one described RFC 5656/the ECDH method described in RFC 5656/

The procedure isn't completely identical, since different encodings are
used for the wire values and the shared secret. IMO it's worth
foreshadowing this here. Perhaps something like:

   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
   transmitted over SSH encapsulated into standard SSH strings.

I think it is also worth mentioning that the protocol flow, the
SSH_MSG_KEX_ECDH_INIT and SSH_MSG_KEX_ECDH_REPLY messages, and
the structure of the exchange hash are identical between this and
RFC5656 chapter 4.

>    The whole method is based on the Curve25519 and Curve448 scalar
>    multiplication, as described in [I-D.irtf-cfrg-curves].  Private and
>    public keys are generated as described therein, and no special
>    validation is required beyond what is discussed there.  Public keys
>    are defined as strings of 32 bytes for Curve25519 and 56 bytes for
>    Curve448.  The derived shared secret is is 32 bytes when Curve25519
>    is used and 56 bytes when Curve448 is used.

I think that it's worth mentioning here that it's [I-D.irtf-cfrg-curves]
that specifies encodings for the public values.

>    The shared secret, k, is defined in SSH specifications to be a big
>    integer.  This number is calculated as follows.  X is the 32 bytes
>    point obtained by the scalar multiplication of the other side's
>    public key and the local private key scalar.  The whole 32 bytes of

s/32 bytes/32 or 56 bytes/ here.

Maybe mention that X is encoded the same as the public values (AFAIK
I-D.irtf-cfrg-curves doesn't explicitly specify an encoding for the
shared secret - maybe it should?)

>    the number X are then converted into a big integer k.  This
>    conversion follows the network byte order.  This step differs from
>    [RFC5656].

Maybe "converted into a big integer k by treating the value X as an
unsigned, network-byte order integer".

-d

---

From: Damien Miller <[email-masked]>
Date: Tue, 10 Nov 2015 21:33:30 +1100 (AEDT)

On Tue, 10 Nov 2015, Simon Josefsson wrote:

> Damien Miller <[email-masked]> writes:
> 
> For Curve448, it appears to lead to 56 byte bigint or sometimes (when
> msb is 1) a 57 byte bigint with leading zero. Is this a problem? If
> somebody could observe the size difference, it would leak the MSB. If
> worth resolving, how to resolve it?

AFAIK it might not be possible to resolve without being incompatible
with the deployed [email-masked] protocol: OpenSSH at
least checks for correct zero-padding for mpints with the MSB set.

When OpenSSH first added [email-masked], I accidentally
messed up this padding and it would cause ~1/128 connections to libssh
to fail :/

IMO it's probably not worth fixing this now; the other kex protocols
have the same problem, and the shared secret is never sent on the wire.

-d

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 10 Nov 2015 10:54:19 +0100

> the structure of the exchange hash are identical between this and

Agreed, it now has two paragraphs:

   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 transmitted over SSH encapsulated into standard SSH strings.

   The protocol flow, the SSH_MSG_KEX_ECDH_INIT and
   SSH_MSG_KEX_ECDH_REPLY messages, and the structure of the exchange
   hash are identical with chapter 4 of [RFC5656].

> that specifies encodings for the public values.

I've changed it into:

   The whole method is based on the Curve25519 and Curve448 scalar
   multiplication, as described in [I-D.irtf-cfrg-curves].  Private and
   public keys are generated as described therein, and no special
   validation is required beyond what is discussed there.  Public keys
   are defined as strings of 32 bytes for Curve25519 and 56 bytes for
   Curve448.  The derived shared secret is 32 bytes when Curve25519 is
   used and 56 bytes when Curve448 is used.  The encodings of all values
   are defined in [I-D.irtf-cfrg-curves].

> s/32 bytes/32 or 56 bytes/ here.

Fixed.

> shared secret - maybe it should?)

The cfrg-curves document should specify encoding for everything, see
section 5.  It has the encodeUCoordinate function and also says:

   Finally, encode the resulting value as 32 or 56 bytes in little-
   endian order.  For X25519, the unused, most-significant bit MUST be
   zero.

So I believe this is covered by the previous changed paragraph which
refers to cfrg-curves for all encodings.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 10 Nov 2015 14:08:22 +0100

> least checks for correct zero-padding for mpints with the MSB set.

Curve25519 would never have the MSB set, if I understand correctly.  So
what is the potential for incompatibility?  Maybe I'm missing something.

I believe this document should document exactly what
[email-masked] does, otherwise things will be confusing.
Unless there is a significant mistake with it, of course, but then
people shouldn't be using it at all.

Nobody has implemented Curve448 for SSH so there is no compatibility to
think about there.  There has not been a lot of interest from
implementers in Curve448 either, since it is slower (no twisted curve).
The only argument I can think of for supporting it is that it hedges you
against potential new analytical ECC attacks that would affect
Curve25519.  But for this work, I believe including Curve448 makes sense
since it is what CFRG recommends.

/Simon

---

From: Damien Miller <[email-masked]>
Date: Wed, 11 Nov 2015 11:01:40 +1100 (AEDT)

> what is the potential for incompatibility?  Maybe I'm missing something.

That's true of the public values, but not necessarily of the shared
secret, right? I'd expect the shared secret to have the most
significant bit set half the time.

> since it is what CFRG recommends.

Changing the encoding means changing the exchange hash's last field
from mpint to string. I argued for this when Aris sent the original
[email-masked] diff to OpenSSH, but didn't think of the
possible MSB leakage and lost the argument :/

Anyway, to summarise the arguments:

For changing the encoding of K from mpint to string:

- Avoids varying length of K encoding in exchange hash, unlikely leak
  of MSB via timing channel
- Easier to implement

Against:

- Inconsistency between curve25519 and curve448 K encoding
- Inconsistency between curve448 and all the other KEX methods

I honestly don't know whether it is worth fixing it. If I were writing
SSH protocol v.3 then I'd remove mpints from the wire protocol entirely
and have each protocol define a canonical string encoding for its
values.

-d

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 12 Nov 2015 09:45:46 +0100

> significant bit set half the time.

Ah, right.  The shared secret is never encoded on the wire though, but I
suppose the same concern applies internally before hashing.

> and have each protocol define a canonical string encoding for its

To change K from mpint to string we would need to update RFC 5656.

I now believe we should describe what libssh/OpenSSH implements, and add
a security consideration around a potential secret MSB side-channel leak
caused by the length difference.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 12 Nov 2015 10:24:24 +0100

I have updated the document to be clearer about the encoding issue, and
to fix some minor issues.

https://tools.ietf.org/html/draft-josefsson-ssh-curves-01

If Aris and Damien are happy with this version, I believe the document
is in good shape.

Feedback from others is welcome, especially if anyone is considering
implementing this.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 18 Nov 2015 21:39:14 +0100

This is another update, clarifying the encoding issue a bit further and
improving language (thank you Denis).

  https://tools.ietf.org/html/draft-josefsson-ssh-curves-02

A discussion on CFRG came up recently about checking for the all-zero
shared secret.  Does anyone know if libssh or OpenSSH (or anyone else)
performs this check?  Not doing that has apparently led to real security
problems.  For more background, see:

  http://thread.gmane.org/gmane.ietf.irtf.cfrg/6228

Thoughts on whether we should add a MUST to require checking the derived
secret for the all-zero value?

/Simon

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 19 Nov 2015 04:57:05 +0000

Simon Josefsson <[email-masked]> writes:

>performs this check? 

I check for too-small values (too many leading zeroes), of which all-zero
is a special case, as well as a few other oddball things.

Peter.

---

From: Damien Miller <[email-masked]>
Date: Tue, 24 Nov 2015 11:12:20 +1100 (AEDT)

> secret for the all-zero value?

OpenSSH performs the all-zero check

https://anongit.mindrot.org/openssh.git/tree/kexc25519.c?id=8ca915fc761519dd1f7766a550ec597a81db5646#n69

I think it should be a MUST.

-d

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 26 Nov 2015 00:05:34 +0100

I have submited -03 which adds a MUST check for the all-zero secret, and
clarifies the mpint conversion further -- a reference to section 5 of
RFC 4251 is added which explains this properly.  Unfortunately, 4251§5
doesn't say that mpint's are prepended by an uint32 with the length of
the data (or the example is wrong).  Please holler if implementations do
not have the uint32 in the mpint that is hashed, or generally if you
believe the new section 2.1 could be clarified further.

https://tools.ietf.org/html/draft-josefsson-ssh-curves-03

/Simon