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 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, 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 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 7.2p1 until 7.9p1, they're simply an 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 exchanges. The bug was introduced by this innocuous-looking cleanup patch. The 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.