Np1sec/SenderKeys - Revision history

Dmitri: Dmitri moved page SenderKeys to Np1sec/SenderKeys

2014-12-02T18:48:30Z

Dmitri moved page SenderKeys to Np1sec/SenderKeys

Infinity0: /* General concepts */ move ordering/consistency stuff to main page

2014-09-19T21:26:12Z

‎General concepts: move ordering/consistency stuff to main page

Infinity0: /* Transcript hashes */ explain the nuance wrt message-ID ("commit ID") here

2014-09-08T18:48:09Z

‎Transcript hashes: explain the nuance wrt message-ID ("commit ID") here

Infinity0: /* Causal order */ explain why we can't just set parent(B) == A

2014-09-08T18:21:19Z

‎Causal order: explain why we can't just set parent(B) == A

Infinity0: /* Causal order */ clarify who controls ownseqnum

2014-09-08T18:12:04Z

‎Causal order: clarify who controls ownseqnum

Infinity0: /* Server order */ clarify implicit sequence numbers

2014-09-08T18:09:21Z

‎Server order: clarify implicit sequence numbers

Infinity0: /* Causal order */ fix equiv symbol

2014-09-08T18:04:08Z

‎Causal order: fix equiv symbol

Infinity0: /* Causal order */ fix equiv symbol

2014-09-08T17:59:37Z

‎Causal order: fix equiv symbol

Infinity0: /* Causal order */ a single parent is not enough; add an explicit per-member sequence number and explain why

2014-09-08T17:58:47Z

‎Causal order: a single parent is not enough; add an explicit per-member sequence number and explain why

Trevor at 06:04, 8 September 2014

2014-09-08T06:04:59Z

← Older revision		Revision as of 21:26, 19 September 2014
Line 25:		Line 25:

	sender_key = HMAC-SHA256(prev_sender_key, "0")		sender_key = HMAC-SHA256(prev_sender_key, "0")
−
−	~~== Server order ==~~
−	~~All clients see the same message order from the server. All messages are sent to all users. Aside from the presence messages sent by the server, messages are sent by users.~~
−
−	All messages in a room have a unique sequence number (0, 1, ...). We assume that the server is unaware of sequence numbers (e.g. XMPP MUC); clients must allocate them implicitly when receiving messages.
−
−	This version of the spec does ''not'' support servers that give explicit sequence numbers to messages; this would force us to handle the case where messages are received with explicitly out-of-order sequence numbers. For now, we rely on transcript consistency to detect out-of-order messages for the ''implicit'' sequence number case.
−
−	~~A new user synchronizes his view of sequence numbers via the QUERY / MEMBER_LIST messages (see below).~~
−
−	~~== Causal order ==~~
−	~~Some (all?) user-sent messages specify a "parent" sequence number which is the last message the user received before sending it. Note:~~
−
−	* If Alice sends messages (A,B) in a row, A will not be B's parent unless Alice waits till A is received back from the server. This is because the server may validly insert messages between parent(A) and A, in which case parent(B) being A would contradict the semantics we just stated.
−	* The parent of a message is different from the "previous" message in the server's ordering, e.g. in a "simultaneous send" case two messages will have the same parent.
−
−	~~To prevent the server re-ordering (A, B) when they have the same parent, each message also includes an explicit own-sequence-number, incremented by the sending client themselves.~~
−
−	~~We must enforce a few invariants. For every pair of messages A, B:~~
−
−	* ownseqnum(A) ≤ ownseqnum(B) ⇔ seqnum(A) ≤ seqnum(B) ⇔ seqnum(parent(A)) ≤ seqnum(parent(B)
−
−	~~In practice, and because currently we implicitly allocate seqnums, for each incoming message m we only need to check:~~
−
−	* let p be the latest message received from the same sender (of m). then, check that:
−	** ownseqnum(p) == ownseqnum(m) + 1
−	** seqnum(parent(p)) ≤ seqnum(parent(m))
−	* if p doesn't exist, then instead check that ownseqnum(m) == 0
−
−	Due to server ordering, the sender of message i must have seen all messages with seqnum between 0...parent(i), as well as all messages m with seqnum between parent(i)...i where ownseqnum(m) ≤ ownseqnum(i). Thus, every user-sent message i has a membership set, determined by the JOIN / USER_LEFT messages from 0...i's parent.
−
−	~~== Transcript hashes ==~~
−	~~Encrypted messages include a "transcript hash" of their parent and all prior messages as "additional authenticated data".~~
−
−	~~The hash also covers the sender_key for DATA messages (set to zeros for all other messages):~~
−
−	~~H(parent) = SHA256(sender_key[parent] \|\| msg[parent] \|\| H(parent-1))~~
−
−	Note that we defined H(parent) rather than H(message). This is because a hash may only be calculated once the subject is actually received back from the server (i.e. gets a sequence number). This differs from some other concepts of "message ID" that may be calculated locally.

	== Timing ==		== Timing ==

← Older revision		Revision as of 18:48, 8 September 2014
Line 62:		Line 62:

	H(parent) = SHA256(sender_key[parent] \|\| msg[parent] \|\| H(parent-1))		H(parent) = SHA256(sender_key[parent] \|\| msg[parent] \|\| H(parent-1))
		+
		+	Note that we defined H(parent) rather than H(message). This is because a hash may only be calculated once the subject is actually received back from the server (i.e. gets a sequence number). This differs from some other concepts of "message ID" that may be calculated locally.

	== Timing ==		== Timing ==

@@ Line 38: / Line 38: @@
 Some (all?) user-sent messages specify a "parent" sequence number which is the last message the user received before sending it.  Note:
-* If Alice sends messages (A,B) in a row, A will not be B's parent unless Alice waits till A is received back from the server.
+* If Alice sends messages (A,B) in a row, A will not be B's parent unless Alice waits till A is received back from the server. This is because the server may validly insert messages between parent(A) and A, in which case parent(B) being A would contradict the semantics we just stated.
 * The parent of a message is different from the "previous" message in the server's ordering, e.g. in a "simultaneous send" case two messages will have the same parent.

@@ Line 41: / Line 41: @@
 * The parent of a message is different from the "previous" message in the server's ordering, e.g. in a "simultaneous send" case two messages will have the same parent.
-To prevent the server re-ordering (A, B) when they have the same parent, each message also includes an explicit own-sequence-number, incremented by the client themselves.
+To prevent the server re-ordering (A, B) when they have the same parent, each message also includes an explicit own-sequence-number, incremented by the sending client themselves.
 We must enforce a few invariants. For every pair of messages A, B:

@@ Line 29: / Line 29: @@
 All clients see the same message order from the server.  All messages are sent to all users.  Aside from the presence messages sent by the server, messages are sent by users.
-All messages in a room have a unique sequence number (0, 1, ...).  Sequence numbers are implicit, as the server may not be aware of them (e.g. XMPP MUC).
+All messages in a room have a unique sequence number (0, 1, ...).  We assume that the server is unaware of sequence numbers (e.g. XMPP MUC); clients must allocate them implicitly when receiving messages.
 A new user synchronizes his view of sequence numbers via the QUERY / MEMBER_LIST messages (see below).

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

@@ Line 43: / Line 43: @@
 We must enforce a few invariants. For every pair of messages A, B:
-* ownseqnum(A) &le; ownseqnum(B) &equiv; seqnum(A) &le; seqnum(B) &equiv; seqnum(parent(A)) &le; seqnum(parent(B)
+* ownseqnum(A) &le; ownseqnum(B) &hArr; seqnum(A) &le; seqnum(B) &hArr; seqnum(parent(A)) &le; seqnum(parent(B)
 In practice, and because currently we implicitly allocate seqnums, for each incoming message m we only need to check:

@@ Line 34: / Line 34: @@
 == Causal order ==
-Some user-sent messages specify a "parent" sequence number which is the last message the user received before sending it.  Note:
+Some (all?) user-sent messages specify a "parent" sequence number which is the last message the user received before sending it.  Note:
 * If Alice sends messages (A,B) in a row, A will not be B's parent unless Alice waits till A is received back from the server.
 * The parent of a message is different from the "previous" message in the server's ordering, e.g. in a "simultaneous send" case two messages will have the same parent.
-Due to server ordering, the sender of message i must have seen all
+To prevent the server re-ordering (A, B) when they have the same parent, each message also includes an explicit own-sequence-number, incremented by the client themselves.
-messages from 0...i's parent.  Thus, every user-sent message i has a membership set, determined by the JOIN / USER_LEFT messages from 0...i's parent.
 == Transcript hashes ==

@@ Line 22: / Line 22: @@
 When a new user joins, she generates a new AES256 key (her "sender key") and Ed25519 key (her "signing key").  She then sends these keys to existing members, encrypted under the "pairwise keys" from pairwise key agreements.  This allows subsequent messages to be encrypted-and-signed once, instead of N times with pairwise keys.
-Every time a message is encrypted or decrypted with a sender key, the key is updated to provide forward secrecy:
+Every time a message is encrypted or decrypted with a sender key, the key is afterwards updated to provide forward secrecy:
 sender_key = HMAC-SHA256(prev_sender_key, "0")