How does SSH client ensure that SSH server bears the private key, which is the pair of the public key in client's "known_hosts" file?

Question

An SSH client obviously authenticates an SSH server in some way. Because when the key of the server changes, the SSH client software gives us a loud warning about the key of the server being changed and this might be a MitM attack.

However, does the client do this authentication using a challenge? That is, does the SSH client encrypt a piece of randomly generated data using the server's public key, and expect that the server will be able to decrypt this using its private key and send back the decrypted data, in order to authenticate the server?

Answer 1

The Secure Shell (SSH) Transport Layer Protocol (RFC 4253) describes how server authentication is done. According to section 7 there is implicit and explicit server authentication. Implicit authentication requires a shared secret between client. Explicit authentication means that the "key exchange messages include a signature or other proof of the server's authenticity". This is the kind of server authentication one usually uses, i.e. where the server has a key pair, the public key is known to the client and it wants to verify that the target of the connection knows the matching private key.

How explicit authentication is included in the Diffie-Hellman key exchange is described in section 8. Essentially the server signs some data from the client using the servers private key to prove ownership of the key and the client validates this signature using the known public key. These client provided data include random data so replaying an older signature is impossible. For the much deeper details see the RFC itself.

Answer 2

I don't think this check is authentication by the SSH client, what you're referring to sounds like it is the cache for server host keys in the SSH client. This does serve to identify the server, but it is not authentication

There are two authentication scenarios for SSH (that I know of), in both cases it is the client that is authenticated, not the server:

1) (default) simple password authentication, where the server challenges the client for a password. There is no checking by the client in that case.

2) Using SSH keys - this involves generating a private key on the client machine and importing the corresponding public key on to the server. In this case something similar happens to what you are describing, but the client is using its own private key to encrypt the server's message. The server is then checking this encrypted message against the client's public key. It's seen as both more secure and easier to manage than a simple password, provided the private key is kept secure

Here is a good breakdown of the SSH key authentication process by Digital Ocean

Answer 3

Being frustrated by DigitalOcean for this topic too, I propose this answer. The reference is section 8 of RFC4253 that claims, during Diffie-Hellman Key Exchange:

First, the client sends the following:

  byte      SSH_MSG_KEXDH_INIT
  mpint     e

The server then responds with the following:

  byte      SSH_MSG_KEXDH_REPLY
  string    server public host key and certificates (K_S)
  mpint     f
  string    signature of H

Basically, during Diffie-Hellman key exchange/generating, client creates key "e" from its secret key "x"; server will do the same with "f" from "y". With "x" and "f" (client) or "y" and "e" (server), the encryption secret key "K" is computed on both sides (I let you look at Diffie-Hellman magic).

Then the trick comes :) A big computation is done on both side: "H". Which is a hash of a long string including many stuff like e, f, name of server "V_S", name of client "V_C", previous messages content ("SSH_MSG_KEXINIT" from client/server = "I_C"/"I_S"), public server key "K_S" and, last but not least, the secret key K:

H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)

H is not explicitly provided to client since it knows all of this information and hence can compute it too; but rather, server provides signature of H, computed with server private key. Client can then check this signature thanks to its own computation of H and public key K_S to authenticate the server.

The main point IMHO is to mix -at least- K (secret) and signature: no MitM can masquerade such a message!

Answer 4

This seems like a relevant answer to your question: Verifying SSH fingerprint of a public server

In short, the SSH server has a public and private key that are used while establishing a connection from the SSH Client. The server will provide a copy of it's public key to the client where it is presented to the user for verification. The user is then responsible for validating that key with the administrator of the server then accepting the key.

Once accepted, the user will only ever see that again if the key changes. When the key changes, it could be a re-key done on the server by the administrator or via MITM style attack; you would need to re-verify the key with the administrator to see which is which.

There is no 'challenge' as I believe you're trying to put it, as this is just how Public-Key Cryptography works.

EDIT: An SSH server will auto-generate it's host-keys during installation through the use of the ssh-keygen application. This typically creates an RSA, DSA, ecdsa or ed25519 key, or some variation there of (depending on configuration).

A client connecting to the server will use ssh-keyscan to check the fingerprint of the server and present that to you as the user for verification. When you accept that key, it writes it to the ~/.ssh/known_hosts file to remember it. Every time your ssh client connects that to that server, it reads the fingerprint, checks it in the known_hosts file and ensures it hasn't changed. If it does, you, the user, are presented with a warning that the key changed and the connection is halted. You must manually delete or alter the key to be able to connect again.

$ ssh-keyscan some.remote.server
some.remote.server ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEA8BPNr+Q8cQfU95jfJKIfAH+z0+q03QDeFH1ndeTC3Zf0EDjZOg1OXs+Xiwjgrkq+vcNIA5DPaux3aStrcSa5o1AjgBNKN4rMyaLMW1c5LUnSic2oE7YTGvO1AHL55+Z4rCiEbDHeK2LXwhZifNvqkxf44pKrIe8kCvt89dkRsCria4n5EedGazKxO0mvbHM9JSpg03CiD4B+/afOrZqCJrf5dYcDCmeiBPSn9vjiZzAl2NYj05GVSqoe8KeFQV9n4c4LtWfzSDshvLlypuSfylzhL3euWG6JP8G6HnBohSiSQFk/Y0VFX/4wYshKjN3px0ugYUrucXXv8Sznv6n1Dw==

If you were to open the known_hosts file on my system, you would see this exact entry in there.

EDIT 2:

Reading the comments, you seem to be stuck on this fingerprint bit. The fingerprint is the Public part of Public-Key Cryptography. You should really go read more about this as I linked before to fully comprehend this concept. In Public-Key Crypto, a Private Key and Public Key are mathematically created simultaneously. This key pair holds a special ability in that anything encrypted by the Private key can ONLY be decrypted by the Public key and anything encrypted by the Public Key can ONLY be decrypted by the Private key. This is asymmetric cyrpto, NOT symmetric crypto (using one key for encrypt/decrypt).

You must also understand how signing works to understand the use of Public-Key crypto. If I write a message in plain text and send it to you, you don't know that I sent it. If instead I write a plain text message and at the bottom I add an encrypted blob which contains a hash of the message and was encrypted using my private key, then my public key can be used to decrypt the blob, the original plain text message can be hashed and compared with the hash I included in the encrypted blob.

This same concept is applied here with SSH. Since only the private key used on the server is capable of working with the public key your client has, you can mathematically prove that they are the same machine. As mentioned in my comment, it is near impossible to generate two private keys which are an exact match thus providing a duplicate fingerprint. If you could generate a private key which was exactly the same as another server's private key, then yes, you would have the same fingerprint as some other server -- Consider this impossible today.

Answer 5

I have read parts of the RFC4253 as Steffen Ullrich suggested. Following is a very incomplete description but what I understand is:

1. Client and server obtain a number of shared secrets as the result of the key exchange.
2. The server signs these shared secrets using its private key and sends it to client.
3. The client decrypts this using the server's public key. If the result matches what is described in the RFC4253, then the server is authenticated.

For a moment, I thought: "Wait, why do we need an explicit authentication mechanism? Since the client is using the server's public key to encrypt the stuff it sent to server, if the server is fake, the server won't be able to decrypt what is sent by the client. Since the server wouldn't understand what the client said, the server won't be able to produce a meaningful response. Hence, the client would know that the server is fake since the server will send a meaningless response."

Well the paragraph above is entirely incorrect. Because the client and server use symmetric key encryption to communicate after the key exchange. Hence, the asymmetric keys of the server (and potentially of the client) are used only for authentication purposes. Not for communication purposes.