x/crypto/ssh: "ssh-rsa-cert-v01@openssh.com" does not work for sshd OpenSSH 7.2-7.7

[masp]

What version of Go are you using (go version)?

$ go version
go version go1.20 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
> go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/masp/Library/Caches/go-build"
GOENV="/Users/masp/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/masp/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/masp/go"
GOPRIVATE=""
GOPROXY="direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.20"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="..."
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/zy/mh971c6s3q31kqyyfzrh_y79ztk14w/T/go-build2848549523=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

I have an OpenSSH server version 7.4p1.

sshd -V
OpenSSH_7.4p1, OpenSSL 1.0.2k-fips  26 Jan 2017

I have the below program which works with golang.org/x/crypto/ssh in Go version 1.17 but not the latest tagged version 0.5.0.

main.goCode

package main

import (
	"log"
	"os"
	"time"

	"golang.org/x/crypto/ssh"
)

func main() {
	pubkeybytes, err := os.ReadFile("/Users/masp/.ssh/id_rsa-cert.pub")
	if err != nil {
		log.Fatalf("could not read keyfile: %v", err)
	}
	privkeybytes, err := os.ReadFile("/Users/masp/.ssh/id_rsa")
	if err != nil {
		log.Fatalf("could not read keyfile: %v", err)
	}
	pubkey, _, _, _, err := ssh.ParseAuthorizedKey(pubkeybytes)
	if err != nil {
		log.Fatalf("could not parse public key: %v", err)
	}
	privkey, err := ssh.ParsePrivateKey(privkeybytes)
	if err != nil {
		log.Fatalf("could not parse private key: %v", err)
	}
	signer, err := ssh.NewCertSigner(pubkey.(*ssh.Certificate), privkey)
	if err != nil {
		log.Fatalf("could not create signer: %v", err)
	}
	config := &ssh.ClientConfig{
		User:            "masp",
		Auth:            []ssh.AuthMethod{ssh.PublicKeys(signer)},
		Timeout:         time.Second * 10,
		HostKeyCallback: ssh.InsecureIgnoreHostKey(),
	}

	device := "openssh-7.4p1-test-host:22"
	_, err = ssh.Dial("tcp", device, config)
	if err != nil {
		log.Fatalf("dial error: %v", err)
	}
	log.Printf("OK")
}

What did you expect to see?

I expect it to dial successfully as it did in previous versions 0.4.0.

What did you see instead?

> go run main.go
2023/02/06 17:47:43 dial error: ssh: handshake failed: ssh: unable to authenticate, attempted methods [none publickey], no supported methods remain

Debugging and Root Cause

After investigating to try and understand what was the issue, I found the following behavior.

OpenSSH 7.2: Supports rsa-sha2-256/512 alternatives, and shares those two with the client
OpenSSH 7.8: Adds support for the certificate versions of rsa-sha2-256 which are rsa-sha2-256-cert-v01@openssh.com and rsa-sha2-512-cert-v01@openssh.com. Important to note that the server does not broadcast these.

In the latest code, the server's SSH_MSG_EXT_INFO contains only rsa-sha2-256 without the certificate variants, which is why the code correctly adds those to the list of supported for those versions.

However, this breaks the fallback mechanisms if the client is using ssh-rsa-cert-v01@openssh.com, because it incorrectly identifies the server as supporting SHA2 certificates, when in reality it only supports SHA2 keys. Because of this, the client tries to get the key verified with the server, and the server rejects it which causes the permission denied error. What should happen is the client still tries the SHA1 certificate if the SHA2 one fails.

Because the library does not support any kind of configuring of signatures, I reproduced it with OpenSSH client:

> ssh -V
OpenSSH_9.2p1, OpenSSL 1.1.1s  1 Nov 2022

> ssh -Q sig
ssh-ed25519
sk-ssh-ed25519@openssh.com
ecdsa-sha2-nistp256
ecdsa-sha2-nistp384
ecdsa-sha2-nistp521
sk-ecdsa-sha2-nistp256@openssh.com
webauthn-sk-ecdsa-sha2-nistp256@openssh.com
ssh-dss
ssh-rsa
<--- NO ssh-rsa support!
rsa-sha2-256
rsa-sha2-512

Output

> ssh openssh-7.4p1-test-host -v -F /dev/null
debug1: send_pubkey_test: no mutual signature algorithm
masp@openssh-7.4p1-test-host: Permission denied (publickey)

Manually adding support for certificate:

ssh openssh-7.4p1-test-host -o "pubkeyacceptedalgorithms=+ssh-rsa,ssh-rsa-cert-v01@openssh.com" hostname
openssh-7.4p1-test-host 

Related

#56342 - seems to be a similar result, but different root causes

[dr2chase]

@golang/security can you give this a look?