How does authentication work for SSH login with a public key?

Question

For SSH public key authentication in Cisco IOS it is sufficient to add RSA public key hash instead of content of that public key.

For example:

ip ssh pubkey-chain
  username admin
  key-hash ssh-rsa 539197BB0F11CE77A123334A97859E30 admin@server

From cryptography point of view, how does authentication actually work in such a case – public key hash on one side with corresponding private key on another?

I thought that we have to have a pair of keys exactly. Not a public key's hash on one side and a private key on another.

Answer 1

The goal of authentication is to verify the identity of a party to communication, i.e. to check that they are who they claim to be. Two parties are involved: the verifier, and the requester. Here the verifier is the server and the requester is a remote user, but in other cases they could have different roles.

Authentication using asymmetric cryptography involves several steps of reasoning.

1. Only the legitimate requester knows the private key. Everybody else is unable to make computations that require the private key.
2. The verifier is able to tie the public key with an identity. Maintaining the association between the public key and the identity is the responsibility of the verifier. In this case, the association is made through a configuration file on the server that says “the public key whose has is … is user #42 authorized to log in as admin”.
3. In order to be authenticated by the verifier, the requester must perform a computation that requires the private key corresponding to a public key. This can be either a signature that the verifier verifies, or an encryption whose result the verifier decrypts.
4. The combination of (1), (2) and a successful (3) allows the verifier to conclude that the requester has the identity associated with the public key.

In order to perform step 2, the server needs to have the public key. But it doesn't need to store the public key. It's ok if the requester sends the public key. The verifier calculates the hash of the public key sent by the requester and compares it with its stored hash. If the hash is correct then the requester has proved the association between the public key and the identity (because it's unfeasible to find a public key with the same hash as the expected one). When the requester proves that they know the associated private key, they have thus proven their identity to the verifier's expectations.

In a nutshell, it's ok for the verifier to store only a hash of the public key because:

• functionally, because the requester sends the public key;
• in terms of security, because knowing the hash allows the verifier to validate the public key.

This principle of hashing a public key is used all the time on the web, when browsers authenticate websites (so in this scenario, the requester is the website and the verifier is the browser). On the web, there's an extra step where a browser doesn't even know the hash of the website's public key before connecting. What the website sends in addition to its public key and to the proof of possession of the private key is an assertion of the form “this is the hash of the public key of www.example.com”, cryptographically signed by a certificate authority that the browser trusts. This assertion is called a certificate. (In fact, things are more complicated, but I gave the basic principle.)