Changes
This changes update the existing protocol paper to bring it into line with the current implementation of the np1sec protocol
<span style="font-size:200%">I</span>n this section we present the ''(n+1)sec'' protocol in algorithmic format. All user IDs should be considered the modulo number of participants in the room.
Deniable authentication is derived from the Triple Diffie-Hellman algorithm presented in [Sys14]. Joining the room is a variation of the two-round mBD+P protocol presented in [ACMP10] where the authentication step has been made deniable. Leaving the room is the one-round mBD+S from [ACMP10]. In both cases, we have added a key confirmation round (round 3) as recommended by [ChMa10] to provide mutual authentication as defined in [GBNM11].
==VIII.1 Schematic view of the key exchange==
|align="center"|Broadcast
|-
|align="center"|-3
|align="center"|11
|align="right"|Check the validity of key confirmation
|align="center"|{{Font color|black|yellow|<math>H(k_{j,i},U_i) \stackrel{?}{=} kc_j[U_i] \; \forall j \neq k</math>}}
|align="center"|Receive
|align="center"|12
|align="right"|Check signatures
|align="center"|<math>Verify_{y_iy_j}(\sigma_j) \; \forall j \neq i</math>
|align="center"|Computation
|-
|align="right"| Generate session key
|align="center"|{{Font color|black|pink|<math>sk_{i} \leftarrow H(GroupDec(k_{i,l} \forall l, z_j ) \forall j, sid_i)=H(z'_1, \dots, z'_n, sid_i) </math>}}
|align="center"|Computation
|-
|align="center"|3
|align="center"|15
|align="right"| Broadcast session confirmation
|align="center"|{{Font color|black|yellow|<math>(sc_{i} \leftarrow H(sk_i,U_i), sigma_i \leftarrow Sign_{x_i}(sc_{i}))</math>}}
|align="center"|Broadcast
|-
|align="center"|-
|align="center"|16
|align="right"|Check the validity of session confirmation
|align="center"|{{Font color|black|yellow|<math>H(sk_{i},U_j) \stackrel{?}{=} sc_j \; \forall j \neq i</math>}}
|align="center"|Receive
|-
|align="center"|
|align="center"|17
|align="right"|Check signatures
|align="center"|{{Font color|black|yellow|<math>Verify_{y_j}(\sigma_j) \; \forall j \neq i</math>}}
|align="center"|Computation
|}
===Triple Diffie-Hellman authentication===
''(n+1)sec'' uses a varient of Triple Diffie-Hellman (TDH) protocol also employed in Textsecure protocol [Mo13] to carry on out mutual deniable authentication as well as peer-to-peer secret key exchange. It can be seen as a variation of [SoKi00] key exchange, however, unlike SoKi00], as it does not multiply all three DH secrets and therefore is not suspticble to attacks mentioned in [BoMa10].
By using TDH secret both in p2p key as well as in key confirmation step, (n+1)sec both implicitly and explicitly authenticate the peers.
|align="center"| -
|align="center"|7
|align="right"|Receive and Check the validity of key confirmation
|align="center"|<math>kc_j \stackrel{?}{=} H(k_{j,i}, U_i)</math>
|align="center"|Receive
|align="center"|Receive
|-
|align="right"|Check the validity of key confirmation of unauthenticated users
|align="center"|<math>kc_j[U_i] \stackrel{?}{=} H(k_{i,j}, U_i)</math> for unauthenticated <math> U_j</math>
|align="center"|Computation
|align="right"| Generate session key
|align="center"|<math>sk_{i} \leftarrow H(GroupDec(k_{i,l} \forall l, z_j ) \forall j, sid_i)=H(z'_1, \dots, z'_n, sid_i)</math>
|align="center"|Computation
|-
|align="right"| Broadcast session confirmation
|align="center"|{{Font color|black|yellow|<math>(sc_{i} \leftarrow H(sk_i,U_i), sigma_i \leftarrow Sign_{x_i}(sc_{i}))</math>}}
|align="center"|Broadcast
|-
|align="right"|Check the validity of session confirmation
|align="center"|{{Font color|black|yellow|<math>H(sk_{i},U_j) \stackrel{?}{=} sc_j \; \forall j \neq i</math>}}
|align="center"|Receive
|-
|align="right"|Check signatures
|align="center"|{{Font color|black|yellow|<math>Verify_{y_j}(\sigma_j) \; \forall j \neq i</math>}}
|align="center"|Computation
|-
On Receive, the protocol updates who has seen which pieces of the key shares. The protocol also generates a new group key if the new key shares have been received from all participants. Those who have not updated their key shares eventually time out via their heartbeat interval.
====Send====
When a participant receives a request for initiating new session, it checks their most current view of participant list (the one with eliminated timed out users) and if it matched then they go ahead with initiating the session, otherwise decline halt the request.
====VIII.9 (n+1)sec Message Dictionary====
All (n+1)sec messages have the following format
:o3np1sec:Base64EnocodedMessage
The Base64EncodedMessage is decoded to sub data fields. There is no delimiter, the fields can be split based on the data size. We use commas (',') only for the purposes of readability in this document. The data types are described as follows.
Bytes (DTByte):
1 byte unsigned value
Shorts (DTSHort):
2 byte unsigned value, big-endian
Length (DTLength):
4 byte unsigned value, big-endian
HashBlock (DTHash):
32 byte data
Opaque variable-length data (DTOpaque):
4 byte unsigned len, big-endian
len byte data
All messages have mandatory version and message type fields:
version (DTShort), message type (DTShort), type-specific part
"version" is equal to 0001.
"message type" is chosen from the following list:
UNKNOWN =0x00, //Invalid
JOIN_REQUEST =0x0a, //Session establishement
PARTICIPANTS_INFO =0x0b,
JOINER_AUTH =0x0c,
GROUP_SHARE =0x0d,
SESSION_CONFIRMATION =0x0e, //In session messages
IN_SESSION_MESSAGE =0x10,
P2P_MESSAGE =0x20,
many messages use "participant id" which is defined as follows:
participant nickname, participant fingerprint (DTHash)
participant nickname is a string. Its size can be determined by the length of the participant id - 32. The participant finger print is a 32bit representation of an ed25519 public key.
"participant info" is defined as
participant id, ephemeral public key (DTHash), authenticated (DTByte)
From the point of view of the sender of the message the participant is authenticated if "authenticated" is 1. Unauthenticated if it is 0.
The following sections will describe the type-specific part for each type of messagee information about the joiner.
=====Join Request=====
participant id, ephemeral publick key (DTHash)
representing the joiner's information.
=====Participant Info=====
session id (DTHash), session view (DTOpaque), key_confirmation(DTOpaque), sender's share(DTHash)
"session view" consists of
participant0_info (DTOpeque), participant1_info (DTOpeque), ..., partcipantn_info(DTOpeque)
where "participant0,...,participantn" are all participants in the session (represented by session id).
"key confirmation" consists of a hash of a triple dh token between the sender and the joining participant and the "participant id" of the joining user.
the sender's share is computed as described in the algorithm.
=====Joiner Auth=====
session id (DTHash), key_confirmation (DTOpeque), signature
"key confirmation" consists of a hash of a triple dh token between the sender and the joining participant and the "participant id" of the joining user.
=====Group Share=====
session id (DTHash), sender share (DTHash), signature (DTHash)
=====Session Confirmation=====
session id (DTHash), session confirmation (DTHash), next session ephemeral key (DTHash)
"session confirmation" is a hash(Session key|sender nickname), the next session ephemeral key is the 32bit public key that the user is going to use in the next session.
=====(n+1)sec in session Message Structure=====
Every (n+1)sec message sent after establishment of a session has the following format:
:o3np1sec:Base64EnocodedMessage
The message has the following structure.
sid (DTHash), Encrypted part of the message, Signature (DTHashx2)
Encrypted message can be decrypted by the session key
sender_index (DTLength), own_sender_id (DTLength), parent_id (DTLength), hash of TranscriptChain of the message (DTHash), nonce (DTHash), message load
"session ID" and the "sender_index" are prepended in part to address concerns of [Da01].
"own_sender_id" is the sequential id assigned to each message by its sender, used for transcript consistency check.
"parent_id" is the global sequential id of the last message seen by the sender before sending the message.
The message also includes the "hash of TranscriptChain" of the parent of the message as "additional authenticated data".
<math>H(TransciptChain[parent(m)])</math>
Note that we send the entry in the chain indexed by <math>parent(m)</math> rather than <math>m</math>. 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.
"nonce" is a random 128 bit value, appended to prevent any possibility of replay or brute force attack.
"message load" is a multi-field message and has the following structure:
sub_message_type(DTShort)
sub_message(DTOpeque) [Optional]
current sub message types are:
USER_MESSAGE: 0001
follewed by the plain text typed by user and handled to (n+1)sec by the chat client(DTOpaque)
LEAVE_MESSAGE 0002
followed by nothing.
If there is no message load, then the message is just an ack, acknowledging receipt of other messages.
====(n+1)sec P2P Message Structure====
Every p2p (n+1)sec message sent after exchange of the ephemeral public keys has the following format.
:o3np1sec:Base64EnocodedMessage
The Base64EncodedMessage is decoded as:
version (DTShort), sid (DTHash), Encrypted part of the message, Signature (DTHashx2)
keyid, Encrypted part of the message, Signature
Encrypted message can be decrypted by the p2p key and has the following structure
Signed Message consists of following parts
keyid, sender id, received id, nonce, User message,
The "Key ID" and the "sender ID" are prepended in part to address concerns of [Da02]. The nonce is a random 128 bit value, appended to prevent any possibility of replay or brute force attack.
User message is the plain text typed by user and handled to (n+1)sec by the chat client.
====VIII.10 (n+1)sec Message Handling====
This section explains the rule - based on which - (n+1)sec governs the order when multiple participants try to join or leave a session simultaneously. Every participant in a chat room has either the status of a "joiner" or a "participant" of a confirmed session exclusively. Based on the user status and the message received, a specific subprotocol needs to be run by the user which is explained in the following sections.
If the message has a session id of a session that the user is part of, then message handling is governed by the finite state machine table described below. Otherwise, the messages should be handled as follows:
=====Joiner====
The Joiner will ignores all messages without session id.
If the message has a session id - of wich the joiner is not a party - the joiner will react as follows:
* ''Participant Info'': the joiner begins a session by appending itself to the list.
* ''Session Confirmation'': re-try to join.
=====Confirmed Participant======
If the received message does not have a session id, then it is a JOIN_REQUEST and can be handled by the current session's finite state machine.
If the received message has a session id, but the confirmed participant is not part of the session then the participant will ignore the message. (The participant is - in this case - leaving the session).
=====Finite State Table=====
{| class="wikitable"
|-
! State/Message !! JOIN_REQUEST !! PARTICIPANTS_INFO !! !! JOINER_AUTH !! GROUP_SHARE !! SESSION_CONFIRMATION !! IN_SESSION_MESSAGE !!
|-
| JOIN_REQUESTED || || auth_and_reshare || || || confirm_or_resession || ||
|-
| RE_SHARED || || confirm_auth_add_update_share_repo || confirm_auth_add_update_share_repo || || ||
|-
| GROUP_KEY_GENERATED || || || || || confirm_auth_add_update_share_repo || ||
|-
| IN_SESSION || init_a_session_with_new_user || || || || mark_confirmed_and_may_move_session || receive ||
|-
| DEAD || || || || || mark_confirmed_and_may_move_session || receive ||
|}
=====Session transmission=====
The session changes when all users have confirmed a session. When a user leaves while another user trys to join, the leave protocol will take priority and a new participant info message is sent to the joining user after all leaving users have left. When multiple users are joining, when the confirmed participant receives the first joiner auth, it will halt the protocol for other joining users. When the session is confirmed, the new participant info list will be sent to the remaining joining users.
= '''IX Cryptographic Primitives''' =
[*CaKr01] Ran Canetti, Hugo Krawczyk. 2001. “Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels” “EUROCRYPT Conference. Lecture Notes in Computer Science”. Edited by Birgit Pfitzmann.
[*ChMa10] Qingfeng Cheng, Chuangui Ma, "Security Weakness of Flexible Group Key Exchange with On-Demand Computation of Subgroup Keys", CoRR, 2010, http://arxiv.org/abs/1008.1221
[*Da14] George Danezis, Should Group Key Agreement be Symmetric and Contributory, http://conspicuouschatter.wordpress.com/2014/06/28/should-group-key-agreement-be-symmetric-and-contributory/
