Repository: go
Issue: x/crypto/ssh: client requires first hostkey to match, knownhosts doesn't expose available key types
Labels: NeedsFix

<!-- Please answer these questions before submitting your issue. Thanks! -->

### What version of Go are you using (`go version`)?

<pre>
$ go version
go version go1.11.3 linux/amd64
</pre>

### Does this issue reproduce with the latest release?

This is the latest docker release (yes)

### What operating system and processor architecture are you using (`go env`)?

<details><summary><code>go env</code> Output</summary><br><pre>
$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/fsalwin/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/Users/fsalwin/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build745071247=/tmp/go-build -gno-record-gcc-switches"
</pre></details>

### What did you do?
<pre>
	config := &ssh.ClientConfig{
		User:            GetRemoteUsername(host),
		HostKeyCallback: knownHostsCallback,
		Timeout:         30 * time.Second,
		Auth:            []ssh.AuthMethod{},
	}
</pre>
knownHostsCallback is an ssh.HostKeysCallback.

2 machines:
machine A has ecdsa-sha2-nistp256 key for remote host in known hosts file
machine B has ssh-ed25519 key for remote host in known hosts file

If machine A connects to the remote host, the remote host sends the ecdsa-sha2-nistp256 key and is allowed to continue the handshake
If machine B connects to the remote host, the remote host sends the ecdsa-sha2-nistp256 key and is rejected because the callback returns an error.

If I set the host key list to prefer ["ssh-ed25519","ecdsa-sha2-nistp256"...]
Machine A fails
Machine B succeeds

### What did you expect to see?

Since there is no mechanism for discovering the available hostkeys for a host published in ssh/knownhosts , I expected it to try each hostkey in the preference list in turn, failing only if all the keys had been tried.

### What did you see instead?

SSH Client ceases handshake after receiving the first error response from the HostKeysCallback.

Since only the method on the database is returned by knownhosts.New() it is not easy to add another method accessing the same hostKeyDB instance.

I propose adding an initializing function for the database from knownhosts which returns the database - NewDB to complement New which would return a hostkeys interface.

There would be published methods on the receiver:
<pre>
type KnownHostDB interface {
	// HostKeyCallback is knownhosts.New without the DB initialization.
	HostKeyCallback() ssh.HostKeyCallback
	// HostKeyAlgorithms takes an address and returns a list of matching key types.
	HostKeyAlgorithms(address string) ([]string, error)
}
// NewDB is knownhosts.New without the callback code
func NewDB(filename string) (KnownHostDB, error)
</pre>

That way you can just use:
<pre>
	knownHosts := knownhosts.NewDB(knownhostfile)
	// just to cut down on example code, the error is ignored.
	algos, _ := knownHosts.HostKeyAlgorithms(host)
	config := &ssh.ClientConfig{
		User:            GetRemoteUsername(host),
		HostKeyCallback: knownHosts.HostKeysCallback(),
		Timeout:         30 * time.Second,
		Auth:            []ssh.AuthMethod{},
		HostKeyAlgorithms: algos,
	}
</pre>

Alternatively if the protocol allows for it, the host key algorithms could be tried in turn until you run out of algorithms (fail) or you have a match (success)