When using the vault "Signed SSH Certificates" secret engine [1], ssh keys are being signed with the now-unsupported ssh-rsa algorithm. This makes them unusable to login to servers deploying the newer openssh version 8.2 [2]

I implemented a potential fix that I submitted to upstream [3]. I backported the patch to 1.3.2 [4] and rebuilt vault with it and can confirm that it fixes the issue but, as noted in the PR, the signed keys are now incompatible with openssh < 7.2.

Since we are shipping with openssh 8.2 I would consider applying the patch to our version of vault.

[1] https://www.vaultproject.io/docs/secrets/ssh/signed-ssh-certificates/
[2] https://www.openssh.com/txt/release-8.2
[3] https://github.com/hashicorp/vault/pull/8383
[4] https://gist.github.com/mtorromeo/36208c441fe4ea833d9641f4c4836411

Every version of vault is affected.

Here is an example of a certificate for a SSH key generated by vault without the patch (notice the "using ssh-rsa" part):

$> ssh-keygen -Lf /home/massimiliano/.ssh/vault_ecdsa-cert.pub
/home/massimiliano/.ssh/vault_ecdsa-cert.pub:
Type: ecdsa-sha2-nistp256-cert-v01@openssh.com user certificate
Public key: ECDSA-CERT SHA256:<SNIP>
Signing CA: RSA SHA256:<SNIP> (using ssh-rsa)
Key ID: "vault-approle-<SNIP>"
Serial: <SNIP>
Valid: from 2020-02-19T13:59:25 to 2020-03-22T13:59:55
Principals:
<SNIP>
Critical Options: (none)
Extensions: (none)

and the same with patched vault:

$> ssh-keygen -Lf /home/massimiliano/.ssh/vault_ecdsa-cert.pub
/home/massimiliano/.ssh/vault_ecdsa-cert.pub:
Type: ecdsa-sha2-nistp256-cert-v01@openssh.com user certificate
Public key: ECDSA-CERT SHA256:<SNIP>
Signing CA: RSA SHA256:<SNIP> (using rsa-sha2-256)
Key ID: "vault-approle-<SNIP>"
Serial: <SNIP>
Valid: from 2020-02-19T15:16:36 to 2020-03-22T15:17:06
Principals:
<SNIP>
Critical Options: (none)
Extensions: (none)

trying to use the ssh-rsa certificate to log in to openssh 8.2 fails with "Permission denied (publickey)." and this logged on the server:

sshd[1446337]: userauth_pubkey: certificate signature algorithm ssh-rsa: signature algorithm not supported [preauth]
sshd[1446337]: Connection closed by authenticating user <SNIP> port 57455 [preauth]