[messaging] Group messaging consistency under resource constraints

[Ximin Luo]

On 16/10/14 19:51, Trevor Perrin wrote:
> I don't think you've internalized the "asynchronous messaging" use
> case (email, text messages, Pond, TextSecure).  It means messages can
> be sent and received regardless of whether correspondents are online.
> 
> Alice to Bob, Charlie: "Krakens are coming!"
>   <message delivered to Bob but not Charlie>
>   <Alice eaten by Kraken>
> Bob to Alice, Charlie: "Krakens headed Charlie's way!"
>   <message delivered to Charlie>
>   <Bob eaten by Kraken>
> 
> There is no way for Alice's message to be re-transmitted here.  So it
> seems obvious to me that Charlie's client should display Bob's message
> with some indicator that there's a missing predecessor (Alice's
> message), and we need transcript consistency algorithms / UIs that can
> support this.
> 

If out-of-order delivery occurs, this means at least one member (e.g. the sender of the "later" message) *has* seen the missing "earlier" messages, and could in theory supply us with those that we are missing, if they stay alive. (In the above scenario, Bob can pre-emptively try to resend Alice's original message to Charlie, as suggested below.)

If members die (or break their device I guess), then consistency cannot be achieved in *any* system. However, member death can be detected via freshness checks, then the others can choose to start a new session without the dead one. But this introduces some latency, so it might not be satisfactory for your urgent scenario above. (But if a real life situation came up like that, I would pick a transport that is more reliable than the one you're using.)

From the above scenario, it looks like you are favouring a model that prefers delivery of single messages, over consistency. That's a valid design goal, but I don't think one should claim that this achieves (any reasonable level of) transcript consistency. As I described previously, "missing predecessors" makes {gaps that are older than direct predecessors} impossible to detect.

I'd be happy to review other definitions of consistency though. I have done a little bit of thinking about that, but not that much. One alternative model, "single-message consistency" that I proposed in the first post, would do something similar to "missing predecessors" but is more precise and generates actionable warnings; but as mentioned, it would be very costly and probably not suitable under the constraints you're thinking about.

OTOH, if you favour transcript consistency, then I'm not sure what the value is of Charlie seeing Bob's message but not its context (Alice's message). There are a few other scenarios that might have happened, e.g.:

- Charlie misses all messages
- Charlie misses the second message only
- Bob misses Alice's message as well, so that his message points to one that Charlie *has* seen

Having a recovery mechanism would help all of these, whereas "missing predecessors" doesn't help that much.

>> 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.
> 
> So if one party in a group is offline, every new message to them
> contains all previous messages?  That's impractical and a forward
> secrecy problem.
> 

Not all of them - only the ones they haven't acked so far.

If you resend exactly the same ciphertext as before, I don't see how it is a forward secrecy problem - in this model we assume an adversary is storing all ciphertext anyway. However, for Pond, I realised it might pose a linkability problem, so this would need to be tweaked. I am just providing an example of things you *could* do; I haven't looked at this in detail yet, and suspect it will take a fair bit of work.

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/1afbbdf0/attachment.sig>