Repository: go
Issue: x/crypto/ssh: knownhosts does not handle multiple keys with same type
Labels: NeedsInvestigation

<!-- Please answer these questions before submitting your issue. Thanks! -->

### What version of Go are you using (`go version`)?
<pre>
go version go1.11 darwin/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>
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/rom/Library/Caches/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/rom/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/Cellar/go/1.11/libexec"
GOTMPDIR=""
GOTOOLDIR="/usr/local/Cellar/go/1.11/libexec/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
CXX="clang++"
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 -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/h0/fll06vqd6wd6mqndvvtfy75r0000gn/T/go-build120797240=/tmp/go-build -gno-record-gcc-switches -fno-common"
</pre></details>

### What did you do?
Open a SSH connection to a host that has multiple keys in my known_hosts file. 

There is a load balancer is in front of two SSH servers that maintain different keys. Although I do not agree the setup is best practice, OpenSSH allows for multiple keys+types for the same hostname. 

I used a simple test application to validate:
<pre>
package main

import (
        "flag"
        "fmt"
        "log"
        "net"
        "os"

        "golang.org/x/crypto/ssh"
        "golang.org/x/crypto/ssh/agent"
        "os/user"
        "path/filepath"
        "golang.org/x/crypto/ssh/knownhosts"
)

var (
        USER = flag.String("user", os.Getenv("USER"), "ssh username")
        HOST = flag.String("host", "localhost", "ssh server hostname")
        PORT = flag.Int("port", 22, "ssh server port")
        PASS = flag.String("pass", os.Getenv("SOCKSIE_SSH_PASSWORD"), "ssh password")
        SIZE = flag.Int("s", 1<<15, "set max packet size")
)

func init() {
        flag.Parse()
}

func main() {

        var auths []ssh.AuthMethod
        if aconn, err := net.Dial("unix", os.Getenv("SSH_AUTH_SOCK")); err == nil {
                auths = append(auths, ssh.PublicKeysCallback(agent.NewClient(aconn).Signers))

        }
        if *PASS != "" {
                auths = append(auths, ssh.Password(*PASS))
        }

        callback, err := GetKnownHostsCallback()

        config := ssh.ClientConfig{
                User: *USER,
                Auth: auths,
                HostKeyCallback: callback,
        }
        addr := fmt.Sprintf("%s:%d", *HOST, *PORT)
        conn, err := ssh.Dial("tcp", addr, &config)
        if err != nil {
                log.Fatalf("unable to connect to [%s]: %v", addr, err)
        }

        conn.Close()

}

func GetKnownHostsCallback() (ssh.HostKeyCallback, error) {
        usr, err := user.Current()

        if err != nil {
                return nil, err
        }

        name := filepath.Join(usr.HomeDir, ".ssh", "known_hosts")
        log.Printf("Using known hosts file %s", name)
        f, err := knownhosts.New(name)

        if err != nil {
                return nil, err
        }

        return func(addr string, remote net.Addr, key ssh.PublicKey) error {
                log.Printf("Checking known host %s (%v)", addr, remote)
                return f(addr, remote, key)
        }, nil
}
</pre>

### What did you expect to see?
I expected the host key to be validated in the same manner as OpenSSH. 

### What did you see instead?
<pre>
ssh: handshake failed: knownhosts: key mismatch
</pre>
In my test, I added a fake key of the same type and hostname. If the valid key was first, it worked fine. Anything else would fail.

I noticed this from crypto/ssh/knownhosts/knownhosts.go:
<pre>
func (db *hostKeyDB) checkAddr(a addr, remoteKey ssh.PublicKey) error {
	// TODO(hanwen): are these the right semantics? What if there
	// is just a key for the IP address, but not for the
	// hostname?

	// Algorithm => key.
	knownKeys := map[string]KnownKey{}
	for _, l := range db.lines {
		if l.match(a) {
			typ := l.knownKey.Key.Type()
			if _, ok := knownKeys[typ]; !ok {
				knownKeys[typ] = l.knownKey
			}
		}
}
</pre>
Which will only look at the first key of a given type. To work around this, I added another key type for the other server and it worked fine. However, I think this should handle multiple key/type combinations.