How does SSH know which public key to use from authorized_keys?

Question

When an SSH client connects to an SSH server using public key authentication, the server encrypts a message using a public key from authorized_keys, and the client must prove it can decrypt the message.

How does the SSH server know which public key to use for a given client?

The client cannot be sending the public key to the server, as according to this answer the client doesn't need the public key to login: https://security.stackexchange.com/a/42847/174597

Note I am not asking about how public key authentication works. I am asking which public key does a typical SSH server (e.g. OpenSSH) use to encrypt the challenge sent to the client, from a list of keys stored for example in authorized_keys?

The client does indeed send the public key to the server, if public key authentication is enabled. — forest, Apr 02 '18 at 23:48
@forest do you have any references to back that up? Did you read the linked answer? — aaa90210, Apr 03 '18 at 00:00
@forest OK but I am asking about the server. How does it know which public key from authorized keys to send to the client? Does it send multiple challenges based on all of them until the client answers one correctly? — aaa90210, Apr 03 '18 at 00:19
Is this what you are asking: [How are unique SSH users linked to authorized_keys file?](https://security.stackexchange.com/q/176366/165253) — forest, Apr 03 '18 at 00:21
@forest that isn't the answer. Authorized_keys for a given user can have multiple public keys in it...when a client connects to bob@foobar.com...which public key from bob's authorized keys is used to encrypt the challenge? — aaa90210, Apr 03 '18 at 00:23
I think the question indicates a common (and incorrect) assumption that authentication protocols work by Encryption, rather than Digital Signature Algorithms. The question in the previous comment probably leads where you want to go. — nbering, Apr 03 '18 at 01:18
I'll add one minor detail, that key selection is negotiated. The client tells the server what keys it has, the server picks one, and the client proves it has the private key by sending a signed string. You can see this happen with `ssh -vvv user@example.com`. — nbering, Apr 03 '18 at 01:21
@multithr3at3d incorrect, that does not answer the question. — aaa90210, Apr 03 '18 at 01:23
@nbering the client does not need the public key for this to work, are you suggesting it is sending it's private key? — aaa90210, Apr 03 '18 at 01:24
@aaa90210 With RSA, the public key is one very large number, produced by multiplying two very large prime numbers together. Finding the public key from the private key is just a matter of multiplying two numbers, whereas breaking the key is a matter of guessing what the two numbers were, which takes astronomically more work for the size numbers we're working with. — nbering, Apr 03 '18 at 01:27
@nbering what are you going on about? I am asking about the specific behavior of ssh, not crypto theory. SSHD encrypts a challenge using a public key to see if the client can decrypt it, which public key from authorized keys does it use? — aaa90210, Apr 03 '18 at 01:31
@aaa90210 I see you've already commented on some of those answers. Well, have you read RFC 4252 that was linked in those answers? It explains what is expected by the SSH protocol; I would argue any further explanation would be an implementation-specific detail, and you've not asked about a specific implementation, albeit likely OpenSSH. — multithr3at3d, Apr 03 '18 at 01:31
Well take SSH being the SSH server/client command on Linux for a start. I am not interested in RFCs. — aaa90210, Apr 03 '18 at 01:32
@aaa90210 Sorry.. my rather verbose explanation is just saying if you have the private key, you have the public key. — nbering, Apr 03 '18 at 01:33
So the client is extracting/deriving the public key and sending it to the server? That is an interesting explanation, the other one I have seen is the server tries all the public keys in authorized keys until the client correctly decrypts the challenge. I just wanted to understand which one it was, or another. — aaa90210, Apr 03 '18 at 01:35
It can be either. The RFC mentioned above states that the client may send the authorization signature without first negotiating a valid public key. In that case, the server would need to check all the valid keys for the target user before deciding if it was valid. — nbering, Apr 03 '18 at 01:37
Oh.. except for one small detail. You say "decrypts the challenge". Digital signatures are not encryption. The client applies the RSA encryption algorithm sort of in reverse. It "encrypts" the well-known authorization details with the private key (the part normally used for decryption), which allows anyone with the public key to reverse the process. The result is compared to the well-known part and this proves the client had the private key. — nbering, Apr 03 '18 at 01:46

score 9 · Accepted Answer · edited Oct 07 '21 at 07:34

RFC 4252 provides guidelines on how public key authentication should work, but it is not entirely specific on the exact order of the exchange. That said, it was stated in the comments that OP is not interested in RFCs but rather the implementation details for "SSH on Linux", which refers to OpenSSH in most cases.

Connecting to a remote host over SSH with the verbose -v flag, you will typically see the following for each key:

debug1: Offering RSA public key: .ssh/id_rsa.pub

Further, we can look at the source code. After a quick skim, the following is relevant:

if (PRIVSEP(user_key_allowed(ssh, pw, key, 1, &authopts)) &&
        PRIVSEP(sshkey_verify(key, sig, slen, sshbuf_ptr(b),
        sshbuf_len(b), NULL, ssh->compat)) == 0) {
        authenticated = 1;
}

The user_key_allowed function checks for the key in an authorized keys file, while the sshkey_verify appears to verify the signature of some buffer.

Combining this information, it appears that the client will use all of its keys until the server accepts one. This is also evident by the fact that having multiple keys present during a single connection attempt may appear on the server as multiple authentication attempts since all of the keys are tried.

Additionally, see @nbering's comments for the details on the challenges/signatures.

Edit: Here's an example where I have several keys, and only the third one tried is accepted by the server. Using -vvv:

debug1: Next authentication method: publickey
debug1: Offering public key: RSA SHA256:QfriqWH2S2uD6wHbxTFSudppOcJ51bB5ABr8ICrUhL8 .ssh/id_rsa2
debug3: send_pubkey_test
debug3: send packet: type 50 # SSH_MSG_USERAUTH_REQUEST
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51 # SSH_MSG_USERAUTH_FAILURE
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Offering public key: RSA SHA256:3M8bnhs+jGJm8X2cgnWzzMrfoeT3WmDkSp8AEr751Sk user@laptop
debug3: send_pubkey_test
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Offering public key: RSA SHA256:CQeP9lcYBVqV11Rn8Ca4Sv+W8l8uU63WQ4TpyG5ZMmI user@laptop
debug3: send_pubkey_test
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 60 #  SSH_MSG_USERAUTH_PK_OK
debug1: Server accepts key: pkalg ssh-rsa blen 279
debug2: input_userauth_pk_ok: fp SHA256:CQeP9lcYBVqV11Rn8Ca4Sv+W8l8uU63WQ4TpyG5ZMmI
debug3: sign_and_send_pubkey: RSA SHA256:CQeP9lcYBVqV11Rn8Ca4Sv+W8l8uU63WQ4TpyG5ZMmI
debug3: send packet: type 50
debug3: receive packet: type 52 # SSH_MSG_USERAUTH_SUCCESS 
debug1: Authentication succeeded (publickey).

This again closely follows RFC 4252, pages 8-9.

Nice. Clear and concise and with source code to boot. Hope this explains things well enough for @aaa90210's purposes. — nbering, Apr 03 '18 at 02:00
Wrong answer, the client doesn't need a public key to connect using public key authentication. — aaa90210, Apr 04 '18 at 00:02
@aaa90210 You don't need the public key _file_ on your system, but as long as you have the private key, you can derive the public key if needed. Also, with that attitude, it is unlikely you will get much more help. — multithr3at3d, Apr 04 '18 at 00:08
@multithr3at3d if being surprised all these experts can't answer a basic question is an attitude, then I guess I have one. I am not interested in deriving a public key, I want to know how e.g. OpenSSH knows which key from authorized_keys to encrypt the challenge sent to the client. Such a simple question. — aaa90210, Apr 04 '18 at 00:10
@aaa90210 OpenSSH does not encrypt any challenge. That's not how the protocol works. — forest, Apr 04 '18 at 00:19
@multithr3at3d So does it mean that a SSH client sends the public key it has to the SSH server before opening a connection? And if the public key sent by the SSH client matches with one of the authorized public key of the SSH server, then only the server will send a challege to the client? — Chinky Sight, Apr 11 '22 at 08:48
@Kalsang that seems about right. There was a project a while ago that demonstrated the first part. There was a server you could try to SSH into (without having access). It would look up your public key fingerprint against GitHub's API, and greet you by your account name. — multithr3at3d, Apr 15 '22 at 01:34

How does SSH know which public key to use from authorized_keys?

1 Answers1