Question: Recently I've been trying to learn the mechanisms behind SSH keys but I came across this question that I haven't been able to find an answer to (I haven't figured out how to word my question such that searching it would give me the answer).

Basically, we add our local machine's public key to the server's `authorized_keys` file which allows us to be authenticated automatically when we try to `ssh` into the server later on. My question is: what if someone takes my public key (it is public after all) and replaces their public key with it? When the "attacker" tries to connect to the server, what part of the process allows the server to know that they do not have the correct private key?

I read somewhere that for RSA, it is possible for a user (let's say user `A`) to encrypt/sign a message with their private key, and then for others to decrypt this message using `A`'s public key, thus proving that `A` is really who they claim to be. However, apparently, this is not true for all cryptosystems, where it is not possible to sign with a private key (according to [What happens when encrypting with private key?](https://security.stackexchange.com/questions/81760/what-happens-when-encrypting-with-private-key), feel free to correct this information if it is wrong). In those cases, how does the server make sure that the user is really who they claim to be?

Answer: 
All forms of public key authentication support at least one of sign/verify or encrypt/decrypt (in practice, I'm pretty sure they all support sign/verify, I know some like DSA don't also support encryption but I don't know of any that can do encryption but not signing). Either operation can be used to prove identity.

I don't know the SSH handshake off the top of my head, but it's going to include a step where each side using public key authentication (the server, and sometimes the client) prove to the other side that they have the corresponding private key, by requiring the private key holder to do something that can only be done with the private key, and cannot be done by capturing and replaying traffic from a previous handshake. There's a few ways to do that (these are all from TLS, but SSH almost certainly does similar things):

1. Determine an unpredictable value (such as a cryptographic hash of all traffic in the handshake thus far) for the private key holder to sign and transmit, and then use the public key to verify the signature. (IIRC, this is how TLS client certs are verified).
2. Public key holder generates, encrypts, and transmits a secret value, private key holder must decrypt it to complete the handshake. (this is how TLS performs key exchange over RSA).
3. Private key holder generates a public and private ephemeral key exchange parameter pair, then signs and transmits the public part. The public key holder verifies the signature and then uses that parameter to complete the key exchange. Because the exchange depends in part on the private key holder's private key exchange parameter (which is generated anew for every handshake and never transmitted), an attacker can't just replay a previous signed public key exchange parameter; it would verify correctly but the attacker wouldn't be able to complete the key exchange, and thus couldn't communicate. (This is how DHE/ECDHE key exchange works in TLS).
SSH versions 1 and 2 do things slightly differently, but the choice of key generation algorithm for each protocol does not matter. The linked question in turn refers to yet another question - [How does ssh public key authentication work?](https://security.stackexchange.com/questions/23227/how-does-ssh-public-key-authentication-work) - and an answer to that question summarizes the two methods succinctly:

> 
> * SSHv1: The server encrypts a message to a public key stored in authorized\_keys, the client has to decrypt it and return it's checksum (modified by a session ID)
> * SSHv2: The client signs a message (depending on the session ID) and transmits the signature and message (without the session ID) including the public key used. The server then prepends the session ID and verifies the signature (provided the public key is actually in authorized\_keys)
> 
> 
> 

The one element missing from this description is that possession of the *private* key is required either to decrypt anything encrypted with the public key, or to create a valid signature which can be verified with the public key. The private key cannot be derived from the public key alone (although the reverse is not true, as the private key contains all the elements needed to reconstruct the public key).

So if the attacker only has your public key, and attempts to rely on it to authenticate to your account on a server, the attacker cannot do so because they do not have your private key with which to decrypt the received message or to sign the sent message.

There is a remote possibility for a man-in-the-middle attack if you use a key agent to authenticate to additional servers (as you would when using a gateway server or "hop box"). I say remote because this would require the attacker to have control of a different server on your network and the ability to induce you to log in to the attacker's server (with your purloined public key) rather than your own, perhaps via DNS poisoning. Host key verification should stop most attacks of this nature; in fact, if you end up logging into a host with a known DNS name in known\_hosts and the server keys do not match, the error message displayed can be quite disconcerting.