kex.go 14 KB

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