How can SSH server know private key is incorrect if passphrase havent been provided yet?

Question

I have server which I am accessing via SSH. I only allow the authentication to be made with private key. Normally when I login via PuTTY, I am first asked for username and then asked for passphrase for the key. Out of curiosity I have created new private key, which should be invalid for my user and I also have put passphrase on it. To my surprise once I provided the user name the key attempted to login with to my server was refused before I have been asked for the passphrase.

I am wondering how can SSH server know that the private key is incorrect if the passphrase for it haven't been provided yet?

Answer 1

While you've encrypted the private key, the public key is still readable. SSH authentication with the "publickey" method works by having the client send each potential public key to the server, then the server responds telling the client which key is allowed. If one of the keys is allowed, then the client must decrypt the private key to sign a message, proving ownership of the private key.

In your experiment, the server responded saying that none of the provided keys was allowed for your username, so there was no need to decrypt a private key, authentication had already failed.

Answer 2

During connection client will sent successively fingerprint of all availables keys to server.

When server signal to client a valid key found, client will use them, then ask for passphrase if needed.

Try to run ssh with debug option:

ssh -o LogLevel=DEBUG3 user@dest

look for fingerprint with

ssh-keygen -l -f .ssh/id_rsa

For checking authorized_keys, line by line:

while read line;do
    ssh-keygen -l -f <(echo "$line")
  done <.ssh/authorized_keys