Bug 3351

I'm not able to replicate this, either manually or with modifications to regress/cert-userkey.sh to explicitly test this case (though I think it was previously anyway).

Could you please attach debug traces from the client and server to this bug?

Note that RSA SHA256 certificates are always identified as ssh-rsa-cert-v01@openssh.com because key type names are actually somewhat separate to signature algorithm names even though they look the same. So a ssh-rsa-cert-v01@openssh.com certificate can happily make a rsa-sha2-256 signature. (Yes, this is a confusing area of the protocol).

Created attachment 3549 [details]
Client log

Attached client log.

Certificate rejection happens on the client.
In sshconnect2.c this line is executed:

1857:   sent = send_pubkey_test(ssh, id);

Then in send_pubkey_test function this line is executed:

1503:   if ((alg = key_sig_algorithm(ssh, id->key)) == NULL) {

Then in key_sig_algorithm function this line is executed:

1195:   return match_list(sshkey_ssh_name(key),

Here sshkey_ssh_name returns "ssh-rsa-cert-v01@openssh.com" and it is compared against a list which is initialized by KEX_DEFAULT_PK_ALG, which does not contain "ssh-rsa-cert-v01@openssh.com".  That check fails and "no mutual signature supported" error is reported.

I was able to "fix" this problem by adding "ssh-rsa-cert-v01@openssh.com," into KEX_DEFAULT_PK_ALG in myproposal.h

The problem here is the server, not the client. OpenSSH 7.4 has a number of bugs relating to RSA-SHA2 algorithm advertisements.

These are mostly worked around in newer versions for plain keys but we don't do the same for certificates because the compatibility code would be pretty ugly. It's better to simply upgrade the server to a less-old release.

You are right, I tested with 8.8 server and it worked.

Our server is currently on 7.4p1 and this is the latest available from repository.

So this change at least breaks compatibility with 7.4.  Do you know which oldest version supports 8.8 client?

OpenSSH 7.8 definitely works (just tested it). I think the previous versions had varying degrees of buginess

Adding my findings about difference between 7.4 and 8.8

On 7.4 when this condition is executed:
	if (ssh == NULL || ssh->kex->server_sig_algs == NULL ||
	    (key->type != KEY_RSA && key->type != KEY_RSA_CERT) ||
	    (key->type == KEY_RSA_CERT && (ssh->compat & SSH_BUG_SIGTYPE))) {
		/* Filter base key signature alg against our configuration */
		return match_list(sshkey_ssh_name(key),
		    options.pubkey_accepted_algos, NULL);
	}

the ssh->compat is equal 0x4000006, which is causing "ssh->compat & SSH_BUG_SIGTYPE" to be true, and therefore execution enters that if and then match_list returns false, causing rejection.


On 8.8 the ssh->compat is equal 0x4000000, therefore if is bypassed. Then this section:
	oallowed = allowed = xstrdup(options.pubkey_accepted_algos);
	while ((cp = strsep(&allowed, ",")) != NULL) {
		if (sshkey_type_from_name(cp) != key->type)
			continue;
		tmp = match_list(sshkey_sigalg_by_name(cp),
		    server_sig_algs, NULL);
		if (tmp != NULL)
			alg = xstrdup(cp);
		free(tmp);
		if (alg != NULL)
			break;
	}
Which passes.

Most of the fixes were in this commit IIRC:

commit 4ba0d54794814ec0de1ec87987d0c3b89379b436
Author: djm@openbsd.org <djm@openbsd.org>
Date:   Tue Jul 3 11:39:54 2018 +0000

    upstream: Improve strictness and control over RSA-SHA2 signature
    
    In ssh, when an agent fails to return a RSA-SHA2 signature when
    requested and falls back to RSA-SHA1 instead, retry the signature to
    ensure that the public key algorithm sent in the SSH_MSG_USERAUTH
    matches the one in the signature itself.
    
    In sshd, strictly enforce that the public key algorithm sent in the
    SSH_MSG_USERAUTH message matches what appears in the signature.
    
    Make the sshd_config PubkeyAcceptedKeyTypes and
    HostbasedAcceptedKeyTypes options control accepted signature algorithms
    (previously they selected supported key types). This allows these
    options to ban RSA-SHA1 in favour of RSA-SHA2.
    
    Add new signature algorithms "rsa-sha2-256-cert-v01@openssh.com" and
    "rsa-sha2-512-cert-v01@openssh.com" to force use of RSA-SHA2 signatures
    with certificate keys.
    
    feedback and ok markus@
    
    OpenBSD-Commit-ID: c6e9f6d45eed8962ad502d315d7eaef32c419dde

closing bugs resolved before openssh-8.9