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

[George Kadianakis]

Trevor Perrin <trevp at trevp.net> writes:

> On Tue, Dec 3, 2013 at 10:12 AM, George Kadianakis <desnacked at riseup.net> 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:
>>> [...]
>>> >>
>>> >> 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).
>
> Sure, an adversarial server can do whatever it wants.
>
> But in the "benign server" case, I would hope the XMPP message stream
> from Alice to Bob is ordered?  If so, then any ordering violations
> could be detected as an attack?
>

That's a good point.

>
>> 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).
>
> It looks like that's only for handling the case where one party
> silently re-starts, and loses the session context.  In that case, she
> can request a new handshake, and the other party will re-send the last
> message.
>
> Seems like a "best-effort" attempt at handling a common failure case,
> but doesn't provide strong guarantees:
>
> """
> In pathological cases, Bob’s message will be lost, but we hope that these
> will occur rarely enough that dropping the message will not
> impose a great burden on the participants;
> """
> https://otr.cypherpunks.ca/otr-wpes.pdf
>
>
>> 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.)
>
> Yeah, UI is a tough question.  I lean torwards silently forwarding
> messages right away, but later raising an alarm if they don't get
> verified in some timeframe, but I'm not sure.
>

(This is drifting towards bikeshedding, but I consider usability
extremely important so I'll keep poking at it.)

I think forwarding messages first and then raising the alarm might
also be a bad idea.

If we consider transcript mangling a security attack, we shouldn't let
the user decide if the attack is happening or not; or even worse if it
happened in the past (especially since there is no ground truth in
this situation and the decision has to be subjective).

Particularly in stressful/extreme situations, an attacker might be
able
to reorder messages smartly so that he forces the other participant to
take an action before the alarm sounds off. Intense fictional example:

<Alice> do you truly love me, Bob?
# <Bob> of course dear!
# <Charlie> yo you wanna go to the NASCAR race?
<Bob> no...
# <Bob> are you serious?

(Commented out messages are dropped by the adversary and not forwarded
to Alice)

Alice thinks that Bob doesn't love her anymore, and before she sees
the "Alarm: Some messages cannot be verified" warning, she closes her
mpOTR client, jumps into her car, changes her identity and moves to
another town. More extreme and situational examples can be thought
too.

My point is that giving options to users, moves the security to the
decisions of the users. Unfortunately, users can be uneducated (normal
users shouldn't have to know how to read DAGs; even I get confused by
convoluted git branches) or extremely stressed which leads them to
making bad decisions. For some related papers on the usability of
security applications:

* "Anonymity Loves Company: Usability and the Network Effect"
  [http://freehaven.net/doc/wupss04/usability.pdf] and specifically
  section 4 "Case study: against options"

* "Why Johnny Can’t Encrypt: A Usability Evaluation of PGP 5.0"
  [http://www.gaudior.net/alma/johnny.pdf] for its criticism against
  giving users too much information (like DAGs).


That said, I hear Nathan's and Ximin's concerns about messages sent
"at the same logical time", serializing the DAG and how this leads to
weird situations. Specifically, I'm referring to Nathan's paragraph:

Nathan said:
> Suppose we try to ensure every participant sees a *consistent linear
> serialization* of the DAG order. We could do this, for example, by
> sorting branches such as {B, C} consistently such as by the lexical
> sorting of the message hashes. When we consider time, this leads to
> a concerning UI behavior: over time, new messages may not only be
> appended to the linearization of messages, but new messages may also
> be inserted.  For example, if B sorts consistently before C, then a
> user may at one time see [A, C], then later [A, B, C].

Maybe a solution (other than displaying the DAG) that tradeoffs
message delivery speed for correct ordered broadcast, could be
achieved by waiting till a message gets ACKed by all participants
before forwarding it and each neighbors to the application. You can
see a similar approach on the PSync protocol. See "Preserving and
Using Context Information in Interprocess Communication" (specifically
section "4.2 Ordered Broadcast") and "Implementing Fault-Tolerant
Replicated Objects Using Psync" (specifically section "2.1 Basic
Operation" for the definition of *stable* messages).

Of course, the PSync protocol is designed for process communication
which is usually faster than over-the-Internet chat messaging; so the
latency of waiting for stable messages is not too big there. I wonder
how big it would be in a multiparty chat protocol (assuming message
ACKs). The good thing is that chat protocols assume people typing to
each other, which is much slower than network packets.

More thinking is required.

> We should all pause and read this paper:
>
> http://research.microsoft.com/en-us/people/mickens/thesaddestmoment.pdf
>

I did not find that "paper" particularly enlighting :(.
Funny figures maybe.

Cheers!