vendor/golang.org/x/crypto/ssh/kex.go

   1 // Copyright 2013 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package ssh
   6
   7 import (
   8         "crypto"
   9         "crypto/ecdsa"
  10         "crypto/elliptic"
  11         "crypto/rand"
  12         "crypto/subtle"
  13         "errors"
  14         "io"
  15         "math/big"
  16
  17         "golang.org/x/crypto/curve25519"
  18 )
  19
  20 const (
  21         kexAlgoDH1SHA1          = "diffie-hellman-group1-sha1"
  22         kexAlgoDH14SHA1         = "diffie-hellman-group14-sha1"
  23         kexAlgoECDH256          = "ecdh-sha2-nistp256"
  24         kexAlgoECDH384          = "ecdh-sha2-nistp384"
  25         kexAlgoECDH521          = "ecdh-sha2-nistp521"
  26         kexAlgoCurve25519SHA256 = "curve25519-sha256@libssh.org"
  27 )
  28
  29 // kexResult captures the outcome of a key exchange.
  30 type kexResult struct {
  31         // Session hash. See also RFC 4253, section 8.
  32         H []byte
  33
  34         // Shared secret. See also RFC 4253, section 8.
  35         K []byte
  36
  37         // Host key as hashed into H.
  38         HostKey []byte
  39
  40         // Signature of H.
  41         Signature []byte
  42
  43         // A cryptographic hash function that matches the security
  44         // level of the key exchange algorithm. It is used for
  45         // calculating H, and for deriving keys from H and K.
  46         Hash crypto.Hash
  47
  48         // The session ID, which is the first H computed. This is used
  49         // to derive key material inside the transport.
  50         SessionID []byte
  51 }
  52
  53 // handshakeMagics contains data that is always included in the
  54 // session hash.
  55 type handshakeMagics struct {
  56         clientVersion, serverVersion []byte
  57         clientKexInit, serverKexInit []byte
  58 }
  59
  60 func (m *handshakeMagics) write(w io.Writer) {
  61         writeString(w, m.clientVersion)
  62         writeString(w, m.serverVersion)
  63         writeString(w, m.clientKexInit)
  64         writeString(w, m.serverKexInit)
  65 }
  66
  67 // kexAlgorithm abstracts different key exchange algorithms.
  68 type kexAlgorithm interface {
  69         // Server runs server-side key agreement, signing the result
  70         // with a hostkey.
  71         Server(p packetConn, rand io.Reader, magics *handshakeMagics, s Signer) (*kexResult, error)
  72
  73         // Client runs the client-side key agreement. Caller is
  74         // responsible for verifying the host key signature.
  75         Client(p packetConn, rand io.Reader, magics *handshakeMagics) (*kexResult, error)
  76 }
  77
  78 // dhGroup is a multiplicative group suitable for implementing Diffie-Hellman key agreement.
  79 type dhGroup struct {
  80         g, p, pMinus1 *big.Int
  81 }
  82
  83 func (group *dhGroup) diffieHellman(theirPublic, myPrivate *big.Int) (*big.Int, error) {
  84         if theirPublic.Cmp(bigOne) <= 0 || theirPublic.Cmp(group.pMinus1) >= 0 {
  85                 return nil, errors.New("ssh: DH parameter out of bounds")
  86         }
  87         return new(big.Int).Exp(theirPublic, myPrivate, group.p), nil
  88 }
  89
  90 func (group *dhGroup) Client(c packetConn, randSource io.Reader, magics *handshakeMagics) (*kexResult, error) {
  91         hashFunc := crypto.SHA1
  92
  93         var x *big.Int
  94         for {
  95                 var err error
  96                 if x, err = rand.Int(randSource, group.pMinus1); err != nil {
  97                         return nil, err
  98                 }
  99                 if x.Sign() > 0 {
 100                         break
 101                 }
 102         }
 103
 104         X := new(big.Int).Exp(group.g, x, group.p)
 105         kexDHInit := kexDHInitMsg{
 106                 X: X,
 107         }
 108         if err := c.writePacket(Marshal(&kexDHInit)); err != nil {
 109                 return nil, err
 110         }
 111
 112         packet, err := c.readPacket()
 113         if err != nil {
 114                 return nil, err
 115         }
 116
 117         var kexDHReply kexDHReplyMsg
 118         if err = Unmarshal(packet, &kexDHReply); err != nil {
 119                 return nil, err
 120         }
 121
 122         kInt, err := group.diffieHellman(kexDHReply.Y, x)
 123         if err != nil {
 124                 return nil, err
 125         }
 126
 127         h := hashFunc.New()
 128         magics.write(h)
 129         writeString(h, kexDHReply.HostKey)
 130         writeInt(h, X)
 131         writeInt(h, kexDHReply.Y)
 132         K := make([]byte, intLength(kInt))
 133         marshalInt(K, kInt)
 134         h.Write(K)
 135
 136         return &kexResult{
 137                 H:         h.Sum(nil),
 138                 K:         K,
 139                 HostKey:   kexDHReply.HostKey,
 140                 Signature: kexDHReply.Signature,
 141                 Hash:      crypto.SHA1,
 142         }, nil
 143 }
 144
 145 func (group *dhGroup) Server(c packetConn, randSource io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
 146         hashFunc := crypto.SHA1
 147         packet, err := c.readPacket()
 148         if err != nil {
 149                 return
 150         }
 151         var kexDHInit kexDHInitMsg
 152         if err = Unmarshal(packet, &kexDHInit); err != nil {
 153                 return
 154         }
 155
 156         var y *big.Int
 157         for {
 158                 if y, err = rand.Int(randSource, group.pMinus1); err != nil {
 159                         return
 160                 }
 161                 if y.Sign() > 0 {
 162                         break
 163                 }
 164         }
 165
 166         Y := new(big.Int).Exp(group.g, y, group.p)
 167         kInt, err := group.diffieHellman(kexDHInit.X, y)
 168         if err != nil {
 169                 return nil, err
 170         }
 171
 172         hostKeyBytes := priv.PublicKey().Marshal()
 173
 174         h := hashFunc.New()
 175         magics.write(h)
 176         writeString(h, hostKeyBytes)
 177         writeInt(h, kexDHInit.X)
 178         writeInt(h, Y)
 179
 180         K := make([]byte, intLength(kInt))
 181         marshalInt(K, kInt)
 182         h.Write(K)
 183
 184         H := h.Sum(nil)
 185
 186         // H is already a hash, but the hostkey signing will apply its
 187         // own key-specific hash algorithm.
 188         sig, err := signAndMarshal(priv, randSource, H)
 189         if err != nil {
 190                 return nil, err
 191         }
 192
 193         kexDHReply := kexDHReplyMsg{
 194                 HostKey:   hostKeyBytes,
 195                 Y:         Y,
 196                 Signature: sig,
 197         }
 198         packet = Marshal(&kexDHReply)
 199
 200         err = c.writePacket(packet)
 201         return &kexResult{
 202                 H:         H,
 203                 K:         K,
 204                 HostKey:   hostKeyBytes,
 205                 Signature: sig,
 206                 Hash:      crypto.SHA1,
 207         }, nil
 208 }
 209
 210 // ecdh performs Elliptic Curve Diffie-Hellman key exchange as
 211 // described in RFC 5656, section 4.
 212 type ecdh struct {
 213         curve elliptic.Curve
 214 }
 215
 216 func (kex *ecdh) Client(c packetConn, rand io.Reader, magics *handshakeMagics) (*kexResult, error) {
 217         ephKey, err := ecdsa.GenerateKey(kex.curve, rand)
 218         if err != nil {
 219                 return nil, err
 220         }
 221
 222         kexInit := kexECDHInitMsg{
 223                 ClientPubKey: elliptic.Marshal(kex.curve, ephKey.PublicKey.X, ephKey.PublicKey.Y),
 224         }
 225
 226         serialized := Marshal(&kexInit)
 227         if err := c.writePacket(serialized); err != nil {
 228                 return nil, err
 229         }
 230
 231         packet, err := c.readPacket()
 232         if err != nil {
 233                 return nil, err
 234         }
 235
 236         var reply kexECDHReplyMsg
 237         if err = Unmarshal(packet, &reply); err != nil {
 238                 return nil, err
 239         }
 240
 241         x, y, err := unmarshalECKey(kex.curve, reply.EphemeralPubKey)
 242         if err != nil {
 243                 return nil, err
 244         }
 245
 246         // generate shared secret
 247         secret, _ := kex.curve.ScalarMult(x, y, ephKey.D.Bytes())
 248
 249         h := ecHash(kex.curve).New()
 250         magics.write(h)
 251         writeString(h, reply.HostKey)
 252         writeString(h, kexInit.ClientPubKey)
 253         writeString(h, reply.EphemeralPubKey)
 254         K := make([]byte, intLength(secret))
 255         marshalInt(K, secret)
 256         h.Write(K)
 257
 258         return &kexResult{
 259                 H:         h.Sum(nil),
 260                 K:         K,
 261                 HostKey:   reply.HostKey,
 262                 Signature: reply.Signature,
 263                 Hash:      ecHash(kex.curve),
 264         }, nil
 265 }
 266
 267 // unmarshalECKey parses and checks an EC key.
 268 func unmarshalECKey(curve elliptic.Curve, pubkey []byte) (x, y *big.Int, err error) {
 269         x, y = elliptic.Unmarshal(curve, pubkey)
 270         if x == nil {
 271                 return nil, nil, errors.New("ssh: elliptic.Unmarshal failure")
 272         }
 273         if !validateECPublicKey(curve, x, y) {
 274                 return nil, nil, errors.New("ssh: public key not on curve")
 275         }
 276         return x, y, nil
 277 }
 278
 279 // validateECPublicKey checks that the point is a valid public key for
 280 // the given curve. See [SEC1], 3.2.2
 281 func validateECPublicKey(curve elliptic.Curve, x, y *big.Int) bool {
 282         if x.Sign() == 0 && y.Sign() == 0 {
 283                 return false
 284         }
 285
 286         if x.Cmp(curve.Params().P) >= 0 {
 287                 return false
 288         }
 289
 290         if y.Cmp(curve.Params().P) >= 0 {
 291                 return false
 292         }
 293
 294         if !curve.IsOnCurve(x, y) {
 295                 return false
 296         }
 297
 298         // We don't check if N * PubKey == 0, since
 299         //
 300         // - the NIST curves have cofactor = 1, so this is implicit.
 301         // (We don't foresee an implementation that supports non NIST
 302         // curves)
 303         //
 304         // - for ephemeral keys, we don't need to worry about small
 305         // subgroup attacks.
 306         return true
 307 }
 308
 309 func (kex *ecdh) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
 310         packet, err := c.readPacket()
 311         if err != nil {
 312                 return nil, err
 313         }
 314
 315         var kexECDHInit kexECDHInitMsg
 316         if err = Unmarshal(packet, &kexECDHInit); err != nil {
 317                 return nil, err
 318         }
 319
 320         clientX, clientY, err := unmarshalECKey(kex.curve, kexECDHInit.ClientPubKey)
 321         if err != nil {
 322                 return nil, err
 323         }
 324
 325         // We could cache this key across multiple users/multiple
 326         // connection attempts, but the benefit is small. OpenSSH
 327         // generates a new key for each incoming connection.
 328         ephKey, err := ecdsa.GenerateKey(kex.curve, rand)
 329         if err != nil {
 330                 return nil, err
 331         }
 332
 333         hostKeyBytes := priv.PublicKey().Marshal()
 334
 335         serializedEphKey := elliptic.Marshal(kex.curve, ephKey.PublicKey.X, ephKey.PublicKey.Y)
 336
 337         // generate shared secret
 338         secret, _ := kex.curve.ScalarMult(clientX, clientY, ephKey.D.Bytes())
 339
 340         h := ecHash(kex.curve).New()
 341         magics.write(h)
 342         writeString(h, hostKeyBytes)
 343         writeString(h, kexECDHInit.ClientPubKey)
 344         writeString(h, serializedEphKey)
 345
 346         K := make([]byte, intLength(secret))
 347         marshalInt(K, secret)
 348         h.Write(K)
 349
 350         H := h.Sum(nil)
 351
 352         // H is already a hash, but the hostkey signing will apply its
 353         // own key-specific hash algorithm.
 354         sig, err := signAndMarshal(priv, rand, H)
 355         if err != nil {
 356                 return nil, err
 357         }
 358
 359         reply := kexECDHReplyMsg{
 360                 EphemeralPubKey: serializedEphKey,
 361                 HostKey:         hostKeyBytes,
 362                 Signature:       sig,
 363         }
 364
 365         serialized := Marshal(&reply)
 366         if err := c.writePacket(serialized); err != nil {
 367                 return nil, err
 368         }
 369
 370         return &kexResult{
 371                 H:         H,
 372                 K:         K,
 373                 HostKey:   reply.HostKey,
 374                 Signature: sig,
 375                 Hash:      ecHash(kex.curve),
 376         }, nil
 377 }
 378
 379 var kexAlgoMap = map[string]kexAlgorithm{}
 380
 381 func init() {
 382         // This is the group called diffie-hellman-group1-sha1 in RFC
 383         // 4253 and Oakley Group 2 in RFC 2409.
 384         p, _ := new(big.Int).SetString("FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF", 16)
 385         kexAlgoMap[kexAlgoDH1SHA1] = &dhGroup{
 386                 g:       new(big.Int).SetInt64(2),
 387                 p:       p,
 388                 pMinus1: new(big.Int).Sub(p, bigOne),
 389         }
 390
 391         // This is the group called diffie-hellman-group14-sha1 in RFC
 392         // 4253 and Oakley Group 14 in RFC 3526.
 393         p, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF", 16)
 394
 395         kexAlgoMap[kexAlgoDH14SHA1] = &dhGroup{
 396                 g:       new(big.Int).SetInt64(2),
 397                 p:       p,
 398                 pMinus1: new(big.Int).Sub(p, bigOne),
 399         }
 400
 401         kexAlgoMap[kexAlgoECDH521] = &ecdh{elliptic.P521()}
 402         kexAlgoMap[kexAlgoECDH384] = &ecdh{elliptic.P384()}
 403         kexAlgoMap[kexAlgoECDH256] = &ecdh{elliptic.P256()}
 404         kexAlgoMap[kexAlgoCurve25519SHA256] = &curve25519sha256{}
 405 }
 406
 407 // curve25519sha256 implements the curve25519-sha256@libssh.org key
 408 // agreement protocol, as described in
 409 // https://git.libssh.org/projects/libssh.git/tree/doc/curve25519-sha256@libssh.org.txt
 410 type curve25519sha256 struct{}
 411
 412 type curve25519KeyPair struct {
 413         priv [32]byte
 414         pub  [32]byte
 415 }
 416
 417 func (kp *curve25519KeyPair) generate(rand io.Reader) error {
 418         if _, err := io.ReadFull(rand, kp.priv[:]); err != nil {
 419                 return err
 420         }
 421         curve25519.ScalarBaseMult(&kp.pub, &kp.priv)
 422         return nil
 423 }
 424
 425 // curve25519Zeros is just an array of 32 zero bytes so that we have something
 426 // convenient to compare against in order to reject curve25519 points with the
 427 // wrong order.
 428 var curve25519Zeros [32]byte
 429
 430 func (kex *curve25519sha256) Client(c packetConn, rand io.Reader, magics *handshakeMagics) (*kexResult, error) {
 431         var kp curve25519KeyPair
 432         if err := kp.generate(rand); err != nil {
 433                 return nil, err
 434         }
 435         if err := c.writePacket(Marshal(&kexECDHInitMsg{kp.pub[:]})); err != nil {
 436                 return nil, err
 437         }
 438
 439         packet, err := c.readPacket()
 440         if err != nil {
 441                 return nil, err
 442         }
 443
 444         var reply kexECDHReplyMsg
 445         if err = Unmarshal(packet, &reply); err != nil {
 446                 return nil, err
 447         }
 448         if len(reply.EphemeralPubKey) != 32 {
 449                 return nil, errors.New("ssh: peer's curve25519 public value has wrong length")
 450         }
 451
 452         var servPub, secret [32]byte
 453         copy(servPub[:], reply.EphemeralPubKey)
 454         curve25519.ScalarMult(&secret, &kp.priv, &servPub)
 455         if subtle.ConstantTimeCompare(secret[:], curve25519Zeros[:]) == 1 {
 456                 return nil, errors.New("ssh: peer's curve25519 public value has wrong order")
 457         }
 458
 459         h := crypto.SHA256.New()
 460         magics.write(h)
 461         writeString(h, reply.HostKey)
 462         writeString(h, kp.pub[:])
 463         writeString(h, reply.EphemeralPubKey)
 464
 465         kInt := new(big.Int).SetBytes(secret[:])
 466         K := make([]byte, intLength(kInt))
 467         marshalInt(K, kInt)
 468         h.Write(K)
 469
 470         return &kexResult{
 471                 H:         h.Sum(nil),
 472                 K:         K,
 473                 HostKey:   reply.HostKey,
 474                 Signature: reply.Signature,
 475                 Hash:      crypto.SHA256,
 476         }, nil
 477 }
 478
 479 func (kex *curve25519sha256) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
 480         packet, err := c.readPacket()
 481         if err != nil {
 482                 return
 483         }
 484         var kexInit kexECDHInitMsg
 485         if err = Unmarshal(packet, &kexInit); err != nil {
 486                 return
 487         }
 488
 489         if len(kexInit.ClientPubKey) != 32 {
 490                 return nil, errors.New("ssh: peer's curve25519 public value has wrong length")
 491         }
 492
 493         var kp curve25519KeyPair
 494         if err := kp.generate(rand); err != nil {
 495                 return nil, err
 496         }
 497
 498         var clientPub, secret [32]byte
 499         copy(clientPub[:], kexInit.ClientPubKey)
 500         curve25519.ScalarMult(&secret, &kp.priv, &clientPub)
 501         if subtle.ConstantTimeCompare(secret[:], curve25519Zeros[:]) == 1 {
 502                 return nil, errors.New("ssh: peer's curve25519 public value has wrong order")
 503         }
 504
 505         hostKeyBytes := priv.PublicKey().Marshal()
 506
 507         h := crypto.SHA256.New()
 508         magics.write(h)
 509         writeString(h, hostKeyBytes)
 510         writeString(h, kexInit.ClientPubKey)
 511         writeString(h, kp.pub[:])
 512
 513         kInt := new(big.Int).SetBytes(secret[:])
 514         K := make([]byte, intLength(kInt))
 515         marshalInt(K, kInt)
 516         h.Write(K)
 517
 518         H := h.Sum(nil)
 519
 520         sig, err := signAndMarshal(priv, rand, H)
 521         if err != nil {
 522                 return nil, err
 523         }
 524
 525         reply := kexECDHReplyMsg{
 526                 EphemeralPubKey: kp.pub[:],
 527                 HostKey:         hostKeyBytes,
 528                 Signature:       sig,
 529         }
 530         if err := c.writePacket(Marshal(&reply)); err != nil {
 531                 return nil, err
 532         }
 533         return &kexResult{
 534                 H:         H,
 535                 K:         K,
 536                 HostKey:   hostKeyBytes,
 537                 Signature: sig,
 538                 Hash:      crypto.SHA256,
 539         }, nil
 540 }