SSH-RSA public key authentication explanation needed

Question

I have recently upgraded my workstation - Fedora 31 to Fedora 34. As it usually happens after upgrade some of ssh alogrithms become obsoleted and I have to add extra lines to .ssh/config and I am okay with that doing my best on security.

This time ssh-rsa term confuse me a lot. I have old RSA public key, for instance it worked to authorize my openssh client against Debian 10, Debian 8 and Cisco 4k router.

After upgrade I have to add PubkeyAcceptedKeyTypes +ssh-rsa to .ssh/config for most of older hosts, in this case it would be Debian 8 and Cisco 4k router. Now I can log in like i used to. But Cisco 4k log a message:

Public-key Algorithm compliance violation detected.Kindly note that weaker Public-key Algorithm 'ssh-rsa' will be disabled

Here are my questions:

1. If Cisco 4k allow higher PK than ssh-rsa, why it does not work with default ssh settings?
2. Is there any connection between key type "ssh-rsa" and allowed PK algorigthms, e.g. does public key type limit allowed algorightms by key length or anything?
3. This authentication is always referred as ssh-rsa, but if I have to add it manually to config - what real PK authentication is used by default? Is it a sort of ssh-rsa or even some other type?
4. Is there any way (I have tried ssh debug and sshd debug) to understand clearly what PK algorithms are supported on server and client like we do with ciphers?

Update:

New information about Cisco 4k router: By default Cisco support host key algorithms: rsa-sha2-512,rsa-sha2-256,ssh-rsa

I have added PubkeyAcceptedKeyTypes +rsa-sha2-512 and I can log in, but still get warning about ssh-rsa.

Considering rsa-sha2-512 as a sort of ssh-rsa (because they both were dumped in recent openssh) my additional questions are:

5. Does router statement seems to refer ssh-rsa as any type of ssh-rsa including rsa-sha2-512?
6. Does host key algorithms enabled in router seem to be limited by some other means?

Answer 1

For background...

There's a great answer on the topic over on Security Stack Exchange which links through to openssh's notes on deprecating ssh-rsa.

It seems the problem is that the original ssh-rsa algorithm (described in RFC 4253) relied on SHA-1 which is now largely defunct for cryptography:

Since 2005, SHA-1 has not been considered secure against well-funded opponents; as of 2010 many organizations have recommended its replacement. NIST formally deprecated use of SHA-1 in 2011 and disallowed its use for digital signatures in 2013. As of 2020, chosen-prefix attacks against SHA-1 are practical.

But it's the signature algorithm that used SHA-1 not the key itself.

---

With that in mind...

If Cisco 4k allow higher PK than ssh-rsa, why it does not work with default ssh settings?

What's changed is that openssh no-longer allows ssh-rsa by default. The change you made lets your client accept ssh-rsa. So the router still accepts it (even if it moans). But there's no strict hierarchy to the algorithms, just some "better" than others. So allowing "higher" algorithms doesn't mean that router and client share the same "higher" algorithms.

Another possible reason is that while your client and router both shared "better" algorithms, they weren't compatible with a raw RSA key. Eg: they allowed ssh certificates, but you have a key and no certificate. In that case you could use default settings but not your existing key with default settings.

Is there any connection between key type "ssh-rsa" and allowed PK algorithms

From what I can find on the topic, yes. They algorithms can be limited to a single cipher but don't typically care so much about key length. Keys are basically just [some] very large numbers. It doesn't matter how large they are, but the algorithm needs to know what to do with them.

Is there any way (I have tried ssh debug and sshd debug) to understand clearly what PK algorithms are supported on server and client like we do with ciphers?

Although it's a bit cryptic this is available with openssh level 2 debug (-vv). You'll see debug2: KEX algorithms: ... and debug2: host key algorithms: .... You should also see which algorithm was selected. There is also a level three debug (-vvv) if you want to delve deeper.