plumbing: transport/ssh, auto-populate ClientConfig.HostKeyAlgorithms. Fixes #411

This commit adjusts the transport/ssh logic in command.connect(), so that it
now auto-populates ssh.ClientConfig.HostKeyAlgorithms. The algorithms are
chosen based on the known host keys for the target host, as obtained from the
known_hosts file.

In order to look-up the algorithms from the known_hosts file, external module
github.com/skeema/knownhosts is used. This package is just a thin wrapper
around golang.org/x/crypto/ssh/knownhosts, adding an extra mechanism to query
the known_hosts keys, implemented in a way which avoids duplication of any
golang.org/x/crypto/ssh/knownhosts logic.

Because HostKeyAlgorithms vary by target host, some related logic for setting
HostKeyCallback has been moved out of the various AuthMethod implementations.
This was necessary because the old HostKeyCallbackHelper is not host-specific.
Since known_hosts handling isn't really tied to AuthMethod anyway, it seems
reasonable to separate these. Previously-exported types/methods remain in
place for backwards compat, but some of them are now unused.

For testing approach, see pull request. Issue #411 can only be reproduced
via end-to-end / integration testing, since it requires actually launching
an SSH connection, in order to see the key mismatch error triggered from
https://github.com/golang/go/issues/29286 as the root cause.

4 files changed, 55 insertions, 25 deletions

diff --git a/go.mod b/go.mod
index 1f0ceaf..68bafbd 100644
--- a/go.mod
+++ b/go.mod
@@ -17,11 +17,12 @@ require (
 	github.com/jessevdk/go-flags v1.5.0
 	github.com/kevinburke/ssh_config v0.0.0-20201106050909-4977a11b4351
 	github.com/sergi/go-diff v1.1.0
+	github.com/skeema/knownhosts v1.1.0
 	github.com/xanzy/ssh-agent v0.3.1
-	golang.org/x/crypto v0.0.0-20210711020723-a769d52b0f97
-	golang.org/x/net v0.0.0-20210326060303-6b1517762897
+	golang.org/x/crypto v0.0.0-20220525230936-793ad666bf5e
+	golang.org/x/net v0.0.0-20211112202133-69e39bad7dc2
 	golang.org/x/sys v0.0.0-20210630005230-0f9fa26af87c
-	golang.org/x/text v0.3.3
+	golang.org/x/text v0.3.6
 	gopkg.in/check.v1 v1.0.0-20201130134442-10cb98267c6c
 	gopkg.in/warnings.v0 v0.1.2 // indirect
 )
diff --git a/go.sum b/go.sum
index c4295c5..4bda7c4 100644
--- a/go.sum
+++ b/go.sum
@@ -51,6 +51,8 @@ github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZN
 github.com/sergi/go-diff v1.1.0 h1:we8PVUC3FE2uYfodKH/nBHMSetSfHDR6scGdBi+erh0=
 github.com/sergi/go-diff v1.1.0/go.mod h1:STckp+ISIX8hZLjrqAeVduY0gWCT9IjLuqbuNXdaHfM=
 github.com/sirupsen/logrus v1.7.0/go.mod h1:yWOB1SBYBC5VeMP7gHvWumXLIWorT60ONWic61uBYv0=
+github.com/skeema/knownhosts v1.1.0 h1:Wvr9V0MxhjRbl3f9nMnKnFfiWTJmtECJ9Njkea3ysW0=
+github.com/skeema/knownhosts v1.1.0/go.mod h1:sKFq3RD6/TKZkSWn8boUbDC7Qkgcv+8XXijpFO6roag=
 github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
 github.com/stretchr/testify v1.2.2/go.mod h1:a8OnRcib4nhh0OaRAV+Yts87kKdq0PP7pXfy6kDkUVs=
 github.com/stretchr/testify v1.4.0/go.mod h1:j7eGeouHqKxXV5pUuKE4zz7dFj8WfuZ+81PSLYec5m4=
@@ -59,24 +61,26 @@ github.com/stretchr/testify v1.7.0/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/
 github.com/xanzy/ssh-agent v0.3.1 h1:AmzO1SSWxw73zxFZPRwaMN1MohDw8UyHnmuxyceTEGo=
 github.com/xanzy/ssh-agent v0.3.1/go.mod h1:QIE4lCeL7nkC25x+yA3LBIYfwCc1TFziCtG7cBAac6w=
 golang.org/x/crypto v0.0.0-20210322153248-0c34fe9e7dc2/go.mod h1:T9bdIzuCu7OtxOm1hfPfRQxPLYneinmdGuTeoZ9dtd4=
-golang.org/x/crypto v0.0.0-20210711020723-a769d52b0f97 h1:/UOmuWzQfxxo9UtlXMwuQU8CMgg1eZXqTRwkSQJWKOI=
 golang.org/x/crypto v0.0.0-20210711020723-a769d52b0f97/go.mod h1:GvvjBRRGRdwPK5ydBHafDWAxML/pGHZbMvKqRZ5+Abc=
+golang.org/x/crypto v0.0.0-20220525230936-793ad666bf5e h1:T8NU3HyQ8ClP4SEE+KbFlg6n0NhuTsN4MyznaarGsZM=
+golang.org/x/crypto v0.0.0-20220525230936-793ad666bf5e/go.mod h1:IxCIyHEi3zRg3s0A5j5BB6A9Jmi73HwBIUl50j+osU4=
 golang.org/x/net v0.0.0-20210226172049-e18ecbb05110/go.mod h1:m0MpNAwzfU5UDzcl9v0D8zg8gWTRqZa9RBIspLL5mdg=
-golang.org/x/net v0.0.0-20210326060303-6b1517762897 h1:KrsHThm5nFk34YtATK1LsThyGhGbGe1olrte/HInHvs=
-golang.org/x/net v0.0.0-20210326060303-6b1517762897/go.mod h1:uSPa2vr4CLtc/ILN5odXGNXS6mhrKVzTaCXzk9m6W3k=
+golang.org/x/net v0.0.0-20211112202133-69e39bad7dc2 h1:CIJ76btIcR3eFI5EgSo6k1qKw9KJexJuRLI9G7Hp5wE=
+golang.org/x/net v0.0.0-20211112202133-69e39bad7dc2/go.mod h1:9nx3DQGgdP8bBQD5qxJ1jj9UTztislL4KSBs9R2vV5Y=
 golang.org/x/sys v0.0.0-20191026070338-33540a1f6037/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200302150141-5c8b2ff67527/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210124154548-22da62e12c0c/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210320140829-1e4c9ba3b0c4/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
-golang.org/x/sys v0.0.0-20210324051608-47abb6519492/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20210423082822-04245dca01da/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20210630005230-0f9fa26af87c h1:F1jZWGFhYfh0Ci55sIpILtKKK8p3i2/krTr0H1rg74I=
 golang.org/x/sys v0.0.0-20210630005230-0f9fa26af87c/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1 h1:v+OssWQX+hTHEmOBgwxdZxK4zHq3yOs8F9J7mk0PY8E=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
-golang.org/x/text v0.3.3 h1:cokOdA+Jmi5PJGXLlLllQSgYigAEfHXJAERHVMaCc2k=
 golang.org/x/text v0.3.3/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
+golang.org/x/text v0.3.6 h1:aRYxNxv6iGQlyVaZmk6ZgYEDa+Jg18DxebPSrd6bg1M=
+golang.org/x/text v0.3.6/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
 golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
diff --git a/plumbing/transport/ssh/auth_method.go b/plumbing/transport/ssh/auth_method.go
index b4959d6..9d3bcd3 100644
--- a/plumbing/transport/ssh/auth_method.go
+++ b/plumbing/transport/ssh/auth_method.go
@@ -10,9 +10,9 @@ import (
 
 	"github.com/go-git/go-git/v5/plumbing/transport"
 
+	"github.com/skeema/knownhosts"
 	sshagent "github.com/xanzy/ssh-agent"
 	"golang.org/x/crypto/ssh"
-	"golang.org/x/crypto/ssh/knownhosts"
 )
 
 const DefaultUsername = "git"
@@ -43,7 +43,6 @@ const (
 type KeyboardInteractive struct {
 	User      string
 	Challenge ssh.KeyboardInteractiveChallenge
-	HostKeyCallbackHelper
 }
 
 func (a *KeyboardInteractive) Name() string {
@@ -55,19 +54,18 @@ func (a *KeyboardInteractive) String() string {
 }
 
 func (a *KeyboardInteractive) ClientConfig() (*ssh.ClientConfig, error) {
-	return a.SetHostKeyCallback(&ssh.ClientConfig{
+	return &ssh.ClientConfig{
 		User: a.User,
 		Auth: []ssh.AuthMethod{
 			a.Challenge,
 		},
-	})
+	}, nil
 }
 
 // Password implements AuthMethod by using the given password.
 type Password struct {
 	User     string
 	Password string
-	HostKeyCallbackHelper
 }
 
 func (a *Password) Name() string {
@@ -79,10 +77,10 @@ func (a *Password) String() string {
 }
 
 func (a *Password) ClientConfig() (*ssh.ClientConfig, error) {
-	return a.SetHostKeyCallback(&ssh.ClientConfig{
+	return &ssh.ClientConfig{
 		User: a.User,
 		Auth: []ssh.AuthMethod{ssh.Password(a.Password)},
-	})
+	}, nil
 }
 
 // PasswordCallback implements AuthMethod by using a callback
@@ -90,7 +88,6 @@ func (a *Password) ClientConfig() (*ssh.ClientConfig, error) {
 type PasswordCallback struct {
 	User     string
 	Callback func() (pass string, err error)
-	HostKeyCallbackHelper
 }
 
 func (a *PasswordCallback) Name() string {
@@ -102,17 +99,16 @@ func (a *PasswordCallback) String() string {
 }
 
 func (a *PasswordCallback) ClientConfig() (*ssh.ClientConfig, error) {
-	return a.SetHostKeyCallback(&ssh.ClientConfig{
+	return &ssh.ClientConfig{
 		User: a.User,
 		Auth: []ssh.AuthMethod{ssh.PasswordCallback(a.Callback)},
-	})
+	}, nil
 }
 
 // PublicKeys implements AuthMethod by using the given key pairs.
 type PublicKeys struct {
 	User   string
 	Signer ssh.Signer
-	HostKeyCallbackHelper
 }
 
 // NewPublicKeys returns a PublicKeys from a PEM encoded private key. An
@@ -151,10 +147,10 @@ func (a *PublicKeys) String() string {
 }
 
 func (a *PublicKeys) ClientConfig() (*ssh.ClientConfig, error) {
-	return a.SetHostKeyCallback(&ssh.ClientConfig{
+	return &ssh.ClientConfig{
 		User: a.User,
 		Auth: []ssh.AuthMethod{ssh.PublicKeys(a.Signer)},
-	})
+	}, nil
 }
 
 func username() (string, error) {
@@ -177,7 +173,6 @@ func username() (string, error) {
 type PublicKeysCallback struct {
 	User     string
 	Callback func() (signers []ssh.Signer, err error)
-	HostKeyCallbackHelper
 }
 
 // NewSSHAgentAuth returns a PublicKeysCallback based on a SSH agent, it opens
@@ -212,10 +207,10 @@ func (a *PublicKeysCallback) String() string {
 }
 
 func (a *PublicKeysCallback) ClientConfig() (*ssh.ClientConfig, error) {
-	return a.SetHostKeyCallback(&ssh.ClientConfig{
+	return &ssh.ClientConfig{
 		User: a.User,
 		Auth: []ssh.AuthMethod{ssh.PublicKeysCallback(a.Callback)},
-	})
+	}, nil
 }
 
 // NewKnownHostsCallback returns ssh.HostKeyCallback based on a file based on a
@@ -231,6 +226,11 @@ func (a *PublicKeysCallback) ClientConfig() (*ssh.ClientConfig, error) {
 //	~/.ssh/known_hosts
 //	/etc/ssh/ssh_known_hosts
 func NewKnownHostsCallback(files ...string) (ssh.HostKeyCallback, error) {
+	kh, err := newKnownHosts(files...)
+	return ssh.HostKeyCallback(kh), err
+}
+
+func newKnownHosts(files ...string) (knownhosts.HostKeyCallback, error) {
 	var err error
 
 	if len(files) == 0 {
@@ -286,6 +286,9 @@ func filterKnownHostsFiles(files ...string) ([]string, error) {
 
 // HostKeyCallbackHelper is a helper that provides common functionality to
 // configure HostKeyCallback into a ssh.ClientConfig.
+// Deprecated in favor of SetConfigHostKeyFields (see common.go) which provides
+// a mechanism for also setting ClientConfig.HostKeyAlgorithms for a specific
+// host.
 type HostKeyCallbackHelper struct {
 	// HostKeyCallback is the function type used for verifying server keys.
 	// If nil default callback will be create using NewKnownHostsCallback
diff --git a/plumbing/transport/ssh/common.go b/plumbing/transport/ssh/common.go
index 46e7913..4b9ac07 100644
--- a/plumbing/transport/ssh/common.go
+++ b/plumbing/transport/ssh/common.go
@@ -121,10 +121,15 @@ func (c *command) connect() error {
 	if err != nil {
 		return err
 	}
+	hostWithPort := c.getHostWithPort()
+	config, err = SetConfigHostKeyFields(config, hostWithPort)
+	if err != nil {
+		return err
+	}
 
 	overrideConfig(c.config, config)
 
-	c.client, err = dial("tcp", c.getHostWithPort(), config)
+	c.client, err = dial("tcp", hostWithPort, config)
 	if err != nil {
 		return err
 	}
@@ -162,6 +167,23 @@ func dial(network, addr string, config *ssh.ClientConfig) (*ssh.Client, error) {
 	return ssh.NewClient(c, chans, reqs), nil
 }
 
+// SetConfigHostKeyFields sets cfg.HostKeyCallback and cfg.HostKeyAlgorithms
+// based on OpenSSH known_hosts. cfg is modified in-place. hostWithPort must be
+// supplied, since the algorithms will be set based on the known host keys for
+// that specific host. Otherwise, golang.org/x/crypto/ssh can return an error
+// upon connecting to a host whose *first* key is not known, even though other
+// keys (of different types) are known and match properly.
+// For background see https://github.com/go-git/go-git/issues/411 as well as
+// https://github.com/golang/go/issues/29286 for root cause.
+func SetConfigHostKeyFields(cfg *ssh.ClientConfig, hostWithPort string) (*ssh.ClientConfig, error) {
+	kh, err := newKnownHosts()
+	if err == nil {
+		cfg.HostKeyCallback = kh.HostKeyCallback()
+		cfg.HostKeyAlgorithms = kh.HostKeyAlgorithms(hostWithPort)
+	}
+	return cfg, err
+}
+
 func (c *command) getHostWithPort() string {
 	if addr, found := c.doGetHostWithPortFromSSHConfig(); found {
 		return addr