ssh: allocate name lists in one piece when unmarshaling

parseNameList split a comma-separated name list with bytes.Split and
then converted each part to a string, allocating the [][]byte from
Split and a separate string for every name. A kexinit message has ten
name lists. For example, the one sent by the OpenSSH 10.3 client holds
68 names in 1594 bytes.

Instead, convert the list to a string once and split that with
strings.Split. The client already does for the server-sig-algs
extension, so a name list takes two allocations no matter how many
names it has.

The names are now substrings of the list they came from. findCommon
returned the agreed name from the client's list, which on a server is
the peer's, and the negotiated algorithms are kept for the lifetime of
the connection. They would have kept the peer's key exchange, host
key, cipher and compression lists alive. This is over 1 KB per
connection for an OpenSSH client. Return the name from a local list
instead, so that nothing from the peer's kexinit outlives the key
exchange.

goos: darwin
goarch: arm64
pkg: golang.org/x/crypto/ssh
cpu: Apple M1 Max
                         │  base.txt   │               new.txt                │
                         │   sec/op    │    sec/op     vs base                │
UnmarshalKexInitMsg-10     3.809µ ± 2%   2.383µ ± 11%  -37.44% (p=0.001 n=20)

                         │   base.txt   │                new.txt                 │
                         │     B/op     │     B/op      vs base                  │
UnmarshalKexInitMsg-10     5.188Ki ± 0%   2.789Ki ± 0%  -46.23% (p=0.000 n=20)

                         │  base.txt  │              new.txt               │
                         │ allocs/op  │ allocs/op   vs base                │
UnmarshalKexInitMsg-10     126.00 ± 0%   30.00 ± 0%  -76.19% (p=0.000 n=20)

The other benchmarks in the package are unchanged.

Fixes golang/go#82099

Change-Id: Id75e931af48632ffb2a107cbd8a6fd622c29f93e
GitHub-Last-Rev: 271b8ad174aca8dc5b59ba3044d0cc882161d2fe
GitHub-Pull-Request: golang/crypto#377
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/848045
Reviewed-by: Nicola Murino <nicola.murino@gmail.com>
Reviewed-by: Junyang Shao <shaojunyang@google.com>
Reviewed-by: David Chase <drchase@google.com>
LUCI-TryBot-Result: golang-scoped@luci-project-accounts.iam.gserviceaccount.com <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

ssh/common.go

diff --git a/ssh/common.go b/ssh/common.go
index 544eb93..62d1b47 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -406,7 +406,12 @@
 	for _, c := range client {
 		for _, s := range server {
 			if c == s {
-				return c, nil
+				// Return the name from the local list, not the peer's, which
+				// would keep the peer's whole name list alive (see parseNameList).
+				if isClient {
+					return c, nil
+				}
+				return s, nil
 			}
 		}
 	}

ssh/messages.go

diff --git a/ssh/messages.go b/ssh/messages.go
index b5c4edc..8c753be 100644
--- a/ssh/messages.go
+++ b/ssh/messages.go
@@ -5,7 +5,6 @@
 package ssh
 
 import (
-	"bytes"
 	"encoding/binary"
 	"errors"
 	"fmt"
@@ -620,10 +619,7 @@
 	return
 }
 
-var (
-	comma         = []byte{','}
-	emptyNameList = []string{}
-)
+var emptyNameList = []string{}
 
 func parseNameList(in []byte) (out []string, rest []byte, ok bool) {
 	contents, rest, ok := parseString(in)
@@ -634,11 +630,7 @@
 		out = emptyNameList
 		return
 	}
-	parts := bytes.Split(contents, comma)
-	out = make([]string, len(parts))
-	for i, part := range parts {
-		out[i] = string(part)
-	}
+	out = strings.Split(string(contents), ",")
 	return
 }