How does SSH know which key to use

First thing after establishing the TCP connection, both systems agree on a session key, using such protocols as DH key exchange, ECDH or GSSAPI. This key is symmetric and temporary – both sides use the same key to encrypt and decrypt data using such algorithms as AES or RC4.

The client keypair is never used for encrypting data, only for authentication – "publickey" is one of several available methods, where the client presents its own public key along with proof of private-key ownership. Similarly, the server keypair is only used for authenticating the server during DH or ECDH key exchanges; no data is encrypted using it.

The SSH2 protocol is documented in several RFCs, including:

• RFC 4253 – Secure Shell (SSH) Transport Layer Protocol
  • section 7 – "Key Exchange"
  • section 8 – "Diffie-Hellman Key Exchange"
• RFC 4419 – Diffie-Hellman Group Exchange
• RFC 4432 – RSA Key Exchange
• RFC 4462 – GSSAPI Authentication & Key Exchange

The Wikipedia article is confusing different SSHv2 layers. (It might have been somewhat correct for SSHv1 a decade ago, but it's definitely simplified to the level of nonsense.)

SSHv2 key pairs, both yours and server's, are used for authentication only, and encryption setup is always done using temporarily generated DH key pairs for every connection. The server's SSH key pair only signs encryption setup data (to prove the server's identity), while the client's SSH key pair isn't used for this process at all.

In SSHv2, when you connect to the server (after both ends exchange lists of supported algorithms), the first step is key exchange, which somehow generates a symmetric key used to encrypt the entire connection. (The server is also authenticated as a side effect of this process.)

Most of the time D–H or ECDH will be used for this, which means:

1. The client generates a DH keypair (used for this connection only) and sends its DH public key.

2. The server also generates a fresh DH keypair. It also loads its SSH "host key" keypair from disk.

   Then it signs the DH public key with SSH private key, and sends both public keys (as well as the signature) to the client.

3. The client checks the signature and verifies that the server's SSH public key is in known_hosts.

   Then it uses both DH keys (client's private + server's public) to generate the shared encryption key, and throws away its DH keypair.

4. The server also uses both DH keys (server's private + client's public) to generate the same shared encryption key, and also throws away its DH keypair.

5. Both sides enable encryption.

(There are some other key exchange methods but they're rarely used.)

The next step is client authentication. Notice that at this point the connection is already encrypted, even though the client's SSH key wasn't used yet!

1. The client sends a "service request" for client authentication.

2. The server offers some mechanisms – "password", "public-key", possibly others.

3. If you have a SSH key pair, the client selects "public-key", sends your SSH public keys, and uses your SSH private key to sign some random data provided by the server, to prove key ownership.

   If you don't have a SSH key pair, the client selects "password" and sends your password directly – however, still inside the encrypted tunnel.