Comment 0 for bug 1790963

Users are unable to connect to Ubuntu when using openssh client 7.8. We have seen this with both xenial and bionic, but this affects connecting to ANY host running openssh <7.8.

The only known recourse at this time is either downgrade clients to 7.7 or a previous version of openssh, or create new keys/certificates with a different alg that is acceptable for both the older server and newer client.

The error message via ssh -vvv is:
debug1: Next authentication method: publickey
debug1: Offering public key: RSA SHA256:REDACTED
debug1: send_pubkey_test: no mutual signature algorithm

It appears that the change noted here in the release notes[1] for 7.8 is related:
 * sshd(8): the semantics of PubkeyAcceptedKeyTypes and the similar
   HostbasedAcceptedKeyTypes options have changed. These now specify
   signature algorithms that are accepted for their respective
   authentication mechanism, where previously they specified accepted
   key types. This distinction matters when using the RSA/SHA2
   signature algorithms "rsa-sha2-256", "rsa-sha2-512" and their
   certificate counterparts. Configurations that override these
   options but omit these algorithm names may cause unexpected
   authentication failures (no action is required for configurations
   that accept the default for these options).

This is also affecting other Linux distributions as well:
https://bugzilla.redhat.com/show_bug.cgi?id=1623929
https://bugs.archlinux.org/task/59838

[1] https://www.openssh.com/releasenotes.html