[OTR-dev] Fwd: Ensuring transcript soundness in a multiparty chat setting

[Trevor Perrin]

On Thu, Dec 5, 2013 at 12:59 PM, Ximin Luo <infinity0 at gmx.com> wrote:
> On 03/12/13 18:12, George Kadianakis wrote:
>>> On Mon, Dec 2, 2013 at 3:43 AM, Ximin Luo <infinity0 at gmx.com> wrote:
>>>> On 02/12/13 02:53, Trevor Perrin wrote:
>>> [...]
>>> You've talked about periodically broadcasting empty messages.  I
>>> think
>>> that's a good idea, particularly if parties can expect that of each
>>> other, as it allows checking for timeliness and liveness of the
>>> whole
>>> group.  Tossing that in, here's my latest:
>>>
>>> --
>>>
>>> Each Message contains:
>>>  - PREDECESSOR list containing the most-recently received message
>>> number from each other participant (equivalently: the number of
>>> messages received from each other Participant)
>>>  - HASH over the predecessor messages (including the sender's
>>>  previous message)
>>>
>
> I still think hashing over all participants is redundant. You only need the direct predecessors, like in the git history DAG. From this, anyone can transitively infer your version of the PREDECESSOR list.

I agree, but hashing the HEAD message from each participant is simple.
 For typical chat group sizes the inefficiency doesn't seem like a big
deal?


>>> A Message's HASH can be verified once all predecessors have arrived.
>>>
>>> Each Participant maintains:
>>>  - An UNVERIFIED pool of received messages whose hashes have not yet
>>> been verified, and an expiration time for each.
>>>  - Lists of RECEIVED messages from each Participant.  The HEAD
>>>  message
>>> in each list is the latest message from that Participant, and has an
>>> expiration.  The tail message in each list is the oldest message
>>>  that
>>> is referred to by an UNVERIFIED message (older messages don't need
>>>  to
>>> be kept around).
>
> I'm not sure this possible in general. If the unverified message has multiple chains of lost messages preceding it, you don't know which "oldest message" is referred to.

Bug!  I think the tail message would have to be the oldest referred to
by any HEAD message (not UNVERIFIED message).  I.e., you don't have to
keep messages older than what everyone has acknowledged seeing.
Sound right?


> One comment (which might be redundant as I'm not up-to-date with all the contextual literature) is that this reduces scalability. This may or may not be a concern, but this would make e.g. a conversation with 30 people more costly. (But perhaps other parts of the protocol, like the handshake, already make this costly, so we will just restrict ourselves to a "small group".)

Good question:  what sort of scale should multiparty chat support?

I think this is even more relevant to the "key agreement" aspect of
multiparty then the consensus-check aspect.

For a small group of N participants, encrypting and sending each
message N-1 times is probably fine (so you could layer the notion of a
conversation atop N^2 OTR conversations, for example).

A more complex scheme like mpOTR allows you to encrypt-and-sign a
single copy of the message, but at the cost of several handshaking
steps to negotiate the group key and "deniable signature" keys.  How
do you determine the cross-over point where that starts being
worthwhile?


Trevor