Np1sec/incremental consistency - Revision history

Dmitri: Dmitri moved page MpOTR/incremental consistency to Np1sec/incremental consistency: protocol renamed

2014-12-02T18:47:57Z

Dmitri moved page MpOTR/incremental consistency to Np1sec/incremental consistency: protocol renamed

Infinity0: /* Consistency */ expand discussion of farewell case

2014-09-17T18:45:28Z

‎Consistency: expand discussion of farewell case

Infinity0: /* Definitions */ make more precise, in the section below explicit-acks might bundle extra crypto material

2014-09-17T18:36:37Z

‎Definitions: make more precise, in the section below explicit-acks might bundle extra crypto material

Infinity0: /* Definitions */ define an explicit-ack

2014-09-17T18:24:30Z

‎Definitions: define an explicit-ack

Infinity0: /* Consistency */ give a summary of the overall consistency strategy

2014-09-17T17:56:34Z

‎Consistency: give a summary of the overall consistency strategy

Infinity0: /* Definitions */ more precise definition with explicit qualifier

2014-09-17T17:37:07Z

‎Definitions: more precise definition with explicit qualifier

Infinity0: /* Definitions */ add a background section for context, and extend definitions

2014-09-17T17:04:08Z

‎Definitions: add a background section for context, and extend definitions

Infinity0: /* Relative ordering */ tone down the terminology, "unsynced" sounds too severe

2014-09-08T19:08:18Z

‎Relative ordering: tone down the terminology, "unsynced" sounds too severe

Infinity0: explain overhead reduction in more detail

2014-09-08T19:03:34Z

explain overhead reduction in more detail

Infinity0: greater-than-or-equals is correct

2014-09-08T18:54:21Z

greater-than-or-equals is correct

@@ Line 39: / Line 39: @@
 Case '''(b)''': when a member ''u'' wants to part, they send a "farewell" message ''m'':
-* Everyone should explicit-ack this message ASAP
+* Everyone should explicit-ack ''m'' as soon as they receive it from the server.
-** This message should contain the next-sender-key, to be used after u leaves, encrypted to everyone except u. This ensures old members can't read new messages even if they eavesdrop.
+** This ack may also bundle any cryptographic material needed for other members to agree on a key or keys that exclude ''u''. For example, in the SenderKeys scenario, this would contain the next sender-key, encrypted to everyone except ''u''.
-** (We could probably do something similar for group keys.)
+* When ''m'' is fully-acked, ''u'' reaches consistency for all previous messages up to ''m'', and may leave.
-* When this message is fully-acked, u gains consistency for all previous messages up to m, and may leave.
+* Messages that others send to ''u'' that are echoed back after ''m'', will not be acked by ''u''.
-** Other messages should be probably be discarded - u won't have a chance to verify their consistency.
+** ''u'' won't have a chance to reach consistency for these messages, even if ''u'' receives them.
 * TBD: need to think about simultaneous parts
 === Parameters and properties ===

@@ Line 26: / Line 26: @@
 Once ''m'' is fully-acked, ''u'' knows that everyone else has seen ''m'' and all messages before it. We'll call the process of gaining that knowledge, "reaching consistency for ''m''" (given context, ''m'' might be implicit). We don't have another mechanism for it, so henceforth we'll use "reach consistency" interchangeably with "reach full-ack", though strictly the former is a security property and the latter is a mechanism for achieving it.
-An '''explicit-ack''' is a message with no other content, that is sent solely for the purpose of declaring (via recv-parent) what the sender has seen. We'll make use of these to ensure consistency is reached in a timely manner, even if no-one wants to send a normal message (that contains user-level contents, and which is an '''implicit-ack''').
+An '''explicit-ack''' is a message with no user content, that is sent solely for the purpose of declaring (via recv-parent) what the sender has seen. We'll make use of these to ensure consistency is reached in a timely manner, even if no-one wants to send a normal message (that contains user-level contents, and which is an '''implicit-ack''').
 == Consistency ==

← Older revision		Revision as of 18:24, 17 September 2014
Line 25:		Line 25:

	Once ''m'' is fully-acked, ''u'' knows that everyone else has seen ''m'' and all messages before it. We'll call the process of gaining that knowledge, "reaching consistency for ''m''" (given context, ''m'' might be implicit). We don't have another mechanism for it, so henceforth we'll use "reach consistency" interchangeably with "reach full-ack", though strictly the former is a security property and the latter is a mechanism for achieving it.		Once ''m'' is fully-acked, ''u'' knows that everyone else has seen ''m'' and all messages before it. We'll call the process of gaining that knowledge, "reaching consistency for ''m''" (given context, ''m'' might be implicit). We don't have another mechanism for it, so henceforth we'll use "reach consistency" interchangeably with "reach full-ack", though strictly the former is a security property and the latter is a mechanism for achieving it.
		+
		+	An '''explicit-ack''' is a message with no other content, that is sent solely for the purpose of declaring (via recv-parent) what the sender has seen. We'll make use of these to ensure consistency is reached in a timely manner, even if no-one wants to send a normal message (that contains user-level contents, and which is an '''implicit-ack''').

	== Consistency ==		== Consistency ==

@@ Line 28: / Line 28: @@
 == Consistency ==
-When a member u wants to part, they send a "farewell" message m:
+We consider two cases: (a) reaching consistency for arbitrary messages during the course of a conversation, and (b) reaching consistency when a user ''u'' leaves. Case (b) may be viewed as a special instance of case (a) plus the additional premise that ''u'' must reach consistency as soon as possible (because they want to leave), and that they don't care about reaching consistency for any subsequent messages that they might receive after their final "farewell" message.
 * Everyone should explicit-ack this message ASAP
@@ Line 37: / Line 44: @@
 * TBD: need to think about simultaneous parts
-When a member u accepts a non-explicit-ack message m at time t:
+Messages that others send to ''u'' that are echoed back after "farewell" will not be acked by ''u'', therefore should not be shown as "seen/acked by u". However, ''u'' may still read them in theory, since they were encrypted to ''u''. Communicating this meaning should be already covered by the same thing as for case (a), though.
-−
-* if u did not send m, and they have not acked m by t+ACK_GRACE_INTERVAL, they should send an explicit-ack
-* if m is not fully-acked (from their POV) by t+(2*BROADCAST_LATENCY)+ACK_GRACE_INTERVAL then issue a local UI warning. Cancel the warning if/when full-ack is reached later.
 === Parameters and properties ===

@@ Line 24: / Line 24: @@
 ** we assume a server-dictated ordering, so accepting a message at seqnum i means we have already accepted all messages j &le; i.
-Once ''m'' is fully-acked, ''u'' knows that everyone else has seen ''m'' and all messages before it. We'll call the process of gaining that knowledge, "reaching consistency". We don't have another mechanism for it, so henceforth we'll use "reach consistency" interchangeably with "reach full-ack", though strictly the former is a security property and the latter is a mechanism for achieving it.
+Once ''m'' is fully-acked, ''u'' knows that everyone else has seen ''m'' and all messages before it. We'll call the process of gaining that knowledge, "reaching consistency for ''m''" (given context, ''m'' might be implicit). We don't have another mechanism for it, so henceforth we'll use "reach consistency" interchangeably with "reach full-ack", though strictly the former is a security property and the latter is a mechanism for achieving it.
 == Consistency ==

← Older revision	Revision as of 18:47, 2 December 2014
(No difference)

@@ Line 1: / Line 1: @@
 This builds on the server-dictated ordered transcript hashes currently mentioned in [[SenderKeys]].
 == Definitions ==
@@ Line 8: / Line 23: @@
 * ''accepted'' means delivered locally, i.e. received, then decrypted-verified including parent hash checks; all causally-previous messages must already be accepted
 ** we assume a server-dictated ordering, so accepting a message at seqnum i means we have already accepted all messages j &le; i.
 == Consistency ==

@@ Line 44: / Line 44: @@
 Ensure that messages received out-of-order are highly visible to the user.
-A message m is ''unsynced'' if seqnum(parent(m)) < seqnum(m) - MAX_UNSYNC_COUNT
+A message m is ''badly ordered'' if seqnum(parent(m)) < seqnum(m) - MAX_UNSYNC_COUNT
 * MAX_UNSYNC_COUNT may either be constant, or a linear function of the number of members, TBD.

@@ Line 13: / Line 13: @@
 When a member u wants to part, they send a "farewell" message m:
-* everyone should explicit-ack this message ASAP
+* Everyone should explicit-ack this message ASAP
-** this message should contain the next-sender-key, to be used after u leaves, encrypted to everyone except u. (Hopefully this addresses the concern Joe brought up.)
+** This message should contain the next-sender-key, to be used after u leaves, encrypted to everyone except u. This ensures old members can't read new messages even if they eavesdrop.
-** could probably do something similar for group keys
+** (We could probably do something similar for group keys.)
-* when this message is fully-acked, u gains consistency for all previous messages up to m, and may leave
+* When this message is fully-acked, u gains consistency for all previous messages up to m, and may leave.
-** other messages should be probably be discarded, u won't have a chance to verify their consistency.
+** Other messages should be probably be discarded - u won't have a chance to verify their consistency.
 * TBD: need to think about simultaneous parts
-When a member u accepts a non-explicit-ack message m at time t
+When a member u accepts a non-explicit-ack message m at time t:
 * if u did not send m, and they have not acked m by t+ACK_GRACE_INTERVAL, they should send an explicit-ack
@@ Line 32: / Line 32: @@
 Both of these should be defined to cover common cases (e.g. 95th-percentile) rather than being mean values.
-This guarantees that a warning shows up if we don't reach consistency within the timeout defined above, ensuring timeliness.
+The above checks should be applied for every single message. This guarantees that a warning shows up if we don't reach consistency within the timeout defined above, and works even if people don't manually send messages.
-In terms of overhead, effectively a user will send a message at least every ACK_GRACE_INTERVAL time period, whilst the session has other people talking. When there is a lull in the conversation, there should be no further messages.
+If we set ACK_GRACE_INTERVAL high enough to match the typical interval between a user's messages, then (in theory) the overhead is only incurred once everyone stops talking and we automatically send off one extra round of acks. While the lull in activity continues, there will be no extra messages, since we don't require explicit-acks to be fully-acked themselves. (Preliminary experiments on some code I wrote shows this to be effective.)
-−
-I'm confident we can tweak the parameters so servers don't see too much extra load, but have not tried to model this precisely.
 We are still vulnerable to a "drop everything" attack, but that can't be helped unless we have unconditionally-periodic heartbeats. Not sure if we want to put these in the upcoming spec.

@@ Line 3: / Line 3: @@
 == Definitions ==
-A message m is '''fully-acked''' (from the POV of a given member ''u'') iff, for all recipients ''r'', ''u'' has accepted a message by ''r'' where seqnum(parent(r)) &gt; seqnum(m).
+A message m is '''fully-acked''' (from the POV of a given member ''u'') iff, for all recipients ''r'', ''u'' has accepted a message by ''r'' where seqnum(parent(r)) &ge; seqnum(m).
 * ''recipients'' possibly includes u, but certainly excludes m's sender