openssh 8.8 breaks login to Canonical servers

It says

Incompatibility is more likely when connecting to older SSH
implementations that have not been upgraded or have not closely tracked
improvements in the SSH protocol. For these cases, it may be necessary
to selectively re-enable RSA/SHA1 to allow connection and/or user
authentication via the HostkeyAlgorithms and PubkeyAcceptedAlgorithms
options. For example, the following stanza in ~/.ssh/config will enable
RSA/SHA1 for host and user authentication for a single destination host:

    Host old-host
        HostkeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

So this may be a server too old issue; and we can fix this in internal tooling.

Question we have to ask: Is breaking support for old servers without a deprecation notice in the LTS release the best cause of action?

No, I'm not going to undo this. IS shouldn't be running a pre-xenial OpenSSH on xenial machines in the first place, and it's good to fix that; and anything older than that is well out of support anyway.

Also, regarding the "without a deprecation notice" claim, this has been advertised under "Future deprecation notice" in the OpenSSH release notes since 8.2.

We generally expect programs to print a depreciation notice to stderr and not just hide them in release notes, that we, as downstream users don't read :)

If it doesn't warn during use, it's not properly deprecated.

For reference to anyone coming here with this problem, when connecting to a remote sshd server you can find what host key algorithms the remote host uses by using -vv and check the debug output; look first for the *peer* server KEXINIT proposal (not the earlier *local client* KEXINIT proposal):

debug2: peer server KEXINIT proposal

a line or two after that, you should see the list of host key algorithms the remote host is offering; if it contains *only* ssh-rsa then this bug is relevant.

debug2: host key algorithms: ssh-rsa

Note that by default many systems support multiple algorithms, e.g. you may see:

debug2: host key algorithms: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519

in this case, even though the remote host does offer ssh-rsa, it also supports other algorithms that jammy does support.

interestingly, paramiko is also broken when connecting to older servers, but not for the same reason as this bug. See bug 1973241

Note: this also affects anyone trying to connect to the dev.azure.com servers (to, for example, git clone <email address hidden>...)

$ ssh -vv ssh.dev.azure.com
...
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha256
debug2: host key algorithms: ssh-rsa
...
Unable to negotiate with 20.41.6.2 port 22: no matching host key type found. Their offer: ssh-rsa