Subject: Re: Curve25519/448 key agreement for SSH

From: denis bider <[email-masked]>
Date: Wed, 11 Nov 2015 21:07:22 +0000

It seems to me the whole X -> K issue can be solved relatively trivially by specifying the operation as an equivalent of a C++ reinterpret_cast.

Any valid X is already a valid K. If the high bit is set, it just so happens that the K is negative. But this doesn't matter because K is never used as an actual integer, anyway.

So, if you have the freedom to do so (not sure how it's done currently for Curve2559 in OpenSSH), you can replace this text:

    The whole 32 bytes of the number X are then converted into a big integer k.

which with these words is underspecified, with this:

    To convert X into K, the [32 bytes / 56 bytes] of X are reinterpreted as an encoded mpint value of length [32 / 56]. Note that if the high bit of the first byte of X is set, the resulting K value is negative.

This allows for an unambiguous and trivial conversion, and doesn't leak anything in the length of K.

----- Original Message -----
From: Damien Miller 
Sent: Tuesday, November 10, 2015 18:01
To: Simon Josefsson 
Cc: [email-masked] 
Subject: Re: Curve25519/448 key agreement for SSH

On Tue, 10 Nov 2015, Simon Josefsson wrote:

> > 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.
> 
> Curve25519 would never have the MSB set, if I understand correctly.  So
> 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.

> 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.

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: denis bider <[email-masked]>
Date: Fri, 13 Nov 2015 12:36:22 +0000

The DSA signature blob is originally defined as a string in RFC 4253, though.

The issue with K is that it's defined as mpint for all key exchange methods in RFC 4253, section 7.2, Output from Key Exchange:

   Encryption keys MUST be computed as HASH, of a known value and K, as
   follows:

   o  Initial IV client to server: HASH(K || H || "A" || session_id)
      (Here K is encoded as mpint and "A" as byte and session_id as raw
      data.  "A" means the single character A, ASCII 65).

It is this that has to be changed - allowing K to have a different encoding for different key exchange methods - in order to allow K to be encoded as string.

----- Original Message -----
From: Niels "Möller" 
Sent: Thursday, November 12, 2015 23:25
To: Simon Josefsson 
Cc: denis bider ; [email-masked] 
Subject: Re: Curve25519/448 key agreement for SSH

Simon Josefsson <[email-masked]> writes:

> A simple approach would be to say that if the MSB is 1, prepend a zero
> byte.  However, the length difference would leak that information.

Note that it's also possible to use some slightly different mapping than
for mpints. Like it's been done in the dsa signature blob since ages;
there the integers are always coded as 20-byte values, no sign bit, and
no normalization if some value happens to get a zero high byte. 

I'm not sure I like that departure from mpint, but I'd like to point out
that it's a possibilty and it's been done before.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: James Cloos <[email-masked]>
Date: Mon, 16 Nov 2015 12:32:06 -0500

Given that one of the design goals of the modern curves is to exchange
the public data as opaque bit strings, the protocol should not use
anything like a mpint to exchange the keys but instead should exchange
them as the opaque bit strings they are.

How the crypto primitives use them is irrelevant to how they should be
exchanged.

Every 25519 public key should be exactly 32 octets and every goldilocks
public key should be exactly 60 octets.  Full stop.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: denis bider <[email-masked]>
Date: Tue, 17 Nov 2015 01:03:37 +0000

James,

this reads like an ideological pamphlet from someone triggered by the wrong hot button words. It seems you're unfamiliar with details.

No one is exchanging 25519 or 448 keys as anything but fixed-length strings. The mpint encoding of the shared secret isn't sent on the wire. It is involved strictly in the SSH parties' private calculation of the exchange hash

---

From: denis bider <[email-masked]>
Date: Thu, 19 Nov 2015 01:59:41 +0000

Regarding the check, it seems to me that SSH has an advantage over TLS, in that it includes hashes of negotiation content in the key exchange. Therefore, perhaps SSH is not as vulnerable to attacks of this type (such as the Triple Handshake attack in TLS).

It still seems a better practice to check than not to check, though, just in case foresight is not 20/20. Surely, if the value is zero, the other party is sabotaging the key exchange (chances of this occurring randomly are astronomically close to zero). If the other party is sabotaging key exchange, it's doing this for some reason. I'm not sure that we need to know the reason in order to refuse to cooperate.

----- Original Message -----
From: Simon Josefsson 
Sent: Wednesday, November 18, 2015 14:39
To: [email-masked] 
Subject: Re: Curve25519/448 key agreement for SSH

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