ssh: add diffie-hellman-group16-sha512 kex

This group is disabled by default because it is a bit slower than
the others.
The group18-sha512 variant is too slow to include.

Benchstat results including diffie-hellman-group18-sha512:

name                                           time/op
Kexes/diffie-hellman-group-exchange-sha256-12  22.6ms ± 9%
Kexes/diffie-hellman-group18-sha512-12          1.15s ±11%
Kexes/ecdh-sha2-nistp384-12                    3.91ms ± 6%
Kexes/ecdh-sha2-nistp256-12                     304µs ± 5%
Kexes/curve25519-sha256@libssh.org-12           413µs ± 7%
Kexes/ecdh-sha2-nistp521-12                    11.6ms ±13%
Kexes/curve25519-sha256-12                      361µs ± 5%
Kexes/diffie-hellman-group-exchange-sha1-12    22.9ms ± 9%
Kexes/diffie-hellman-group1-sha1-12            3.59ms ± 6%
Kexes/diffie-hellman-group14-sha1-12           22.1ms ±11%
Kexes/diffie-hellman-group14-sha256-12         21.6ms ± 8%
Kexes/diffie-hellman-group16-sha512-12          138ms ± 9%

name                                           alloc/op
Kexes/diffie-hellman-group-exchange-sha256-12  67.8kB ± 1%
Kexes/diffie-hellman-group18-sha512-12          243kB ± 9%
Kexes/ecdh-sha2-nistp384-12                    13.9kB ± 0%
Kexes/ecdh-sha2-nistp256-12                    12.1kB ± 0%
Kexes/curve25519-sha256@libssh.org-12          8.22kB ± 0%
Kexes/ecdh-sha2-nistp521-12                    16.5kB ± 0%
Kexes/curve25519-sha256-12                     8.22kB ± 0%
Kexes/diffie-hellman-group-exchange-sha1-12    67.5kB ± 0%
Kexes/diffie-hellman-group1-sha1-12            34.9kB ± 0%
Kexes/diffie-hellman-group14-sha1-12           61.9kB ± 0%
Kexes/diffie-hellman-group14-sha256-12         62.0kB ± 0%
Kexes/diffie-hellman-group16-sha512-12          117kB ± 0%

name                                           allocs/op
Kexes/diffie-hellman-group-exchange-sha256-12     314 ± 0%
Kexes/diffie-hellman-group18-sha512-12            271 ± 4%
Kexes/ecdh-sha2-nistp384-12                       243 ± 0%
Kexes/ecdh-sha2-nistp256-12                       213 ± 0%
Kexes/curve25519-sha256@libssh.org-12             168 ± 0%
Kexes/ecdh-sha2-nistp521-12                       245 ± 0%
Kexes/curve25519-sha256-12                        168 ± 0%
Kexes/diffie-hellman-group-exchange-sha1-12       314 ± 0%
Kexes/diffie-hellman-group1-sha1-12               255 ± 0%
Kexes/diffie-hellman-group14-sha1-12              255 ± 0%
Kexes/diffie-hellman-group14-sha256-12            255 ± 0%
Kexes/diffie-hellman-group16-sha512-12            256 ± 0%

Change-Id: Id119401fda7e417675325f37e3d442e70585206c
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/506839
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Filippo Valsorda <filippo@golang.org>

4 files changed, 61 insertions, 3 deletions

diff --git a/ssh/common.go b/ssh/common.go
index 3862ec8..b419c76 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -49,7 +49,8 @@ var supportedKexAlgos = []string{
 	// P384 and P521 are not constant-time yet, but since we don't
 	// reuse ephemeral keys, using them for ECDH should be OK.
 	kexAlgoECDH256, kexAlgoECDH384, kexAlgoECDH521,
-	kexAlgoDH14SHA256, kexAlgoDH14SHA1, kexAlgoDH1SHA1,
+	kexAlgoDH14SHA256, kexAlgoDH16SHA512, kexAlgoDH14SHA1,
+	kexAlgoDH1SHA1,
 }
 
 // serverForbiddenKexAlgos contains key exchange algorithms, that are forbidden
@@ -59,8 +60,9 @@ var serverForbiddenKexAlgos = map[string]struct{}{
 	kexAlgoDHGEXSHA256: {}, // server half implementation is only minimal to satisfy the automated tests
 }
 
-// preferredKexAlgos specifies the default preference for key-exchange algorithms
-// in preference order.
+// preferredKexAlgos specifies the default preference for key-exchange
+// algorithms in preference order. The diffie-hellman-group16-sha512 algorithm
+// is disabled by default because it is a bit slower than the others.
 var preferredKexAlgos = []string{
 	kexAlgoCurve25519SHA256, kexAlgoCurve25519SHA256LibSSH,
 	kexAlgoECDH256, kexAlgoECDH384, kexAlgoECDH521,
diff --git a/ssh/kex.go b/ssh/kex.go
index 927a90c..8a05f79 100644
--- a/ssh/kex.go
+++ b/ssh/kex.go
@@ -23,6 +23,7 @@ const (
 	kexAlgoDH1SHA1                = "diffie-hellman-group1-sha1"
 	kexAlgoDH14SHA1               = "diffie-hellman-group14-sha1"
 	kexAlgoDH14SHA256             = "diffie-hellman-group14-sha256"
+	kexAlgoDH16SHA512             = "diffie-hellman-group16-sha512"
 	kexAlgoECDH256                = "ecdh-sha2-nistp256"
 	kexAlgoECDH384                = "ecdh-sha2-nistp384"
 	kexAlgoECDH521                = "ecdh-sha2-nistp521"
@@ -430,6 +431,17 @@ func init() {
 		hashFunc: crypto.SHA256,
 	}
 
+	// This is the group called diffie-hellman-group16-sha512 in RFC
+	// 8268 and Oakley Group 16 in RFC 3526.
+	p, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D788719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA993B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199FFFFFFFFFFFFFFFF", 16)
+
+	kexAlgoMap[kexAlgoDH16SHA512] = &dhGroup{
+		g:        new(big.Int).SetInt64(2),
+		p:        p,
+		pMinus1:  new(big.Int).Sub(p, bigOne),
+		hashFunc: crypto.SHA512,
+	}
+
 	kexAlgoMap[kexAlgoECDH521] = &ecdh{elliptic.P521()}
 	kexAlgoMap[kexAlgoECDH384] = &ecdh{elliptic.P384()}
 	kexAlgoMap[kexAlgoECDH256] = &ecdh{elliptic.P256()}
diff --git a/ssh/kex_test.go b/ssh/kex_test.go
index 327013b..cb7f66a 100644
--- a/ssh/kex_test.go
+++ b/ssh/kex_test.go
@@ -8,6 +8,7 @@ package ssh
 
 import (
 	"crypto/rand"
+	"fmt"
 	"reflect"
 	"sync"
 	"testing"
@@ -63,3 +64,43 @@ func TestKexes(t *testing.T) {
 		})
 	}
 }
+
+func BenchmarkKexes(b *testing.B) {
+	type kexResultErr struct {
+		result *kexResult
+		err    error
+	}
+
+	for name, kex := range kexAlgoMap {
+		b.Run(name, func(b *testing.B) {
+			for i := 0; i < b.N; i++ {
+				t1, t2 := memPipe()
+
+				s := make(chan kexResultErr, 1)
+				c := make(chan kexResultErr, 1)
+				var magics handshakeMagics
+
+				go func() {
+					r, e := kex.Client(t1, rand.Reader, &magics)
+					t1.Close()
+					c <- kexResultErr{r, e}
+				}()
+				go func() {
+					r, e := kex.Server(t2, rand.Reader, &magics, testSigners["ecdsa"].(AlgorithmSigner), testSigners["ecdsa"].PublicKey().Type())
+					t2.Close()
+					s <- kexResultErr{r, e}
+				}()
+
+				clientRes := <-c
+				serverRes := <-s
+
+				if clientRes.err != nil {
+					panic(fmt.Sprintf("client: %v", clientRes.err))
+				}
+				if serverRes.err != nil {
+					panic(fmt.Sprintf("server: %v", serverRes.err))
+				}
+			}
+		})
+	}
+}
diff --git a/ssh/test/session_test.go b/ssh/test/session_test.go
index b44877e..4745ed9 100644
--- a/ssh/test/session_test.go
+++ b/ssh/test/session_test.go
@@ -410,6 +410,9 @@ func TestKeyExchanges(t *testing.T) {
 	// are not included in the default list of supported kex so we have to add them
 	// here manually.
 	kexOrder = append(kexOrder, "diffie-hellman-group-exchange-sha1", "diffie-hellman-group-exchange-sha256")
+	// The key exchange algorithms diffie-hellman-group16-sha512 is disabled by
+	// default so we add it here manually.
+	kexOrder = append(kexOrder, "diffie-hellman-group16-sha512")
 	for _, kex := range kexOrder {
 		t.Run(kex, func(t *testing.T) {
 			server := newServer(t)