Return to Answer

debug1: SSH2_MSG_EXT_INFO received
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>

debug1: SSH2_MSG_EXT_INFO received
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>

What makes everything confusing is that originally in SSHv2, the key type and the signature type used to be defined in combination. (For example, the same "ssh-rsa" identifier was defined to mean RSA keys and RSA/SHA-1 signatures.) So changing the signature process would have meant assigning a new key type identifier, and that would have meant generating a new key.

This applies when using certificates, but is irrelevant to plain keys.

What makes everything confusing is that originally in SSHv2, the key type and the signature type used to be defined in combination. (For example, the same "ssh-rsa" identifier was defined to mean RSA keys and RSA/SHA-1 signatures.) So changing the signature process would have meant assigning a new key type identifier, and that would have meant generating a new key...

This applies when issuing certificates, but is irrelevant when generating plain keys.

Note that this is a different situation from previous SHA-1 usage in X.509 (HTTPS) certificates.

Certificates, such as those used in HTTPS (X.509), had to be replaced because they hold a signature inside – each certificate is signed by the parent CA at the time it is issued. This long-term signature stored in the certificate is a completely separate thing and unrelated to the short-term signatures that are made during each connection and then thrown away.

So if your workplace uses the so-called "OpenSSH certificates" (e.g. you have files whose names end with -cert.pub), you might need to have those re-issued and ssh-keygen -Lf <file> will tell you whether they were signed using RSA/SHA-1 or RSA/SHA-256.

But if you just generated a key yourself, then it does not have signature inside, so there's nothing you need to do with it.

I tried checking the type of the key with ssh-keygen -l -f key and it shows me that it is indeed SHA256 type

Signatures in ssh-keygen

the default option rsa for the -t argument explains that the chosen option is using the SHA1 signature, so one should choose rsa-sha2-256 for example.

This applies when using certificates, but is irrelevant to plain keys.

Each certificate is signed by the parent CA at the time it is issued. This long-term signature is stored in the certificate itself (and it's very important to realize that this is a different thing from the short-term signatures that are made during each connection and then thrown away). That's why many HTTPS (X.509) certificates had to be replaced – the issuing CA had stamped them with RSA/SHA-1 signatures.

OpenSSH has also created its own certificate format, which is what the manual page is referring to. These so-called "SSH certificates" are not just regular SSH keys – they're additionaly signed by e.g. your workplace CA. So if you have files whose names end with *-cert.pub, you might need to have those re-issued. (Use ssh-keygen -Lf <file> to check how they were signed).

But plain SSH keys do not hold any long-term signature inside – they're only used to make temporary signatures during each connection. So there is nothing that needs replacement in the key itself.

The -l option

I tried checking the type of the key with ssh-keygen -l -f key and it shows me that it is indeed SHA256 type

Other key types