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

[George Kadianakis]

> 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:
> [...]
> >>
> >> But I agree that committing to DAG predecessors would result in
> >> smaller messages, so could be advantageous.
> >>
> >> OTOH, piggybacking all predecessors means the recipient learns
> >> all
> >> predecessors for a message upon receipt of that message.  That
> >> has
> >> advantages too:
> >>
> >>  * In an OldBlue-type protocol, the recipient could issue LostMsg
> >> requests for all missing predecessors right away, instead of
> >> needing
> >> multiple rounds of waiting for lost messages to arrive before
> >> discovering more predecessors.
> >>
> >
> > Multiple rounds could be alleviated without resorting to "all
> > previous
> > messages", if they communicate their own Frontier in the LostMsg
> > message. Then,
> > people handling this LostMsg can infer that the grandparent(s) are
> > also Lost,
> > and retransmit those too.
> 
> That makes sense.  I'll admit I'm not super interested in
> LostMsg/Retransmit algorithms, as we've got existing chat/messaging
> protocols that do an adequate job with reliability (I think?)
> 

I'm also not super interested in LostMsg/Retransmit algrorithms. That
said, I don't think that the current major chat protocols provide
reliability (when the server is adversarial or when a user suddenly
disconnects).

For example, I don't think that XMPP provides reliability or
in-order-delivery on its own (see XEP-0198 and XEP-0184). However,
because it's used over TCP, its streams are both reliable and
ordered. Still, communication between Alice and Bob over XMPP actually
involves two streams: Alice <-> Server and Server <-> Bob.  While each
of those streams is reliable and ordered, nothing tells us that the
communication channel Alice <-> Bob is reliable or ordered if we
consider the server as an adversary (i.e. the server can reorder or
drop Alice's packets before forwarding them to Bob).

FWIW, based on https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html, OTR
itself "assumes a network model which provides in-order delivery of
messages, but that some messages may not get delivered at all (for
example, if the user disconnects).". I think OTR provides its own
reliability by using NAKs and doing retransmissions (at least
according to section 5.1 of the otr-wpes.pdf paper).

Slightly off-topic, but lately when I'm thinking of the network model
of a secure multiparty chat, I've found it helpful to consider a
multiparty chat over a centralized chat protocol (like IRC or XMPP,
where clients send messages to the server and the server broadcasts
them to the other clients). It seems helpful for two reasons: 
a) The server, in centralized protocols, is a powerful network
adversary that can easily reorder, delay or drop messages (it's like
the Global Active Adversary for the distributed case).  Similar
attacks can also be performed by network links in a decentralized P2P
model, but thinking of the centralized case seems easier.
b) In the same protocol-agnostic fashion as OTR, it seems natural to
me that the first instances of secure multiparty chats will use the
popular chat protocols that are currently available. This probably
means XMPP MUCs and IRC, which are both centralized.

What I'm trying to say, is that even though providing reliability in a
multiparty chat protocol doesn't seem like a huge priority, a robust
such protocol should have a way to ensure reliable end-to-end delivery
of its messages.

> 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)
> 
> 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).
> 
> The expirations associated with UNVERIFIED and HEAD messages are for
> timeliness checks:
>  * If there's ever an expired UNVERIFIED message, that means you
> haven't received some predecessor within a reasonable amount of
> time.
>  * If there's ever an expired HEAD message, that means you haven't
> heard anything from some party within a reasonable amount of time.
> 
> On receiving a message, do:
>  - Check that the message has newer predecessors than the previous
> message from this sender
>  - Add the message to the UNVERIFIED pool and the appropriate
>  RECEIVED
> list, and set expiration times
>  - If any message in UNVERIFIED can now be verified, do so, and
>  either
> raise a security fault or delete it from UNVERIFIED
> 
> If you haven't sent a message in X time, send an empty message.
> 
> Thoughts?
> 

I like it. It seems like it would work.

(Would be even better if we could sketch a quick proof for its
soundness too.)

Also, IMHO, messages should not be forwarded to the chat client while
they are in the UNVERIFIED pool. Assuming normal (non-adversarial)
network operation, receiving message predecessors should be quick and
users shouldn't even notice the buffering.

We can even make some "Large amount of unverified messages" or
"Impossible to verify messages from participant X for a while"
warnings that we can forward to the chat application instead.

(I'm saying this, because forwarding unverified messages to the client
with a big fat "UNVERIFIED MESSAGE" warning seems like a recipe for
disaster. Similar to CA-SSL's "The site's security certificate is not
trusted" usability/security nightmare.)