Paper 2022/740

Practical Privacy-Preserving Authentication for SSH

Lawrence Roy, Oregon State University
Stanislav Lyakhov, Oregon State University
Yeongjin Jang
Mike Rosulek, Oregon State University

Public-key authentication in SSH reveals more information about the participants' keys than is necessary. (1) The server can learn a client's entire set of public keys, even keys generated for other servers. (2) The server learns exactly which key the client uses to authenticate, and can further prove this fact to a third party. (3) A client can learn whether the server recognizes public keys belonging to other users. Each of these problems lead to tangible privacy violations for SSH users. In this work we introduce a new public-key authentication method for SSH that reveals essentially the minimum possible amount of information. With our new method, the server learns only whether the client knows the private key for some authorized public key. If multiple keys are authorized, the server does not learn which one the client used. The client cannot learn whether the server recognizes public keys belonging to other users. Unlike traditional SSH authentication, our method is fully deniable. Our new method also makes it harder for a malicious server to intercept first-use SSH connections on a large scale. Our method supports existing SSH keypairs of all standard flavors — RSA, ECDSA, EdDSA. It does not require users to generate new key material. As in traditional SSH authentication, clients and servers can use a mixture of different key flavors in a single authentication session. We integrated our new authentication method into OpenSSH, and found it to be practical and scalable. For a typical client and server with at most 10 ECDSA/EdDSA keys each, our protocol requires 9 kB of communication and 12.4 ms of latency. Even for a client with 20 keys and server with 100 keys, our protocol requires only 12 kB of communication and 26.7 ms of latency.

Available format(s)
Publication info
Published elsewhere. USENIX 2022
anonymity identification protocols elliptic curve cryptosystem RSA
Contact author(s)
ldr709 @ gmail com
lyakhovs @ oregonstate edu
jangye @ oregonstate edu
rosulekm @ oregonstate edu
2022-06-09: approved
2022-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lawrence Roy and Stanislav Lyakhov and Yeongjin Jang and Mike Rosulek},
      title = {Practical Privacy-Preserving Authentication for SSH},
      howpublished = {Cryptology ePrint Archive, Paper 2022/740},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.