Subject: Re: Curve25519/448 key agreement for SSH

From: denis bider <[email-masked]>
Date: Tue, 10 Nov 2015 14:32:17 +0000

Simon -

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

The length difference might not be much of a problem, since K is never sent.

> For Curve448 this seems like a problem.  Is it okay to
> prepend a zero byte in SSH big integers even if
> one is not necessary?

No, this is prohibited in RFC 4251:

  Unnecessary leading bytes with the value 0 or 255 MUST NOT be
  included.  The value zero MUST be stored as a string with zero
  bytes of data.
denis

----- Original Message -----
From: Simon Josefsson 
Sent: Tuesday, November 10, 2015 03:30
To: denis bider 
Cc: [email-masked] 
Subject: Re: Curve25519/448 key agreement for SSH

denis bider <[email-masked]> writes:

> Simon, Aris -
>
> thank you for this work. I plan to be implementing this soon, and I
> appreciate that you're moving ahead with standardization.

Hi Denis.  Excellent!  It would be perfect if someone would attempt
implementation based on this document (and cfrg-curves) and tell us what
is missing, and what could have helped them implement it more quickly.

> With respect to conversion of the binary string X into mpint K, is
> there a chance that X might have its high bit set?
>
> If it's possible for the high bit to be set, it seems you ought to
> clarify how that's converted into mpint, given that mpint is signed:
>
> https://www.ietf.org/rfc/rfc4251.txt

>       Represents multiple precision integers in two's complement format,
>       stored as a string, 8 bits per byte, MSB first.  Negative numbers
>       have the value 1 as the most significant bit of the first byte of
>       the data partition.  If the most significant bit would be set for
>       a positive number, the number MUST be preceded by a zero byte.

Good point, I believe the document has to discuss the mapping between
binary Curve25519/Curve448 binary strings into mpint's.

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.

For Curve25519 the most-significant bit is always zero though, so this
will never happen.  For Curve448 this seems like a problem.  Is it okay
to prepend a zero byte in SSH big integers even if one is not necessary?
Then a simple approach would be to do nothing for Curve2559 and to
always add a zero byte for Curve448.

> Besides that, I'm noticing the language could use improvement in
> places ("this document re-use" -> "this document reuses", "is is" ->
> "is").

Fixed, thank you.

/Simon

> Overall, thank you for moving forward with this, though.
>
>
> ----- Original Message -----
> From: Simon Josefsson 
> Sent: Monday, November 9, 2015 09:07
> To: [email-masked] 
> Subject: Curve25519/448 key agreement for SSH
>
> 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: Simon Josefsson <[email-masked]>
Date: Thu, 12 Nov 2015 09:50:22 +0100

> The length difference might not be much of a problem, since K is never sent.

It shouldn't be difficult to fingerprint (statistically, over many
connections) if a remote application performs a hash on X bytes or X+1
bytes.  Knowing which leaks the MSB of the derived secret.

I'm inclined to add a security consideration describing this, and allow
for the potential of a nice conference paper describing how to exploit
this observation.  At this point, to fix this (as Damien described)
appear less appealing.

/Simon

---

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

denis bider <[email-masked]> writes:

> But X and K are different in each key exchange. The only way to make
> them same would be for both parties to conspire.

It doesn't matter if they are different -- a listening entity may be
able to use a side channel (e.g., time) to infer wether the parties
hashed X or X+1 bytes, which leaks one bit of the secret.

> I have suggested solving this by reinterpreting X as an already
> encoded K, which may be negative. Well - that has a different issue:
> it violates mpint encoding when the first byte of X is zero...
>
> All things considered, I don't think it really matters which way this
> is resolved. Just please make sure to be clear when you specify it. :)
> An imprecise specification may lead to problems that manifest in
> e.g. 1/256 of key exchanges.

Yep.  I don't care strongly about this point, but I do share your strong
opinion that it has to be clearly specified.  Right now I'm inclined to
describe exactly what libssh/OpenSSH implements and describe the
vulnerability.

If implementers are interested in "fixing" this while we go through this
process, we have that opportunity.  There is no direct backwards
compatibility problem to care about, since we are registering a new
name.  However, implementations will likely need to support both for
quite some time, and having the two implementations differ has code
maintenance costs.  It seems Aris and Damien represent two significant
implementations of this, so if they can agree on this, we have a way
forward.

/Simon

>
> Simon Josefsson <[email-masked]> , 11/12/2015 8:50 AM:

---

From: denis bider <[email-masked]>
Date: Thu, 12 Nov 2015 08:57:18 +0000

But X and K are different in each key exchange. The only way to make them same would be for both parties to conspire.

I have suggested solving this by reinterpreting X as an already encoded K, which may be negative. Well - that has a different issue: it violates mpint encoding when the first byte of X is zero...

All things considered, I don't think it really matters which way this is resolved. Just please make sure to be clear when you specify it. :) An imprecise specification may lead to problems that manifest in e.g. 1/256 of key exchanges.

 

/Simon