Latest revision as of 18:48, 2 December 2014

Security Goals

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

General concepts

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")

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.

Messages

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"

Algorithms

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.

@@ Line 19: / Line 19: @@
 Users can only leave the conversation if the server says they left the room.
-(TBD: should users be able to declare that they're leaving, or kick each other out?)
+== 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.
-== Sender keys ==
+Every time a message is encrypted or decrypted with a sender key, the key is afterwards updated to provide forward secrecy:
-When a new user joins, she exchanges AES256 "sender keys" with existing members, encrypted under the "pairwise keys" from pairwise key agreements.  This allows subsequent messages to be encrypted once with a sender key, instead of N times with pairwise keys.
-Every time a message is encrypted or decrypted with a sender key, the key is updated as:
+sender_key = HMAC-SHA256(prev_sender_key, "0")
-sender_key = HMAC-SHA256(prev_sender_key, member_list)
-This provides forward secrecy and ensures new members can't decrypt messages prior to when they joined.
-== 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, ...).  Sequence numbers are implicit, as the server may not be aware of them (e.g. XMPP MUC).
-A new user synchronizes his view of sequence numbers via the QUERY / MEMBER_LIST messages (see below).
-== Causal order ==
-Every user-sent message specifies 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
-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 ==
-Every message specifies its parent's sequence number.  Some messages also specify a transcript hash of that parent and all prior messages.  The hash also covers the sender_key for each message (set to zeros for cleartext messages):
-H(parent) = SHA256(sender_key[parent] || ciphertext[parent] || H(parent-1))
 == Timing ==
@@ Line 55: / Line 31: @@
 * 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 whose parent was received before a message you received more than MAX_RTD + MAX_RTT time ago, 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.
@@ Line 74: / Line 50: @@
 * "Presence" messages sent in clear by the server to indicate a user has entered or left the room
-== Cleartext messages from users ==
+== User messages ==
 === QUERY ===
 * Contains a nonce
-* Requests anyone to send a MEMBER_LIST
+* Requests a MEMBER_LIST
 === MEMBER_LIST ===
-* Lists the sequence number and nonce of the QUERY it's responding to
+* Contains the sequence number and nonce of the QUERY it's responding to
-* Lists the certificate for each member of its parent
+* Contains the transcript hash for the QUERY
+* Contains a certificate for each member as of the QUERY
 === JOIN ===
-* Lists the certificate for the new member
+* Contains a certificate for the new member
-* Contains CONFIRM messages for each member of its parent
+* Contains the sequence number of the MEMBER_LIST it's responding to
-== Encrypted messages ==
 === CONFIRM ===
-* Encrypts-and-confirms an AES256 "sender key" from one member to another
+* 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 a transcript hash
+* 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"
-* Contains a transcript hash
+* Ed25519 signature from the sender's signing key
-* Ed25519 signature from the sender's ephemeral public key
+* Contains the sequence number for its parent
+* The transcript hash and membership of its parent is included as "additional authenticated data"
 = Algorithms =
-== Nonblocking Join ==
+== Blocking Join ==
-On entering a room, a user sends a QUERY.  She is present in the room but hasn't yet joined the conversation.  Someone (or multiple parties) will respond with a MEMBER_LIST.
+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, a present user learns the room's membership and sequence numbers, and can keep track of the membership by observing subsequent JOIN / USER_LEFT messages.
+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.
-To join a room, a present user sends a JOIN, including a CONFIRM for each member in its parent, and expects to receive a CONFIRM from each member shortly.
+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.
-After sending the JOIN, the user considers herself part of the conversation and can send DATA messages and respond to QUERY messages.  She responds to any subsequent JOINs with a CONFIRM.  If the subsequent JOIN doesn't include a CONFIRM for the user (simultaneous join), then she expects to receive one shortly.
+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.
-== Blocking Join ==
+== Nonblocking Join ==
-As above, except:
+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.
-* A user is only added to group membership once all CONFIRMs from her JOIN, and any subsequent CONFIRMS (due to simultaneous join) have been responded to with CONFIRMs.
-* In a simultaneous JOIN case, the JOINs are handled based on the server ordering (earliest first).
+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.
-Example: Alice and Bob are existing members.  Charlie and Dave send simultaneous JOINs, but the server places Charlie's first.  Alice and Bob send CONFIRM messages to both Charlie and Dave.  Charlie and Dave send CONFIRM messages to each other.  Once Charlie receive Alice and Bob's CONFIRMs, he's part of the group and can send DATA.  Once Dave receives Alice, Bob, and Charlie's CONFIRMs, he's part of the group and can send DATA.
+[[Category: mpOTR]]

learn.equalit.ie

Difference between revisions of "Np1sec/SenderKeys"