How does ssh public key authentication work?

Question

My basic understanding is this:

• The (connected to) server's sshd uses the public key to encrypt some message
• The client's ssh or ssh-agent decrypts it and sends something back (the message's checksum? its signature?)
• The server's sshd verifies that this is consistent with the message to authenticate the user

But what are the details? What is the "some message", what does ssh(-agent) send back? Would doing this with the same original message over and over again always yield the same communication?

Can this authentication process be replayed via bash tools if ssh-agent is used? E.g. the public keys that ssh-agent provides can be obtained via ssh-add -L, what about the rest of the process? Or would that require manually connecting to the $SSH_AUTH_SOCK unix socket and some low-level communication?

---

Related: Thomas' Server-Bob dialogue here, though that suggests the client just signs some random data that will then be checked against all public keys of the server user's authenticated_keys. This illustration on the other hand claims the message is encrypted to the previously determined user's public key (not the one for the ssh encryption) and the client outputs the checksum which also depends on some random session ID. Which one is correct? Or do both only tell part of the actually more complex story?

Answer 1

In brief:

• SSHv1: The server encrypts a message using 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 document PROTOCOL.agent summarizes this:

Protocol 1 and protocol 2 keys are separated because of the differing cryptographic usage: protocol 1 private RSA keys are used to decrypt challenges that were encrypted with the corresponding public key, whereas protocol 2 RSA private keys are used to sign challenges with a private key for verification with the corresponding public key. It is considered unsound practice to use the same key for signing and encryption.

Here's the SSHv2 relevant section from RFC 4252:

To perform actual authentication, the client MAY then send a
signature generated using the private key. The client MAY send the
signature directly without first verifying whether the key is
acceptable. The signature is sent using the following packet:

  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication
  string    signature

The value of 'signature' is a signature by the corresponding private key over the following data, in the following order:

  string    session identifier
  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication

When the server receives this message, it MUST check whether the
supplied key is acceptable for authentication, and if so, it MUST
check whether the signature is correct.

Answer 2

The particulars of the authentication depend on the protocol version and the type of key. In all cases, there is always a challenge, with some randomness to avoid replay attacks. When the user key is of type DSA, a true digital signature is necessarily involved, since DSA is a signature-only algorithm. The article you link to shows something which assumes that the user key can do asymmetric encryption; I guess this is something that SSHv1 did (in SSHv1, all keys were RSA, and RSA can do asymmetric encryption). For the current (SSHv2) protocol, public-key based client authentication is specified in RFC 4252, section 7.

The core concept remains the same: the client proves its control of the private key by performing an operation which requires knowledge of that key, but such that the "inverse" operation can be done with the public key which is located in the .ssh/authorized_keys on the server.