can anyone explain how user keys are verified (post host key/KEX, and not authorized_keys)? issue with ssh user key verify

Question

Nutshell: Looking for a bit of an ELI5 explaining the protocol and/or implementation (openssh) of [post-KEX] user key verification (who does what) without being in code I don't understand or a too-simple website for noob setting up key auth. We've got Workday and Red Hat looking into it, but I'm trying to be an informed consumer when dealing with them.

How does this verification work right around mm_answer_keyverify? How do they verify the user keys (after authorized_keys is checked and allowed)?

1. Does each side sign their keys and signatures are matched?
2. Do they encrypt something using their local signing algorithm, and then compare?

More detail:

We're seeing some weird problems when making connections from another server to our inhouse EL9 system. Everything works fine and the same with an EL7 system (being replaced) - using same keys (RSA), same users, same files (NFS home), etc. Host keys and KEX and even authorized_keys checks are successful, and it seems to fail on user keys: We get fails from Workday, and from an AIX system running curl+sftp, but NOT AIX using sftp alone):

debug1: /home/USER/.ssh/authorized_keys:12: matching key found: RSA SHA256:aGrK...
Accepted key RSA SHA256:aGrK... found at /home/USER/.ssh/authorized_keys:12
debug3: mm_answer_keyallowed: publickey authentication: RSA key is allowed

debug3: mm_answer_keyverify: publickey RSA signature unverified: error in libcrypto

We've resorted to running the LEGACY crypto policy just to attempt to diagnose (no joy). Personally, I think we're running into library differences where one is still using a ssh-rsa algorithm, and the other side is using a compatibility algorithm ("you asked for ssh-rsa, but i'll use rsa-sha256-512"), and thus the issue and my questions, but that's just a guess and I'm a layman.

Just for clarity, here's what I see in server logs for a success:

debug3: userauth_pubkey: have rsa-sha2-512 signature for RSA SHA256:aGrK.....

and same server, a fail (keeping in mind we are temporarily allowing SHA1, etc, so that's not the issue; our user keys are 2k RSA sshv2 keys, so that's ok too):

debug3: userauth_pubkey: have ssh-rsa signature for RSA SHA256:aGrK.....

The most obvious bit is the signature difference, but I don't know why the server would use different ones unless that's really the CLIENT saying that to the server...

Thanks for any pointers!

Answer 1

None of the above. The mechanism is signing – but only the client sends a signature; the server verifies that signature.

Regarding the guesses:

• Does each side sign their keys and signatures are matched?

  That's not possible, as only one side has the private key to make signatures with – the server cannot make signatures while having only the public key, nor would that make any sort of practical sense. (This asymmetry of public/private keys is actually the point of asymmetric algorithms; it's completely different from e.g. HMAC or password hashing.) Instead, when one side signs something, the other side will verify the signature against the data – much like encryption/decryption, there's a complementary 'verify' operation to signing.

  So if the server says "have ssh-rsa signature", that means it has received such a signature from the client and is about to perform verification (which fails for some strange reason).

• Do they encrypt something using their local signing algorithm, and then compare?

  You don't encrypt with a signing algorithm; you sign with a signing algorithm. Even if the underlying math happens to be similar (and that's only for some algorithms), you shouldn't think of them as the same.

  Besides that, "encrypting and comparing" wouldn't be useful because RSA encryption is done using the public key alone – and the public key is often publicly known – so it would be trivial to spoof. You need an operation that involves the private key, and that's either signing or decryption.

As a side note, encryption/decryption used to be the SSHv1 method: the server used to encrypt a challenge and request the client to decrypt it. But it's no longer done that way in SSHv2 which uses only signing (and signature verification): The side that has the private key (the user, for authorized_keys) will sign a "challenge" – a chunk of random data provided by the opponent – and will send the signature, which the opponent will verify.

Note that the 'sign' operation only takes inputs of a limited size, so it's never the actual challenge data that's being signed, but a hash of the data. The difference between ssh-rsa and rsa-sha256-512 is merely in what hash is applied to the challenge; newer SSH clients will hash it using SHA256 while older ones use SHA1. (And RSA is the only supported algorithm that has flexible-size keys and has outlasted the SHA1 era; both EC and EdDSA use fixed-size keys and use a hash algorithm that exactly matches the curve bit size, so they do not have such compatibility issues.)

Personally, I think we're running into library differences where one is still using a ssh-rsa algorithm, and the other side is using a compatibility algorithm ("you asked for ssh-rsa, but i'll use rsa-sha256-512"), and thus the issue and my questions, but that's just a guess and I'm a layman.

While it's possible for the client to send a signature in the wrong format (as mentioned above, the server doesn't make its own signature), the failure would normally be different, as the software explicitly tells the crypto library what algorithms to use. (Or, if the SSH server were really too old to understand rsa-sha256-512, then it would've rejected the signature as unrecognized type before passing it to the crypto library.)