[OTR-dev] The mpOTR diary: multiparty tripleDH

[George Kadianakis]

I've been thinking of modifying tripleDH for the multiparty scenario
since I read:
https://whispersystems.org/blog/simplifying-otr-deniability/

Doing tripleDH pairwise is definitely possible, but a broadcast
variant is more fun.

My naive idea: Let's assume n participants P_1...P_n. Each participant
P_i has long-term Diffie-Hellman (public key, private key) as (PK_i,
SK_i).

a) Each participant P_i generates ephemeral DH keypair (pk_i, sk_i).

b) Each participant publishes their public keys (both ephemeral and
   long-term). That is, they publish (PK_i, pk_i).         [0]

c) Each participant collects public keys till all n are received (or
   timeout happens XXX).

d) Each participant generates a group key by doing a tripleDH with
   each other participant, concatenating the resulting secrets and
   plugging them in a KDF. That is, for participant P_1, we have:
            k = KDF[DH(PK_1, pk_2), DH(pk_1, PK_2), DH(pk_1, pk_2),
                    DH(PK_1, pk_3), DH(pk_1, PK_3), DH(pk_1, pk_3),
                    DH(PK_1, pk_4), DH(pk_1, PK_4), DH(pk_1, pk_4),
                    ...,
                    DH(PK_1, pk_N), DH(pk_1, PK_N), DH(pk_1, pk_N)]

e) Optional but probably needed: Each participant sends key
   confirmation using the key 'k'.

Trevor, have you played around with this idea?

(Alternatively, maybe the tripleDH scheme could be combined with the
Burmester-Desmedt broadcast cyclic group key agreement scheme [1] to
make a broadcast protocol.)

[0]: Even though it's not required, we need to send our long-term
     public key in that message, otherwise the other party won't know
     which long-term key to use to do the DH operations.

     This is unfortunate, because a protocol that doesn't reveal
     public keys to a passive adversary is quite interesting (I think
     this property is called 'identity hiding' or 'unlinkability' or
     'anonymity'). With such a protocol, the server (or Eve) wouldn't
     be able to know who communicates with whom. XMPP/IRC-layer
     nicknames could become useless and nyms could be assigned based
     on the public key in the OTR layer. Fun times.

     Unfortunately, I don't see a nice & simple way of avoiding to
     send the long-term public key in the first message, except if the
     receiver brute-forces keys using all the public keys in her
     keychain. This is terrible in large keychains.

     A half-assed solution would be to negotiate an identifier in each
     session, that can be used in the next session instead of the
     long-term public key. So instead of (PK_i, pk_i), the participant
     would send (identifier, pk_i), and the receiver would match the
     identifier to a specific public key. If this is combined with the
     Elligator scheme, (PK_i, pk_i) will be indistinguishalbe from
     (identifier, pk_i).

     Still the above idea is not too good. In the first session, the
     PK_i of the other end is sent in the clear. Also, it doesn't work
     well with people who chat from multiple devices. Also, it's not
     very resistant to compromise (if you get owned, your stored
     identifiers are revealed). Still, I find it interesting to think
     about.
     
[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.2268