Summary:
* Before the OpenSSH release that ships the deprecation, we need to upgrade every prod host and network device to at least OpenSSH [7.2p1, 7.4p1) or to >=7.5p1, or backport a single patch to 7.4p1.
** 7.4p1 -- the version in Stretch -- is itself buggy in a way that affects the deprecation, fixed in [[ https://github.com/openssh/openssh-portable/commit/183ba55aaaecca0206184b854ad6155df237adbe | this patch ]] released in 7.5p1
** Unless that patch (or a release 7.5p1 or later) is backported to Stretch, I am pretty confident that post-deprecation clients will not be able to negotiate RSA host keys or user public keys with Stretch servers.
** Post-deprecation clients will not be able to negotiate RSA host keys or user public keys with Jessie servers.
* Just in case there's any confusion about the nomenclature here, we do //not// need to stop accepting `ssh-rsa` public keys; it's only the authentication algorithm being deprecated (see below).
---
Upstream announcement: https://www.openssh.com/txt/release-8.3
>It is now possible[1] to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K. For this reason, we will be disabling the "ssh-rsa" public key signature algorithm by default in a near-future release.
NB that this //isn't// a deprecation of RSA, or of `ssh-rsa` keypairs themselves -- only of the over-the-wire verification algorithm of "RSA coupled with SHA-1", which confusingly is also named `ssh-rsa`.
Helpfully, [[ https://tools.ietf.org/html/rfc8332 | RFC8332 ]] provides two other verification algorithms that use the exact same keys, including using identical public/private keyfiles, including `ssh-rsa` as a prefix of the public keys. Those algorithms are `rsa-sha2-256` and `rsa-sha2-512` and they are exactly what they sound like. As of OpenSSH 7.2p1, they are implemented and automatically used when available.
Somewhat confusingly, it isn't until [[ https://github.com/openssh/openssh-portable/commit/4ba0d54794814ec0de1ec87987d0c3b89379b436 | this patch ]] lands in 7.9p1 in which those names become meaningful for anything except the HostKeyAlgorithms, despite the fact that they should be meaningful for HostbasedKeyTypes and PubkeyAcceptedKeyTypes.
In versions from [[ https://github.com/openssh/openssh-portable/commit/76c9fbbe35aabc1db977fb78e827644345e9442e | 7.2p1 ]] until 7.9p1, they're simply an [[ https://tools.ietf.org/html/rfc8308 | extra part of the key exchange added in a protocol extension]] that is transparent to older clients and servers -- but pre-7.9p1, it's not possible to write a configuration file asking to deny the older RSA-SHA1 verification, which isn't a huge deal but is worth noting.
What //is// a problem is that 7.4p1 (in Stretch) had a bug introduced in it where `sshd` does //not// enumerate `rsa-sha2-256` or `rsa-sha2-512` as possible signature algorithms in the `server-sig-algs` extension to key exchanged. The bug was introduced by this [[ https://github.com/openssh/openssh-portable/commit/130f5df4fa37cace8c079dccb690e5cafbf00751 | innocuous-looking cleanup patch ]]. The [[ https://github.com/openssh/openssh-portable/commit/183ba55aaaecca0206184b854ad6155df237adbe | fix ]] landed in 7.5p1.
It's possible to demonstrate this via the following. On a Buster or other modern host, and using an RSA pubkey for yourself, disable `ssh-rsa` and attempt to authenticate to a Stretch host:
```
% ssh bast1002.wikimedia.org
Linux bast1002 4.9.0-9-amd64 #1 SMP Debian 4.9.168-1+deb9u3 (2019-06-16) x86_64
^D
% ssh -o PubkeyAcceptedKeyTypes=-ssh-rsa bast1002.wikimedia.org
Password: ^C
% ssh -o PubkeyAcceptedKeyTypes=-ssh-rsa -vvv bast1002.wikimedia.org |& grep server-sig-alg
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521>
^C
% ssh -o PubkeyAcceptedKeyTypes=-ssh-rsa -vvv localhost |& grep server-sig-alg
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,ssh-rsa,rsa-sha2-256,rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521>
```
You can also inspect the signature algorithm being selected:
```
% ssh -vvv bast1002.wikimedia.org |& grep sign_and_send_pubkey
debug3: sign_and_send_pubkey: RSA SHA256:I9DIoOoVwPiPODdlJiLGWQTN5+MC9oWbiYkkKQbg2q4
debug3: sign_and_send_pubkey: signing using ssh-rsa
% ssh -vvv localhost |& grep sign_and_send_pubkey
debug3: sign_and_send_pubkey: RSA SHA256:I9DIoOoVwPiPODdlJiLGWQTN5+MC9oWbiYkkKQbg2q4
debug3: sign_and_send_pubkey: signing using rsa-sha2-512
```
It's probably worth verifying all this with OpenSSH upstream, and then asking them to clarify their release notes, as I don't believe 7.4p1 servers will be compatible with post-deprecation clients -- but they presently state that 7.2p1 or later is all that is necessary to be compatible on either end.
I'm not sure if Debian themselves would want to patch their 1:7.4p1-10+deb9u7 of openssh-server, even though Stretch is oldstable, but it might be a good idea as well.