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

[George Kadianakis]

Trevor Perrin <trevp at trevp.net> writes:

> On Sun, Nov 10, 2013 at 1:32 PM, George Kadianakis <desnacked at riseup.net> wrote:
>> Hello again Matthew (and otr-dev),
>>
>> I was recently thinking of ways to make sure that all participants of
>> a multiparty chat see the same transcript at all times. It seems like
>> a very important security property.
>>
>> Papers like mpOTR (and the recent "Improved Group Off-the-Record
>> Messaging" paper by Liu et al. [0]) are "solving" the problem simply
>> by sending out a hash of all previous sent and received messages. This
>> seems like a crude solution that does not even allow you to detect
>> out-of-order messages (which can make a big difference when human
>> beings communicate with each other).
>
>
> Hi George,
>
> I'm wondering if sending a "hash of all previous sent and received
> messages" is really that crude an approach.
>
> Suppose message flow from any user X to user Y is ordered, reliable,
> and all messages arrive within some reasonable time interval, eg 1
> minute.  Then piggybacking a "consensus check" on each message in a
> multiparty chat seems good to me.  For example:
>
> "In this chat, prior to sending this message at time 20130809T0418Z,
> I've received 7 messages from Bob, 6 from Charlie, and this is my 9th.
>  Here is a hash calculated over all these messages, in sorted order
> (first my 1-9, then Bob's 1-7, then Charlie's 1-6)."
>
> If any party receives a message with
>  a) an incorrect hash, or
>  b) whose value is inconsistent with previously-received hashes, or
>  c) where the sender's view is excessively out-of-date, or
>  d) where the receiver's view is excessively out-of-date,
>
> then this is a security error, and the chat is shut down.
>

Hm, I might be confused, but it is my impression that incorrect hashes
of the above scheme can happen even in legitimate situations.

This might happen because while the message flow from user X to user Y
is ordered, you can't guarantee that flows from users X and Z will
arrive neat and ordered to user Y.

For example, let's consider a multiparty chat protocol run and its
three participants A, B and C. Let's also consider that each message
contains a consensus check of the fashion you described.

At some point t_0, it so happens that A and B each send a message (m_a
and m_b) to all other participants at approximately the same time [0].
At t_0, the internal transcript state of A, B and C is the same.

When C receives m_a, the consensus check matches and C updates her
internal transcript state to include m_a.

Now, when C receives m_b, the consensus check won't match since the
internal transcript state of C includes m_a, while the consensus check
of m_b doesn't (B was not aware of m_a when m_b was sent and hence it
was not included in its consensus check).

(Also, if we assume that the first implementations of a multiparty
chat will happen over a centralized chat framework (like XMPP and
IRC), the server can easily cause this reordering simply by delaying
certain messages before forwarding them to the participants.)

Does this even make sense? Where is my fallacy?

[0]: This might mean that both messages are sent at exactly the same
time, or that one message was sent while the other was still on the air.