Diffie Hellmann Dating
Date: 2013-09-27
In the last days the webservice bang with friends came up in the media. This is a service were you can say for each of your facebook friends that you are into them. And only if the other person states the same interest, both are informed that there is mutual interest. This ensures that there is no moment, where one person said "I'm interested in you" and the other one denies the request, which can be hurtful. Although it shouldn't a big deal with adult human beings, but hey humans are complicated.
So what is the problem with this here? Clearly the central instance, in this case facebook, that holds the attraction database. What if i don't trust that third instance, or the third instance loses its database. Then my secret would be unveiled, and everybody would know my interest. But we can do better. So let's collect what should be the central points a better protocol must accomplish:
- No central instance should be necessary to operate the basic version of the protocol.
- A person who denies a request must not get any information about the choice the other person made.
- Both parties know at the same time wether the protocol was successful, or not. This prevents, that the protocol is ended when one person knows the answer, and the other one doesn't.
But there are some points the protcol doesn't have to fix:
- A person with a positive answer, knows that the other one said no. This is just a natural conclusion, since otherwise the protocol would have succeded.
- It cannot prevent people from lying. But hey, nothing can do that.
So what path should we go to accomplish the goals. The basic outline of the protocol is to generate a common secret between the two parties with Diffie-Hellman, which only succeedes if both parties say "yes". Otherwise no common secret should be generated. The second phase utilizes a stepwise challenge-response schema to ensure that both have generated the same secret.
So let's have a look at the common schema for a Diffie Hellman Key exchange (Image comes from Wikipedia and is Public Domain):
So as you see in the process the schema succedes if both parties start with the same "common paint". Our starting point is now, that each party only then uses the "common paint", when it says "yes", otherwise it uses a different paint. We have to choose the different paint in such a way that, no one can conclude from the published fragments wether i've choosen the right common paint or another one. When both start with the common paint, they have a secret in common, otherwise they won't produce a secret.
So now lets implement this stuff with a good DH algorithm. The most used case of DH is the usage of a prime number p and a generator g, which is a primitive root modulo p. p,g together are the common paint. Everybody chooses a private secret s and calculates gsecret_a mod p, which is published. Then the other one does the same with the received public key reveivedsecret_b mod p = gsecret_a * secret_b mod p.
So now to our protocol again; As a prime number and generator we use a secure prime from RFC3526, which is recommended for DH. So iff the person wants to give a positive answer, it uses the suggested generator, otherwise it uses a random number that is different to the generator. This does ensure the protocol fails, but is it possible to detect whether a person has used the correct generator or a random number? Since the generator is a primitive root, its multiplicative group modulo p are all numbers in [0, p-1]. Therefore our published key could also be generated with the correct generator, when we would have chosen a different secret in the first place. This ensures our deniability.
Now at this point both parties have a key, but nobody knows whether the other one has generated the same key. If one party starts to publish its key the other one would already know whether the protocol has succeeded or not, and could stop the protocol without unveiling if he has the same secret.
Therefore we will do a multiple step challenge response schema, where stepwise everybody has to unveil a bit of information. If the bit is not correct the other party knows that the other one hasn't the same secret. He can stop the protocol, or send random answers. In practice we take rounds. Everyone sends a random number. The other has to encrypt the random number with the generated secret and does send back a bit of information about the result (e.g the lowest bit). With each round of challenge-response we gain more confidence that the other does not only guess the results, but really has generated the same key.
So I believe that with this protocol, we have accomplished all features, we needed. To create deniability you have to play this game also with people you don't have interest in. This ensures that you don't know from the fact that the protocol takes place, that someone is interested in you.
So I have implemented this protocol in python, and wrote an plugin for the irssi IRC program. The source code is on github. Please leave some comments if this shit is broken. I would like to improve it.