[messaging] Minimal requirements for group chat

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

That's similar to what we do in Briar: each message has a parent
pointer, which is the hash of the message it replies to (if any), and
a timestamp, which is greater than the timestamp of any message
received by the sender before the message was sent (so it's really a
hybrid of a timestamp and a Lamport clock).

This allows messages to be displayed in a tree by using the parent
pointers, or in a flat list by using the timestamps. However, in a
flat list this scheme has the problem you mentioned: someone can
insert a new message before an existing message, changing the apparent
meaning of the existing message (the ice cream attack).

I'm not sure whether any scheme based on pointers and timestamps can
prevent the ice cream attack in a flat UI. As far as I can see, the
only way to prevent it is for the conversation to be an append-only
log. But pointers and timestamps don't achieve that...

Cheers,
Michael

On 16/04/14 21:58, Moxie Marlinspike wrote:
> 
> TextSecure supports group messaging.  I've been meaning to write up
> a blog post about it, but if I understand correctly, you're mostly
> asking about transcript consistency in a "pairwise group" model.
> 
> We believe this can be as simple as including the truncated hash of
> the (sender, plaintext, counter) tuple for the last messages seen
> with every message sent.
> 
> This allows each client to build a view of a message transcript
> that's reminiscent of a git commit log, where each message is a
> commit.  One could imagine visualizing this like an old-school
> email client visualizes conversation threads, which would make
> transcript inconsistencies and "reply intent" clear.  That way if
> Bob sends a message to everyone that says "Who wants to kill the
> president?" except Alice, who Bob instead sends "Who wants to get
> some ice cream?," when Alice responds "I do, how about this
> afternoon!" -- it'd be clear to everyone in the conversation that
> Alice is responding to something they didn't see.
> 
> Unfortunately, that type of UI isn't really possible on mobile
> devices, and even desktop communication apps are moving away from
> those types of threaded views.  For now, TextSecure conversations
> are "linearized," and the way to *display* transcript consistency
> for untrusted groups like these remains an open UI/UX question for
> us.
> 
> But at least at the protocol level, it's pretty simple even in an 
> asynchronous environment.
> 
> - moxie
> 
> 
> On 04/16/2014 08:36 AM, Michael Rogers wrote: Hi all,
> 
> I've been thinking about ways to cut down the forward-secret group 
> chat problem to a manageable size. I'm looking for a core problem 
> that's big enough to be worth solving, but small enough to be
> solved; then we can think up some solutions, prototype them, and
> see whether we can extend them to solve bigger problems.
> 
> Here's a suggestion for a core problem we could start with:
> 
> * Small groups, so O(n^2) bandwidth or processing cost is OK *
> Group membership is fixed for the duration of the chat * All
> members know the membership of the group somehow * All members have
> pairwise OTR connections to all other members * We accept that any
> member can prevent the chat from making progress
> 
> Goals:
> 
> * Messages are forward secret * Messages can be authenticated by
> group members * Messages are repudiable * All members agree about
> which messages are part of the chat * All members agree about the
> order of the messages in the chat * Messages can only be added to
> the end of the chat
> 
> In some ways this is an easier problem than mpOTR, but I think a
> tool that met these goals would be worth having. As far as I know,
> that tool doesn't exist yet.
> 
> Here's a sketch of one possible approach to solving this problem.
> It's basically an append-only log with two-phase commit. Messages
> aren't shown in the UI until they've been committed. (If used over
> a high-latency transport there would need to be some intermediate
> UI state for messages that had been sent but not yet committed.)
> 
> Each member of the group has a copy of the log and a staging area
> for uncommitted messages. Messages in the log are numbered
> sequentially, and each message has a retransmission counter. When a
> member wants to send a message, she assigns the first unused
> sequence number to the message, stages the message, and sends a
> copy of the numbered message to every other member. Each member who
> receives the message stages it and sends an ack to every other
> member, including the author. The ack includes a hash over the
> author's identity, the sequence number, the retransmission counter
> and the content, so everyone knows whether everyone else is acking
> the same message. Each member who receives an ack from every other
> member except the author commits the staged message to the log.
> 
> If a member receives a message with the same sequence number as a 
> staged message, she sends a nack to every other member and
> discards both messages. Anyone who receives a nack for a staged
> message discards the message, except the author, who unstages the
> message. If two or more authors try to send messages with the same
> sequence number, every colliding message will be nacked by at least
> one member, unstaged by its author and discarded by everyone else,
> and the sequence number will remain unused. Each author waits for a
> random interval and then resends her message with an incremented 
> retransmission counter and the first unused sequence number, which
> may be the same as before, or higher if another message has been
> committed in the meantime.
> 
> The retransmission counter prevents confusion between acks or
> nacks for different transmissions of the same message. The
> retransmission interval increases exponentially to avoid repeated
> collisions.
> 
> What do you reckon - is this a problem worth tackling, and does
> this solution seem sound?
> 
> Cheers, Michael
>> _______________________________________________ Messaging mailing
>> list Messaging at moderncrypto.org 
>> https://moderncrypto.org/mailman/listinfo/messaging
>> 
>> 
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTT7RsAAoJEBEET9GfxSfMDQIH/Avv/QVI+Y7YEqCGXRriGlQ0
KY8a5FZPJ4VCW+AFSArGlltI7AhYhaAt51xcfpK6rdgWVJjo/YWloba/chkjdHm4
+zH8sVnAJHrVSkR99Vw14riexQBt6EbT4VZuFElk+PI6jLuXOfkoreycM/kmyaOQ
e8CmGKONFbBxmYFJgrsTE3/XOdDBAS4klJ5K3dABDbHubvxZqMCEoQOxMsh4Blih
8IpVcTrPFjBWFshralYCUUQqf6yWJ4lLbftlxiPjvLEbKuxeolf8q7OrGQOBlCuL
q6tAJ0CrXKjhoTQFKndE+Ci+UVeAcvloMmb7Ajb9yHvJzmD9acJ5KJ33Sohi5zg=
=UQ1N
-----END PGP SIGNATURE-----