code review 13021045: go.crypto/ssh: implement client side elliptic curve

go.crypto/ssh: implement elliptic curve
Diffie-Hellman, including host key signature verification.

Moves host key cryptographic verification to
ClientConn.handshake(), so RSA host keys are also verified.

Fixes issue 6158.

[hanwen-google, 2013-08-16 17:01:55]

Hello dave@cheney.net, agl@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go.crypto

[hanwen-google, 2013-08-16 17:04:49]

This is more of a heads up. The server side is missing, and the tests against
SSHD need tweaking, but I can connect to a local SSHD with this.

This is my first attempt at crypto code, so if you have any early comments, I
would be grateful.

I'll add the server side early next week.

[hanwen-google, 2013-08-20 14:02:02]

I've added server side too, and a test for all key exchanges.

both tests under ssh/ and ssh/test/ pass.

[agl1, 2013-08-20 14:30:14]

(Note: on vacation until next week. Review may be delayed.)

On Tue, Aug 20, 2013 at 10:02 AM,  <hanwen@google.com> wrote:
> I've added server side too, and a test for all key exchanges.
>
> both tests under ssh/ and ssh/test/ pass.
>
> https://codereview.appspot.com/13021045/

[agl1, 2013-08-26 16:39:16]

Mostly LGTM.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go
File ssh/client.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode146
ssh/client.go:146: // NOSUBMIT - should check this only if HostKeyChecker is
set?
Note NOSUBMIT. If this is checking the signature of the handshake by the
purported host key, then I believe that it should always be called.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode180
ssh/client.go:180: magics *handshakeMagics, hostKeyAlgo string) (*kexResult,
error) {
I'd unbreak the line.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode208
ssh/client.go:208: return nil, errors.New("ssh: elliptic.Unmarshal failure.")
most error messages here do not include a period at the end.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode214
ssh/client.go:214: // generate secret
shared secret.

https://codereview.appspot.com/13021045/diff/29001/ssh/common.go
File ssh/common.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/common.go#newcode35
ssh/common.go:35: kexAlgoDH14SHA1, kexAlgoDH1SHA1}
I think the } should be on its own line.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
File ssh/server.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode168
ssh/server.go:168: return nil, errors.New("ssh: elliptic.Unmarshal failure.")
ditto about the period at the end.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode190
ssh/server.go:190: // generate secret
shared secret.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode244
ssh/server.go:244: if x.BitLen() == 0 && y.BitLen() == 0 {
.BitLen() == 0 should be written .Sign() == 0

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
ssh/server.go:252: zx, zy := curve.ScalarMult(x, y, curve.Params().N.Bytes())
This is expensive and all NIST curves have a cofactor of 1, so there's no need
to do this, I believe.

[hanwen-google, 2013-08-26 17:20:13]

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go
File ssh/client.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode146
ssh/client.go:146: // NOSUBMIT - should check this only if HostKeyChecker is
set?
On 2013/08/26 16:39:16, agl1 wrote:
> Note NOSUBMIT. If this is checking the signature of the handshake by the
> purported host key, then I believe that it should always be called. 

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode180
ssh/client.go:180: magics *handshakeMagics, hostKeyAlgo string) (*kexResult,
error) {
On 2013/08/26 16:39:16, agl1 wrote:
> I'd unbreak the line.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode208
ssh/client.go:208: return nil, errors.New("ssh: elliptic.Unmarshal failure.")
On 2013/08/26 16:39:16, agl1 wrote:
> most error messages here do not include a period at the end.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/client.go#newcode214
ssh/client.go:214: // generate secret
On 2013/08/26 16:39:16, agl1 wrote:
> shared secret.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/common.go
File ssh/common.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/common.go#newcode35
ssh/common.go:35: kexAlgoDH14SHA1, kexAlgoDH1SHA1}
On 2013/08/26 16:39:16, agl1 wrote:
> I think the } should be on its own line.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
File ssh/server.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode168
ssh/server.go:168: return nil, errors.New("ssh: elliptic.Unmarshal failure.")
On 2013/08/26 16:39:16, agl1 wrote:
> ditto about the period at the end.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode190
ssh/server.go:190: // generate secret
On 2013/08/26 16:39:16, agl1 wrote:
> shared secret.

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode244
ssh/server.go:244: if x.BitLen() == 0 && y.BitLen() == 0 {
On 2013/08/26 16:39:16, agl1 wrote:
> .BitLen() == 0 should be written .Sign() == 0

Done.

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
ssh/server.go:252: zx, zy := curve.ScalarMult(x, y, curve.Params().N.Bytes())
On 2013/08/26 16:39:16, agl1 wrote:
> This is expensive and all NIST curves have a cofactor of 1, so there's no need
> to do this, I believe.

(reading up .. )

OK. It would be more robust if we could check the cofactor here, since SSH also
allows for generic curves, eg. "ecdh-sha2-1.3.132.0.36", although this CL
obviously doesn't add it. 


Is there a foolproof way of checking the cofactor? It looks as if I could tell
from the size of N-P, but they're not exactly the same.

[agl1, 2013-08-27 16:54:32]

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
File ssh/server.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
ssh/server.go:252: zx, zy := curve.ScalarMult(x, y, curve.Params().N.Bytes())
On 2013/08/26 17:20:13, hanwen wrote:
> On 2013/08/26 16:39:16, agl1 wrote:
> > This is expensive and all NIST curves have a cofactor of 1, so there's no
need
> > to do this, I believe.
> 
> (reading up .. )
> 
> OK. It would be more robust if we could check the cofactor here, since SSH
also
> allows for generic curves, eg. "ecdh-sha2-1.3.132.0.36", although this CL
> obviously doesn't add it. 

I think that supporting generic curves is a mistake for the spec and I don't
think we would ever want to support it.

> Is there a foolproof way of checking the cofactor? It looks as if I could tell
> from the size of N-P, but they're not exactly the same.

N-P is the number of points in the subgroup minus the size of the field, that's
not a useful number. crypto/elliptic doesn't record the full group size, but I
think I'm just going to remove this when landing: we're using ephemeral keys
anyway so small subgroup attacks don't matter even if we had any curves with
significant subgroups.

https://codereview.appspot.com/13021045/diff/37001/ssh/cipher.go
File ssh/cipher.go (right):

https://codereview.appspot.com/13021045/diff/37001/ssh/cipher.go#newcode93
ssh/cipher.go:93: // DefaultKeyExchangeOrder specifies a default set of key
exchange algorithms
Why export this? I fear that it invites code to modify it.

[hanwen-google, 2013-08-27 17:48:16]

PTAL

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
File ssh/server.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
ssh/server.go:252: zx, zy := curve.ScalarMult(x, y, curve.Params().N.Bytes())
On 2013/08/27 16:54:33, agl1 wrote:
> On 2013/08/26 17:20:13, hanwen wrote:
> > On 2013/08/26 16:39:16, agl1 wrote:
> > > This is expensive and all NIST curves have a cofactor of 1, so there's no
> need
> > > to do this, I believe.
> > 
> > (reading up .. )
> > 
> > OK. It would be more robust if we could check the cofactor here, since SSH
> also
> > allows for generic curves, eg. "ecdh-sha2-1.3.132.0.36", although this CL
> > obviously doesn't add it. 
> 
> I think that supporting generic curves is a mistake for the spec and I don't
> think we would ever want to support it.

Documented.

> > Is there a foolproof way of checking the cofactor? It looks as if I could
tell
> > from the size of N-P, but they're not exactly the same.
> 
> N-P is the number of points in the subgroup minus the size of the field,
that's
> not a useful number. 

Are you sure?  By the Hasse theorem, N-P is about (1/h-1)P, so for h > 1, N-P is
too small (it looks to be about sqrt(P)). Maybe I'm  missing something. 

> crypto/elliptic doesn't record the full group size, but I
> think I'm just going to remove this when landing: we're using ephemeral keys
> anyway so small subgroup attacks don't matter even if we had any curves with
> significant subgroups.

added comment.

https://codereview.appspot.com/13021045/diff/37001/ssh/cipher.go
File ssh/cipher.go (right):

https://codereview.appspot.com/13021045/diff/37001/ssh/cipher.go#newcode93
ssh/cipher.go:93: // DefaultKeyExchangeOrder specifies a default set of key
exchange algorithms
On 2013/08/27 16:54:33, agl1 wrote:
> Why export this? I fear that it invites code to modify it.

unexported. by the same logic, shouldn't DefaultCipherOrder be hidden too?

https://codereview.appspot.com/13021045/diff/37001/ssh/common.go
File ssh/common.go (right):

https://codereview.appspot.com/13021045/diff/37001/ssh/common.go#newcode199
ssh/common.go:199: // TODO(hanwen): should this not filter out unknown
algorithms?
Adam, any comment on this?

[agl1, 2013-08-27 18:31:36]

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
File ssh/server.go (right):

https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
ssh/server.go:252: zx, zy := curve.ScalarMult(x, y, curve.Params().N.Bytes())
On 2013/08/27 17:48:16, hanwen wrote:
> Are you sure?  By the Hasse theorem, N-P is about (1/h-1)P, so for h > 1, N-P
is
> too small (it looks to be about sqrt(P)). Maybe I'm  missing something. 

Yes, you're right. The difference is related by Hasse. But I'm not sure about
your equations:

|#E - P - 1| <= 2*sqrt(P)   (Hasse)
|#E - P| <= 2*sqrt(P)       (approx since P is very large)
|hN - P| <= 2*sqrt(P)       (hN is the number of points in the full group)
|N - P| <= 2*sqrt(P)-(h-1)N (sort of, see below)

The last line gets complex because, depending on the value of h, we might be
making the RHS negative and then the inequality is wrong. Although we can
certainly say that, for h=1, |N - P| <= 2*sqrt(P) and, if that's not true, then
we know that there's a subgroup.

(Although, for curve25519, |N-P| == 2*sqrt(P)-(h-1)N to the limits of a float.)

But I still don't think we should do anything here since it's an ephemeral key
:)

https://codereview.appspot.com/13021045/diff/37001/ssh/common.go
File ssh/common.go (right):

https://codereview.appspot.com/13021045/diff/37001/ssh/common.go#newcode199
ssh/common.go:199: // TODO(hanwen): should this not filter out unknown
algorithms?
On 2013/08/27 17:48:17, hanwen wrote:
> Adam, any comment on this?

No strong feelings. I guess by filtering out unknown algorithms code might be
able to specify overly optimistic algorithms on the assumption that a future
version might support them without breaking now.

[hanwen-google, 2013-08-28 11:36:21]

On Tue, Aug 27, 2013 at 8:31 PM,  <agl@golang.org> wrote:
>
> https://codereview.appspot.com/13021045/diff/29001/ssh/server.go
> File ssh/server.go (right):
>
> https://codereview.appspot.com/13021045/diff/29001/ssh/server.go#newcode252
> ssh/server.go:252: zx, zy := curve.ScalarMult(x, y,
> curve.Params().N.Bytes())
> On 2013/08/27 17:48:16, hanwen wrote:
>>
>> Are you sure?  By the Hasse theorem, N-P is about (1/h-1)P, so for h >
>
> 1, N-P is
>>
>> too small (it looks to be about sqrt(P)). Maybe I'm  missing
>
> something.
>
> Yes, you're right. The difference is related by Hasse. But I'm not sure
> about your equations:
>
> |#E - P - 1| <= 2*sqrt(P)   (Hasse)
> |#E - P| <= 2*sqrt(P)       (approx since P is very large)
> |hN - P| <= 2*sqrt(P)       (hN is the number of points in the full
> group)
> |N - P| <= 2*sqrt(P)-(h-1)N (sort of, see below)

> The last line gets complex because, depending on the value of h, we
> might be making the RHS negative and then the inequality is wrong.


 hN = |#E|

so

 hN < P + 2sqrt(P)
 N < P/h + 2sqrt(P) /h
 P - N > (1 - 1/h) P - 2 sqrt(P) / h

(the other side goes similar).

> Although we can certainly say that, for h=1, |N - P| <= 2*sqrt(P) and,
> if that's not true, then we know that there's a subgroup.
>
> (Although, for curve25519, |N-P| == 2*sqrt(P)-(h-1)N to the limits of a
> float.)
>
> But I still don't think we should do anything here since it's an
> ephemeral key :)

Certainly :)

> https://codereview.appspot.com/13021045/diff/37001/ssh/common.go
> File ssh/common.go (right):
>
> https://codereview.appspot.com/13021045/diff/37001/ssh/common.go#newcode199
> ssh/common.go:199: // TODO(hanwen): should this not filter out unknown
> algorithms?

>> Adam, any comment on this?
>
>
> No strong feelings. I guess by filtering out unknown algorithms code
> might be able to specify overly optimistic algorithms on the assumption
> that a future version might support them without breaking now.

OK, removed the TODO.

Feel free to submit.

--
Han-Wen Nienhuys
Google Munich
hanwen@google.com

[agl1, 2013-08-28 14:50:41]

*** Submitted as
https://code.google.com/p/go/source/detail?r=fe336c7071ab&repo=crypto ***

go.crypto/ssh: implement ECDH.

Implement elliptic-curve Diffie-Hellman, including host key signature
verification.

Moves host key cryptographic verification to ClientConn.handshake(), so
RSA host keys are also verified.

Fixes issue 6158.

R=dave, agl
CC=golang-dev
https://codereview.appspot.com/13021045

Committer: Adam Langley <agl@golang.org>

[hanwen-google, 2013-08-28 14:51:32]

*** Abandoned ***