ZK-SSH - A Zero Knowledge Implementation for OpenSSH

Motivation

SSH provides a secure way of accessing remote systems. This goal can only be achieved if it incorporates user authentication which ensures the identity of a user. Several methods like public key, password and hostbased authentication methods are implemented in OpenSSH.

Public key systems like RSA and DSA provide a reasonable level of security in regard to properties like transferability and impersonation. Nevertheless, these challenge response methods leak in polynomial time information to a third party making it easier to impersonate another party. Although this is nothing to be really afraid of, this problem does not exist when a zero knowledge user authentication protocol is used. Therefore, a zero knowledge protocol was chosen (by Ohta-Okamoto) and implemented for usage with OpenSSH.

Idea behind zero knowledge

Imagine that Alice knows a secret and wants to prove this to Bob. Of course she could just reveal the secret to Bob, but then he would know the secret too. Instead Alice does something like this:

Alibaba's Cave

Alice knows the secret password for Alibaba's cave. Alice goes into the cave and randomly chooses the left or right corridor. Then Bob enters the cave and tells Alice from which corridor she should walk out from. Let's say Bob picked the left corridor. If Alice chooses the left corridor at the beginning, she can just walk the same way back and does not even have to use the password. If she is standing on the right side, she has to use the password, the magic wall opens and she also can walk into the left corridor.

At this point Bob is not very impressed. Alice had a 50% chance of already beeing in the left corridor. So she could have passed the test, even without knowing the password. So Bob plays the same game another round. If Alice passes the test again, Bob is a little more convinced. After a sufficient amount of rounds Bob will believe that Alice knows the secret to Alibaba's cave. For example, after 10 rounds of playing this game, Alice has got a chance of (1/2) to the power of 10, or in numbers 0.0009765625% to pass the test if she does not know the secret.

More Literature about zero knowledge

For an easy to understand and more detailed description of zero knowledge, you can read "How to explain zero knowledge to your children" (available here). If you want to learn more and get deeper into this topic "Zero-Knowledge twenty years after its invention" (available here) would be a good start.

There is also a paper written in German "Zero Knowledge Prinzipien und besondere Sicherheitsgarantien" available from one of the authors. This paper also tries to explain zero knowledge in a simple way. If you want you can grab it here.

How the protocol works

We used a modified version of the Fiat-Shamir protocol introduced by Kazuo Ohta and Tatsuaki Okamoto. It relies on the difficulty to extract the L-th root mod n, when the factors of n are unknown. The description of their scheme can be found here.

Ohta-Okamoto present a sequential version in some detail, and discuss the security of a parallel scheme, but they do not present the parallel protocol's actions. So here you can find a detailed description of the actual scheme used in our implementation.

Downloads

Our implementaion was written for OpenSSH Version 4.0 (both BSD and portable). It has not been tested for the newer versions than 4.0. Also we want to remind you, that this implementation is just a proof of concept and should not be used in production systems.

OpenSSH Source Code

ZK-SSH Patches for OpenSSH

Documentation

How to use ZK-SSH in a few words

It would be wise if you use a prefix for the configure script like

   ./configure --prefix=$HOME/zkssh

so your working installation of OpenSSH will be untouched. This description is based on the assumption that you use $HOME/zkssh as prefix.

After patching and installing the sources you have to edit the config files to enable support for the zero knowledge authentication method. Edit both

   $HOME/zkssh/conf/ssh_config
   $HOME/zkssh/conf/sshd_config

and add the following line to enable zero knowledge support.

   ZeroKnowledgeAuthentication yes

Before you are able to login into your server you have to create a key pair used by the zero-knowledge authentication. Use ssh-keygen with the following command to create the key-pair.

   $HOME/zkssh/bin/ssh-keygen -t oo-zk

By default this will create two files in your .ssh directory:

   ~/.ssh/id_oo_zk containing the private keys
   ~/.ssh/id_oo_zk.pub containing the public keys

Next you have to add the public keys to your authorized_keys file:

   cat ~/.ssh/id_oo_zk.pub >> ~/.ssh/authorized_keys

Now you can start the server and login with the client. If you want to see whats going on, use the verbose option. The server must be started using the full path and since we may be not root we have to use another port. Just assume /home/christschn is your home directory.

   /home/christschn/zkssh/sbin/sshd -ddd -p 2222
   /home/christschn/zkssh/bin/ssh -vvv -p 2222 localhost

Known Issues

Our implementation does not work, if privilege seperation is turned on. If you want to try out our version you have to turn off this feature. By default we allready turned it off in the config files.

About this project

We are all studying "Secure Information Systems" at our university FH-Hagenberg.The idea to implement a zero knowledge authentication in OpenSSH was born during one of our cryptographic lessons. We did so during our 8.th semester with help from our professor Jürgen Ecker.

Contact us

Feel free to contact us about anything regarding ZK-SSH. We are happy about any kind of feedback.

We'd like to thank Jürgen Ecker for teaching us how cryptography works and for beeing our project coach. If you want to contact him, you can do so here.

Last updated on Fri Aug 12 16:49:28 CEST 2005

Valid XHTML 1.0 Transitional Valid CSS