Transcript consistency

• Recipients are informed of the correct causal order of messages
• Excessively delayed messages are detected

Nonblocking join

• Join and leave are treated as messages, so transcript consistency applies (causal order, delays are detected).
• New users have to "confirm" to existing users to join.
• Existing users have to "confirm" to the new user shortly after the new user joins (e.g. 1 minute).

Room membership

Users can enter and leave the room, as signalled by presence messages from the server (USER_ENTERED, USER_LEFT).

Users can join the room's conversation by sending a JOIN message.

Users can only leave the conversation if the server says they left the room.

Sender keys and Signing keys

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 afterwards updated to provide forward secrecy:

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.
• 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))

Timing

Timing rules can trigger errors based on some assumed constants:

• MAX_RTT - this is the maximum time it should take for a sent message to arrive at all parties. If you send a message and haven't received it back within MAX_RTT, something is wrong.

• MAX_RTD - this is the maximum difference in time when a message arrives at all parties. If you receive a message that's not a successor of a message (X) you received more than MAX_RTD + MAX_RTT time ago, something is wrong. (This is because message X might have arrived at the other party more than MAX_RTD after you saw it, and the other party's message might have taken MAX_RTT to reach you. But after MAX_RTD + MAX_RTT, there's no excuse for the other party not to have seen X).

• MAX_CONFIRM - this is the maximum time an existing member may spend after receiving a new user's JOIN message before sending a CONFIRM message in response. If the new user hasn't received CONFIRM messages from existing membership within 2*MAX_RTT + MAX_CONFIRM, something is wrong.

Generic structures

Certificate

• The user's Curve25519 identity public key
• The user's Curve25519 ephemeral public key
• An Ed25519 signature from the identity key over the ephemeral key

  (Ed25519 signatures can be produced from Curve25519 keys)

Server messages

USER_ENTERED, USER_LEFT

• "Presence" messages sent in clear by the server to indicate a user has entered or left the room

User messages

QUERY

• Contains a nonce
• Requests a MEMBER_LIST

MEMBER_LIST

• Contains the sequence number and nonce of the QUERY it's responding to
• Contains the transcript hash for the QUERY
• Contains a certificate for each member as of the QUERY

JOIN

• Contains a certificate for the new member
• Contains the sequence number of the MEMBER_LIST it's responding to

CONFIRM

• Encrypts-and-confirms an AES256 "sender key" and Ed25519 "signing key" from one member to another
• Uses pairwise TripleDH between sender and recipient keys, i.e.

  HASH( DH(A_id, B_eph) || DH(A_eph, B_id) || DH(A_eph, B_eph) )

• Contains the sequence number for its parent
• The transcript hash and membership of its parent is included as "additional authenticated data"

DATA

• Encrypted under the sender's "sender key"
• Ed25519 signature from the sender's signing key
• Contains the sequence number for its parent
• The transcript hash and membership of its parent is included as "additional authenticated data"

Blocking Join

On entering a room, a user sends a QUERY. Someone will respond with a MEMBER_LIST. If two users try to join simultaneously, the second QUERY will not be responded to until the first user has finished joining.

On receiving a MEMBER_LIST, the new user learns the membership, transcript hash, and sequence number for the QUERY message. To finish joining, the new user sends a JOIN, including a CONFIRM for each existing member. Each member will respond to her JOIN message with a CONFIRM, containing a new sender key.

Until the new user has finished joining, existing members continue exchanging DATA with their old sender keys. Once the last confirmation has been received, existing users switch to their new sender keys.

Once the new user has received all CONFIRM messages from the existing membership, she is successfully joined. If other users sent a QUERY in the meantime, the next one will be responded to with a MEMBER_LIST.

Nonblocking Join

On entering a room, a user sends a QUERY. Someone will respond with a MEMBER_LIST. If multiple users try to join simultaneously, they will all be responded to immediately.

On receiving a MEMBER_LIST, the new user learns the membership, transcript hash, and sequence number for the QUERY message. To finish joining, the new user sends a JOIN, including a CONFIRM for each existing member. Each member will respond to her JOIN message with a CONFIRM, containing their current sender key.

The new user is part of the group once her JOIN message is received. This means that DATA can be sent between group members who have not yet confirmed each other.