Quoting from source, authentication using SSH key pairs goes something like this:

1) The client begins by sending an ID for the key pair it would like to authenticate with to the server.

2) The server check's the authorized_keys file of the account that the client is attempting to log into for the key ID.

3) If a public key with matching ID is found in the file, the server generates a random number and uses the public key to encrypt the number.

4) The server sends the client this encrypted message.

5) If the client actually has the associated private key, it will be able to decrypt the message using that key, revealing the original number.

6) The client combines the decrypted number with the shared session key that is being used to encrypt the communication, and calculates the MD5 hash of this value.

7) The client then sends this MD5 hash back to the server as an answer to the encrypted number message.

8) The server uses the same shared session key and the original number that it sent to the client to calculate the MD5 value on its own. It compares its own calculation to the one that the client sent back. If these two values match, it proves that the client was in possession of the private key and the client is authenticated.

This seems to achieve all the necessary requirements of a zero knowledge proof. It is complete, sound, and the server learns no new knowledge of the user's private key.

I found this question that seemed related at first.

Is Using Digital Signatures to prove identity a zero knowledge proof?

However, the OP in this question required the Validator send a text, have the Prover encrypt it using their private key, and the Validator verify it using the public key. Thus some knowledge is being leaked (namely the private-key ciphertext and its corresponding challenge). Using the SSH key-pair protocol though, only the public-key ciphertext is being communicated, which is already public knowledge. As no new knowledge is being communicated, SSH meets the requirements of zero-knowledge proof, right?

  • Be careful, MD5 is broken. – Viou Nov 20 at 20:10

At step 3-4), the server can use the protocol to decrypt any message encrypted with the public key of the client. The server is not able to decrypt alone because it does not know the secret key of the client, so the protocol is not perfectly zero-knowledge. Moreover, the protocol is not a proof of knowledge because you cannot build an efficient knowledge extractor (see "validity"). At best, this protocol prove that the public key of the client is "well formed".

  • Comments are not for extended discussion; this conversation has been moved to chat. – SEJPM Nov 22 at 15:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.