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?

  • $\begingroup$ Be careful, MD5 is broken. $\endgroup$
    – Viou
    Commented Nov 20, 2018 at 20:10
  • $\begingroup$ Note that auth protocol was for SSHv1 which is obsolete and no longer used -- in fact not even implemented in OpenSSH since 7.6 2017-10-03. Although that doesn't prevent us thinking about it. $\endgroup$ Commented Dec 7, 2021 at 0:06

3 Answers 3


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".

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – SEJPM
    Commented Nov 22, 2018 at 15:13

"Learns no new knowledge" is formalized as existence of a simulator algorithm producing an indistinguishable transcript fast enough. In other words: a simulator must exist to name it zero knowledge.

Goldreich, Micali, Wigderson. Proofs That Yield Nothing But Their Validity.. Link.

Update: a simulator (running by the server/verifier) would

1: pick a random, exactly as the server at step 3, and produce a ciphertext;

2: produce a shared secret, combine it with the random from step 1, produce a hash exactly as the client at step 6.

Simulated transcript is the two messages generated, distributed according to probability distribution of the random chosen at step 1. This means, simulated transcript and session transcript are indistinguishable.

In this case anyone could (a) pick a random and produce a ciphertext allegedly decrypted by the client, and (b) produce a shared secret to be combined with the random from the previous step.

  • $\begingroup$ Can you elaborate on this answer? Why can't a simulator algorithm produce an indistinguishable transcript in this case? $\endgroup$ Commented Dec 7, 2021 at 2:57
  • $\begingroup$ Fedyuvoych I read your update. I agree with your analysis that the SSH connection process (once a shared session key is established) is zero-knowledge. I suspect this to be correct but hopefully someone else can chime in. $\endgroup$ Commented Dec 8, 2021 at 6:37

It is not zk (zero knowledge). Imagine Bob some invited some coworker on his house. Each guest will conversion about idea in a single pesudo-code. if a code crack within 5sec then guest idea on investment table. However bob don't know the text is pesudo or plain text. Once the code crack other coworkers did the other partners. if other partner crack the code then secret ballot number update by 1 otherwise -1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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