[OTR-users] What type of encryption?

[Ian Goldberg]

On Wed, Mar 22, 2006 at 11:30:08PM -0800, CLAY SHENTRUP wrote:
> >
> > > I should read the source, but it's easier just to ask...  Is OTR just
> > > using a single DH group? Does the protocol have support for multiple
> > > groups?  Group sharing/agreement?
> >
> > Yes, a single DH group in v2.  We can add more groups easily enough,
> > though, if we need to in the future.
> 
> 
> Does this mean multiple DH key agreements between duos, or some  way of
> having a group shared secret that every member participates in?

We're still talking about 2-person conversations here.

> > We've talked about this before, and in fact there's a much cooler way to
> > do this, which I totally have plans to implement.  It's called the
> > "socialist millionaire's protocol", and it lets two people determine if
> > they both know the same secret, while revealing no information about
> > each other's secret if they're not the same.  The way that it works is
> > that both sides end up computing r^(sA-sB), where sA and sB are Alice
> > and Bob's secrets (which don't have to have high entropy), and r is a
> > random number neither side learns.  So if the secrets are the same, the
> > value of this expression is 1, and if they're different, it's a random
> > number.
> 
> 
> Can you briefly describe how this happens?  How is sA-sB calculated by
> either party if he can't know the other party's secret?  Who chooses what r
> is...is it the xor of a random value generated by each party.

sA-sB is of course never calculated by either party (since then that
party would be able to calculate the other's secret).  r is calculated
in an only slightly more complicated way than you suggest; because we're
dealing with exponents and group operations and such, we use
r = g_2^{x_a x_b} where g_2 is a (known) generator, and x_a and x_b are
random values chosen by the two parties.  [Note that this looks like a
DH computation, but the important difference is that what would be the
"DH public key" g_2^{x_a} is *not* revealed to the other side.]

For all the details, see Boudot, Schoenmakers, Traor\'e.  "A Fair and
Efficient Solution to the Socialist Millionaires' Problem".
http://www.win.tue.nl/~berry/papers/dam.pdf

   - Ian