x/crypto: regression: no longer able to authenticate using rsa-sha2-512 key

[kprav33n]

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

$ go version
go version go1.19.2 linux/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
GO111MODULE="on"
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/praveen/.cache/go-build"
GOENV="/home/praveen/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/local/praveen/go/pkg/mod"
GONOPROXY="redacted-host"
GONOSUMDB="redacted-host"
GOOS="linux"
GOPATH="/local/praveen/go"
GOPRIVATE="redacted-host"
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/praveen/sdk/go1.19.2"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/praveen/sdk/go1.19.2/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.19.2"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/local/praveen/src/crypto/go.mod"
GOWORK=""
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 -Wl,--no-gc-sections -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3315967625=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Authenticating to SSH server using rsa-sha2-512 used to work fine with in my Go program when I was using golang.org/x/crypto v0.0.0-20220128200615-198e4374d7ed. However, after upgrading to the latest (v0.1.0) crypto, the same program is unable to authenticate successfully anymore. I narrowed down the regression to a particular commit 5d542ad81a58c89581d596f49d0ba5d435481bcf. Key was generated using ssh-keygen -t rsa-sha2-512. (openssh version 8.9p1-3 on Ubuntu jammy). SSH server used was Github enterprise edition (SSH-2.0-babeld-5f3a6bb).

I have provided a test program to reproduce the issue below.

What did you expect to see?

Successful connection to the SSH server using the provided rsa-sha2-512 key.

What did you see instead?

Following error returned from the crypto library.

ssh: handshake failed: ssh: unable to authenticate, attempted methods [none publickey], no supported methods remain

Go Program to Reproduce/Bisect

Placed the following program in cmd/sshauthtest/main.go under the local crypto git repo checked out based on v0.1.0 tag.

Note: I have redacted the username, hostname and key file path. Needs to be populated by the developer when reproducing the issue.

package main

import (
	"fmt"
	"net"
	"os"

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

func main() {
	user := "***REDACTED***"
	host := "***REDACTED***"
	keyFilePath := "***REDACTED***"

	keyBytes, err := os.ReadFile(keyFilePath)
	if err != nil {
		fmt.Fprintf(os.Stderr, "failed to read private key file %s: %s", keyFilePath, err)
		os.Exit(1)
	}

	signer, err := ssh.ParsePrivateKey(keyBytes)
	if err != nil {
		fmt.Fprintf(os.Stderr, "failed to parse private key file %s: %s", keyFilePath, err)
		os.Exit(1)
	}

	config := &ssh.ClientConfig{
		User: user,
		Auth: []ssh.AuthMethod{
			ssh.PublicKeys(signer),
		},
		HostKeyCallback: func(string, net.Addr, ssh.PublicKey) error {
			return nil
		},
	}

	if _, err := ssh.Dial("tcp", host, config); err != nil {
		fmt.Fprintf(os.Stderr, "failed to connect to %s: %s", host, err)
		os.Exit(1)
	}

	fmt.Printf("successfully connected to %s\n", host)
}

Git Bisection Result

$ git show --stat
commit 642fcc37f5043eadb2509c84b2769e729e7d27ef (HEAD -> master, tag: v0.1.0, origin/master, origin/HEAD)
Author: Gopher Robot <gobot@golang.org>
Date:   Wed Oct 19 15:40:49 2022 +0000

    go.mod: update golang.org/x dependencies

    Update golang.org/x dependencies to their latest tagged versions.
    Once this CL is submitted, and post-submit testing succeeds on all
    first-class ports across all supported Go versions, this repository
    will be tagged with its next minor version.

    Change-Id: If840eea1cadc749ce55efd88eb7d9fc38472839e
    Reviewed-on: https://go-review.googlesource.com/c/crypto/+/443996
    Auto-Submit: Gopher Robot <gobot@golang.org>
    Reviewed-by: Roland Shoemaker <roland@golang.org>
    Reviewed-by: Heschi Kreinick <heschi@google.com>
    TryBot-Result: Gopher Robot <gobot@golang.org>
    Run-TryBot: Gopher Robot <gobot@golang.org>

 go.mod |  8 ++++----
 go.sum | 34 +++++++++++++++++++++++++++-------
 2 files changed, 31 insertions(+), 11 deletions(-)

$ git bisect start HEAD 198e4374d7ed
Bisecting: 23 revisions left to test after this (roughly 5 steps)
[5352b09029215197cc109b46f0560d05ffab29db] acme/autocert: support External Account Binding (EAB) tokens

$ git bisect run go run ./cmd/sshauthtest
running  'go' 'run' './cmd/sshauthtest'
failed to connect to redacted-host:22: ssh: handshake failed: ssh: unable to authenticate, attempted methods [none publickey], no supported methods remainexit status 1
Bisecting: 11 revisions left to test after this (roughly 4 steps)
[6068a2e6cfdc895ce524b6d2bdc8ea0cea8ea0e8] ssh: ignore MAC if AEAD ciphers negotiated
running  'go' 'run' './cmd/sshauthtest'
successfully connected to redacted-host:22
Bisecting: 5 revisions left to test after this (roughly 3 steps)
[1baeb1ce4c0b006eff0f294c47cb7617598dfb3d] ssh: don't advertise rsa-sha2 algorithms if we can't use them
running  'go' 'run' './cmd/sshauthtest'
successfully connected to redacted-host:22
Bisecting: 2 revisions left to test after this (roughly 2 steps)
[3147a52a75dda54ac3a611ef8978640d85188a2a] ssh: support rsa-sha2-256/512 for client certificates
running  'go' 'run' './cmd/sshauthtest'
failed to connect to redacted-host:22: ssh: handshake failed: ssh: unable to authenticate, attempted methods [none publickey], no supported methods remainexit status 1
Bisecting: 0 revisions left to test after this (roughly 1 step)
[5d542ad81a58c89581d596f49d0ba5d435481bcf] ssh: support rsa-sha2-256/512 for client authentication
running  'go' 'run' './cmd/sshauthtest'
failed to connect to redacted-host:22: ssh: handshake failed: ssh: unable to authenticate, attempted methods [none publickey], no supported methods remainexit status 1
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[a5774263c1e06050d4c71b5794b2b5a321289a8f] ssh: send (and rename) keyboard-interactive name field to the client
running  'go' 'run' './cmd/sshauthtest'
successfully connected to redacted-host:22
5d542ad81a58c89581d596f49d0ba5d435481bcf is the first bad commit
commit 5d542ad81a58c89581d596f49d0ba5d435481bcf
Author: Filippo Valsorda <filippo@golang.org>
Date:   Mon Mar 14 10:48:13 2022 -0400

    ssh: support rsa-sha2-256/512 for client authentication

    CL 220037 had implemented support for host authentication using
    rsa-sha2-256/512, but not client public key authentication. OpenSSH
    disabled the SHA-1 based ssh-rsa by default in version 8.8 (after
    pre-announcing it in versions 8.2, 8.3, 8.4, 8.5, 8.6, and 8.7) although
    some distributions re-enable it. GitHub will start rejecting ssh-rsa for
    keys uploaded before November 2, 2021 on March 15, 2022.

    https://github.blog/2021-09-01-improving-git-protocol-security-github/

    The server side already worked, as long as the client selected one of
    the SHA-2 algorithms, because the signature flowed freely to Verify.
    There was however nothing verifying that the signature algorithm matched
    the advertised one. The comment suggested the check was being performed,
    but it got lost back in CL 86190043. Not a security issue because the
    signature had to pass the callback's Verify method regardless, and both
    values were checked to be acceptable.

    Tested with OpenSSH 8.8 configured with "PubkeyAcceptedKeyTypes -ssh-rsa"
    and no application-side changes.

    The Signers returned by ssh/agent (when backed by an agent client)
    didn't actually implement AlgorithmSigner but ParameterizedSigner, an
    interface defined in an earlier version of CL 123955.

    Updates golang/go#49269
    Fixes golang/go#39885
    For golang/go#49952

    Change-Id: I13b41db8041f1112a70f106c55f077b904b12cb8
    Reviewed-on: https://go-review.googlesource.com/c/crypto/+/392394
    Trust: Filippo Valsorda <filippo@golang.org>
    Run-TryBot: Filippo Valsorda <filippo@golang.org>
    TryBot-Result: Gopher Robot <gobot@golang.org>
    Reviewed-by: Roland Shoemaker <roland@golang.org>

 ssh/agent/client.go     |  24 ++++++----
 ssh/client_auth.go      | 116 +++++++++++++++++++++++++++++++++++++++---------
 ssh/client_auth_test.go |  54 +++++++++++++++++++++-
 ssh/common.go           |   7 +--
 ssh/handshake.go        |   7 +++
 ssh/messages.go         |  11 +++++
 ssh/server.go           |   8 +++-
 7 files changed, 192 insertions(+), 35 deletions(-)
bisect found first bad commit

Additional Debug Information

CC: @FiloSottile

I tried to debug further and narrowed down the difference in behavior to x/crypto/ssh.confirmKeyAck function, which thinks that there is a mismatch between the algorithm used by the client and responded by the server. Note the additional fmt.Printf that I added under case msgUserAuthPubKeyOk.

func confirmKeyAck(key PublicKey, algo string, c packetConn) (bool, error) {
	pubKey := key.Marshal()

	for {
		packet, err := c.readPacket()
		if err != nil {
			return false, err
		}
		switch packet[0] {
		case msgUserAuthBanner:
			if err := handleBannerResponse(c, packet); err != nil {
				return false, err
			}
		case msgUserAuthPubKeyOk:
			var msg userAuthPubKeyOkMsg
			if err := Unmarshal(packet, &msg); err != nil {
				return false, err
			}
			fmt.Printf("msg.Algo: %s, algo: %s\n", msg.Algo, algo)
			if msg.Algo != algo || !bytes.Equal(msg.PubKey, pubKey) {
				return false, nil
			}
			return true, nil
		case msgUserAuthFailure:
			return false, nil
		default:
			return false, unexpectedMessageError(msgUserAuthPubKeyOk, packet[0])
		}
	}
}

In the failing case, it produces the following output.

msg.Algo: ssh-rsa, algo: rsa-sha2-256

What is even more interesting is that the algo was reported as rsa-sha2-256 even though it was generated as rsa-sha2-512!

In the succeeding case, both are of value ssh-rsa.

ssh-ed25519 works fine with both the new and old versions of crypto library. As a workaround for now, we are recommending our users to stick with ed25519 keys because of this issue.

[kprav33n]

Probably related to #53391

[dr2chase]

@golang/security can you have a look at this? It smells like a dupe but IANAE.

[idcmp]

FWIW this is only somewhat related - and not dupe of - #53391 as this is the client side (cc @FiloSottile ).

[idcmp]

For my use case, if I patch pickSignatureAlgorithm in client_auth.go to ignore server-sig-algs I seem to be able to get things to work again. (I forced ok=false after it reads extPayload).

I can't speak to the security of doing this though, but it does unblock me until the code is fixed.

[cschelcher]

Indeed, this seems to be a mismatch between key algorithm sent by the client and acknowledged by the server during authentication phase (pubkey).

Checking the RFC 4252 §7 on that point, the public key authentication request sent by the client is:

 byte      SSH_MSG_USERAUTH_REQUEST
 string    user name in ISO-10646 UTF-8 encoding [RFC3629]
 string    service name in US-ASCII
 string    "publickey"
 boolean   FALSE
 string    public key algorithm name
 string    public key blob

In our case the public key algorithm name field is set to rsa-sha2-256 or rsa-sha2-512 by the client.

The server reply as per RFC 4252 §7:

Any public key algorithm may be offered for use in authentication.
In particular, the list is not constrained by what was negotiated
during key exchange. If the server does not support some algorithm,
it MUST simply reject the request.

The server MUST respond to this message with either
SSH_MSG_USERAUTH_FAILURE or with the following:

 byte      SSH_MSG_USERAUTH_PK_OK
 string    public key algorithm name from the request
 string    public key blob from the request

In our case, the public key algorithm name from the request is set to ssh-rsa which is not what the client sent. So, the server seems not being RFC compliant.

However, there is no mention in the RFC that the client MUST, MAY or SHOULD verify these fields from the SSH_MSG_USERAUTH_PK_OK message. In other words, as the server replied with such message, it then indicate that it supports the algorithm sent by the client and accepts the public key.

As a consequence, in the x/crypto/ssh.confirmKeyAck function, skipping the algorithm match check on SSH_MSG_USERAUTH_PK_OK would be a valuable fix to this issue:

func confirmKeyAck(key PublicKey, algo string, c packetConn) (bool, error) {
	pubKey := key.Marshal()

	for {
		packet, err := c.readPacket()
		if err != nil {
			return false, err
		}
		switch packet[0] {
		case msgUserAuthBanner:
			if err := handleBannerResponse(c, packet); err != nil {
				return false, err
			}
		case msgUserAuthPubKeyOk:
			var msg userAuthPubKeyOkMsg
			if err := Unmarshal(packet, &msg); err != nil {
				return false, err
			}
			// if msg.Algo != algo || !bytes.Equal(msg.PubKey, pubKey) {
			if !bytes.Equal(msg.PubKey, pubKey) {
				return false, nil
			}
			return true, nil
		case msgUserAuthFailure:
			return false, nil
		default:
			return false, unexpectedMessageError(msgUserAuthPubKeyOk, packet[0])
		}
	}
}

Removing the algorithm match check improves client interoperability with servers that supports rsa-sha2-256 and rsa-sha2-512 (as per RFC 8303) but their implementation still reports them as ssh-rsa. Most probably a transition phase.

As far as I understand, the algorithm match check here does not improve security and removing it does not degrade it either. The client will then proceed with a SSH_MSG_USERAUTH_REQUEST message including its signature. If the server after all does not support the algorithm, the authentication will fail.

Did I miss something ?
I may be wrong, of course, what do you think ?