Re: Curve25519/448 key agreement for SSH

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 protected] 
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 protected] 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 protected] 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 protected] 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