Repository: go
Issue: x/crypto/ssh/knownhosts: can't verify host key if host certificate is sent
Labels: NeedsInvestigation

<!-- Please answer these questions before submitting your issue. Thanks! -->

### What version of Go are you using (`go version`)?

<pre>
$ go version
go version go1.12.7 linux/amd64
</pre>

### Does this issue reproduce with the latest 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="/home/julian/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/julian/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/lib/go"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/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-build549038278=/tmp/go-build -gno-record-gcc-switches"
</pre></details>

### What did you do?

<!--
If possible, provide a recipe for reproducing the error.
A complete runnable program is good.
A link on play.golang.org is best.
-->

Write the following single line to a file called `known_hosts`:

<pre>
faui06.informatik.uni-erlangen.de ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQC8Mt0PH9D8QxhTRy3LezMhwKSp2l5D5FsljhbDU4NhRH7PP668zdPBfOMoJXNDOHSzKcs4X2K4P5eNVyWhFU7jJwdLDCtetnZWRA984jwmBrWUGOZXpuxs72wjHVfnYp5npq3LzbYUPQ6FzdVmHsWHy/SW1OW28xNP1Z4JhHysqcnZpuVT7wOvgpQ81ltpbnqEEkMez39mwin044CfdpjDQUKSYjySsxexX9wrZqMD4CfwB0D/Y5T/sZToHO8UURnxIw08SMOxn7VwGFFv1F6AhDu9T7Pd/9aWMP0djY/WWIJwB6iAhmalPcdEA88uHBar5Zwbo6yKusmRb0JjiKkb
</pre>

Run the following Go code (in the same directory so that it finds the file or change the path accordingly):

```go
package main

import (
	"golang.org/x/crypto/ssh"
	"golang.org/x/crypto/ssh/knownhosts"
	"log"
)

func main() {
	hostKeyCallback, err := knownhosts.New("known_hosts")
	if err != nil {
		log.Fatalf("unable to read ssh known hosts file: %v", err)
	}

	config := &ssh.ClientConfig{
		User: "nobody",
		HostKeyCallback:   hostKeyCallback,
		// HostKeyAlgorithms: []string{ssh.KeyAlgoRSA},
	}

	client, err := ssh.Dial("tcp", "faui06.informatik.uni-erlangen.de:22", config)
	if err != nil {
		log.Fatalf("unable to connect: %v", err)
	}
	defer client.Close()
}
```

### What did you expect to see?

The host key can be verified successfully.

Due to the minimal example which omits any authentication, there will also be an error in the successful case, but a different one:

```
unable to connect: ssh: handshake failed: ssh: unable to authenticate, attempted methods [none], no supported methods remain
```

Note that the connection works fine if the `HostKeyAlgorithms` from the code is uncommitted, which disables requesting host certificates. I found this behavior quite surprising and it took me some time to figure this out. Also this is inconsistent with OpenSSH which, if it receives a host certificate, seems to extract the host public key from it and also check this against the known hosts file.

### What did you see instead?

The host key can't be verified and the program exits with this error message:

```
unable to connect: ssh: handshake failed: ssh: no authorities for hostname: faui06.informatik.uni-erlangen.de:22
```