[messaging] Group messaging consistency under resource constraints

[Ximin Luo]

On 16/10/14 18:37, Trevor Perrin wrote:
> On Thu, Oct 16, 2014 at 9:53 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
>>
>> There have been arguments that "typical transports don't work like this" and I gave TCP as a counterexample. Trevor also mentioned Pond, but actually this is an example in my favour - Pond delays *sent* messages to defeat some types of timing attack. Come on, this is pretty counterintuitive, but it is made essentially invisible to the user and its security reasoning is solid. So why not delay some *received* messages to defeat some types of consistency attack?
> 
> Messages in Pond are pairwise-encrypted, and different recipients may
> have different mailbox servers.
> 
> Pond doesn't have a notion of group messages.  But if it did, I
> imagine they would still have these properties (in particular, I
> imagine users would *not* want to reveal to mailbox servers what
> groups they are members of, since hiding relationships is the point of
> Pond).  So if the sender goes offline, there's no-one else who can
> re-transmit a lost message.
> 

I'm sure there would be ways to accomplish this. Doesn't everyone already contact the central server via Tor, so the server should not know who is doing the re-sending? Are there particular reasons why you think this might be fundamentally impossible or hard?

> Dropped messages could easily arise, e.g. my network connection is
> interrupted before I've sent my message to everyone in the group.
> 
> In that case, it seems obvious that the UI would have to tolerate
> dropped messages.  Having a single dropped message prevent that
> recipient from seeing the rest of the conversation doesn't seem
> acceptable.
> 

To reason about this more precisely, we would want a model of delay. But, intuitively, in practise I don't think this situation is as severe as you think.

The "prevention" is only temporary, never permanent. This is because, to be able to receive a message out-of-order in the first place, the transport is at least semi-reliable. If it is semi-reliable, then we can fix dropped messages just by resending them intelligently. So we can try to come up with strategies to reduce this time, which is what I hoped people might contribute in this thread. (If the adversary knows which messages to drop, they could have just dropped everything anyways.)

These strategies might work in greatly different ways, too. For example, there is a strategy that results in *no delay*, but takes more bandwidth so is not suitable for TextSecure SMS, but might fit within the larger (but granted, still limited) bandwidth constraints of Pond. Consider this sequence of events (from A's point of view):

A: 1
B: ack(1)
A: 2
A: 3

When Alice sends 3, she knows that Bob has acked 1 but not 2, so she sends {3,2} at the same time. Quoting previous emails accomplishes the same thing, but in a more ad-hoc way.

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141016/cc7f22fd/attachment.sig>