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

[George Kadianakis]

Trevor Perrin <trevp at trevp.net> writes:

> On Wed, Nov 20, 2013 at 4:13 PM, George Kadianakis <desnacked at riseup.net> wrote:
>> Trevor Perrin <trevp at trevp.net> writes:
>>>
>>> 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.
>
> Yes, there could be "race conditions" between messages in these
> different streams.  That's why my example suggested hashing the
> messages "in sorted order (first my 1-9, then Bob's 1-7, then
> Charlie's 1-6)."
>
> This sorting by user would canonicalize away the race conditions.  Yet
> the "causal ordering" of messages would still be preserved (I think)
> since a consensus hash piggybacked on message X is calculated over all
> the messages that X's sender had received before sending X.
>
>
>> 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).
>
> That's OK.  m_b's consensus check doesn't have to include every
> message in C's transcript, it just has to be consistent with C's
> transcript.  Which it is!
>

Ah, I think I understand now:

Because your "consensus check" format contains the number of messages
contributed by each participant, a receiver knows when the "consensus
check" of a message is incomplete and can instead calculate the digest
for that specific subset of messages.

This seems like it might work. But we should still consider some
scenarios:

- What happens if an evil participant selectively sends a message to
  n-1 participants? That is, all participants but one.

  If this happens, the n-1 participants will start including that
  extra message in their consesus check, but the single participant
  who was left out will not be able to calculate a proper digest.

  But I guess that's why you included the timestamp in the consesus
  check [0]: So that after a while (when the missing message can't be
  attributed to network latency) the client of the left out
  participant will be like "hm, something weird is happening with your
  transcript!". And I guess in the meanwhile, the UI of the left out
  client will have to make it obvious to the user that "transcript
  can't be verified!".

  And this brings me to the next comment:

- What happens if the consensus check fails? You said "then this is a
  security error, and the chat is shut down." but shutting down the
  chat so easily might enable DoS attacks that can be triggered by a
  single evil client who sends corrupted consensus digests (and in our
  threat model we assume that some participants can be evil...)
  
Hm. Hm. More thinking needs to be done!

[0]: But timestamps are not fun... They fail on desynchronized clocks
     and they leak information about skewed clocks that might be
     fingerprintable through sessions and even between different
     protocols.