Changes
===Abstract===
''In this document we present the first public draft of mpSEQ ''(n)sec'' - a secure multi-party communication protocol developed by eQualit.ie with support from the [https://www.opentechfund.org/ Open Technology Fund] and [https://crypto.cat/ Cryptocat]. We include the design rationale, choice of security features, adversarial models, schematic and high level specification of sub-protocols. A subsequent document will present security proofs and implementation details.''
=I. INTRODUCTION=
<span style="font-size:200%">T</span>he mpSEQ ''(n)sec'' project was inspired by [https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html Off-The-Record] messaging protocol and subsequent efforts to explore a multiparty use-case for OTR in [GUVGC09]. mpSEQ ''(n)sec'' is currently developed for [https://github.com/cryptocat/cryptocat/wiki/mpOTR-Project-Plan Cryptocat] - a browser based XMPP chat platform and assumes its use-cases. Most importantly, mpSEQ ''(n)sec'' allows for secure multi-party key exchange and end-to-end encrypted communications without extensive computational requirements from the client. You can follow and contribute to the implementation of [https://github.com/equalitie/libmpotr libmpotr] on our Github pages. Future protocol iterations will consider a variety of other real-world use cases and be platform independent.
In the following section we summarise relevant publications and describe their influence on this protocol. In [[#III._Design_rationale|Section III]], we describe our approach and choice of security features. In [[#IV._Security_Properties|Section IV]], we review the security properties within this protocol. In [[#V._Chat_Session_Model|Section V]] we give basic mathematical definition needed to model the chat session and security proofs for various security aspects of the protocol. [[#IV._Adversarial_Models|Section VI]] provides formal definitions and references to the adversarial models for each property. In [[#VII._Protocol_High_Level_Design|Section VII]] we describe various parts of the protocol and present choices for each sub protocol. In [[#VIII._mpSEQ_Protocol_''(n)sec''_Protocol:_Step_by_Step|Section VIII]], we present each of the mpSEQ ''(n)sec'' protocol steps at various stages in schematic and algorithmic format. We present our choice of primitives in [[#iX._Cryptographic_Primitives|Section IX]]. Finally, we conclude by describing work remaining to be done on this protocol.
= II. History and literature review =
=III. Design rationale =
<span style="font-size:200%">T</span>he main motivation driving mpSEQ ''(n)sec'' development is the lack of a provably secure and implementable multiparty chat protocol offering end-to-end encryption and applicable to a variety of use-cases. Our approach for mpSEQ ''(n)sec'' design was based on the following rationales, listed in order of importance:
# A protocol that is provably secure in a sufficiently strong adversarial model which addresses the most urgent requirement of users in need of security. These are: confidentiality, authenticity and forward secrecy.
To achieve these goals, we focused our studies on the OTR protocol and various subsequent protocols evolved from OTR such as the TextSecure protocol [Sys14], as well as papers offering security analysis of the original OTR protocol. We designate the protocol suggested in [GUVGC09] as our starting point and apply various modifications to reach a desirable protocol which satisfies our goals.
A significant portion of this research suggests a better performing, more secure alternative to the key exchange protocol suggested in [GUVGC09] which is considered by various researchers to be one of the most troubling and inefficient aspects of the proposal. In-session transcript consistency and periodic heartbeats are other major departing points of mpSEQ ''(n)sec'' from mpOTR [GUVGC09].
In designing mpSEQ’s ''(n)sec''’s deniable authentication and key agreement protocol, we have followed the main idea of [ACMP10] in choosing a provably secure authenticated key exchange method and replacing the signature-based authentication with a deniable one. We have chosen the protocol introduced in [ACMP10] instead of [BS07], due to its superior efficiency. We abstract out the method where parties communicate their secret for additional flexibility.
We have chosen the two round SKEME-based Triple Diffie-Hellman deniable key authentication instead of Schnorr signature scheme suggested in [BS07] because it saves us two critical rounds for authentication even though it offers a slightly weaker form of deniability. We have also modified the protocol to represent the chat condition where participants sequentially join and leave the chat.
Another major difference between mpSEQ ''(n)sec'' and the suggested original protocol for mpOTR in [GUVGC09] is in-session transcript authentication, which happens every time a participant receives or send a message. The transcript authentication, which we refer to as transcript consistency check throughout this document, is an optimistic approach based on the assumption that the XMPP server provides a reliable and orderly message delivery.
Additionally, based on the conclusions of [BM] and [RGK05], we are taking the following points into consideration:
* Using a more secure deniable key exchange algorithm, instead of naive Diffie-Hellman, and a more practical algorithm, rather than the peer-to-peer signature key exchange suggested in [GUVGC09].
* Omitting forgeability and malleability from the protocol as recommended by [RGK05] and refraining from broadcasting the expired ephemeral authentication keys. We propose the possibility of using block-based, rather than stream-based, encryption for the symmetric encryption primitives.
* Offering provably secure models for every aspect of the algorithm which formalizes the critical security properties of mpSEQ''(n)sec''.
We also equip mpSEQ ''(n)sec'' with heartbeat to ensure in-session forward secrecy, periodical consistency check and freshness.
= IV. Security Properties =
<span style="font-size:200%">F</span>ollowing the original proposal for the mpOTR protoocol proposed in [GUVGC09] and based on our rationales proposed in Section[[mpSEQ''(n)sec''#Design_rationale|III]], we give an informal description of the properties which mpSEQ ''(n)sec'' aims to secure in a multi-party chat session:<br /><br />
* <span>'''Participant deniable authenticity'''</span> based on their long term persistent identity: While a participant in a chat can be sure of another participant’s authenticity, they cannot prove their confidence to anybody else who has not actively participated in the chat session or who has not interacted with the authenticator prior to the session.
* <span>'''Transcript consistency'''</span>, where all participants are confident that they have been participating in the same conversation; they are confident that they have seen the same sequence of messages.
For each of these requirements, it is necessary to formalize the above mentioned properties against an adversarial model which addresses the elements discussed in [[mpSEQ''(n)sec''#Design_rationale|III]]. The next section will introduce formal definitions covering these elements.
= V. Chat Session Model =
= VI. Threat Models and Adversarial Goals =
<span style="font-size:200%">A</span>dversarial models are explained as a game, in which the adversary's possibilitiy of winning the game should be considered in terms of their ability to break the cryptographic primitives.<br /><br />Accordingly to the requirements discussed in Section [[mpSEQ''(n)sec''#Security_Properties|IV]], it is necessary to examine the algorithm in terms of following threat cases:
# Deniable Authenticated key exchange (including a forward secrecy adversary)
As deniability is not our primary focus, we wil consider a weaker deniability adversarial model, which limits possible input similarly to the limitations considered by [GKR06]. This provision would disallow an input from the 'judge' and therefore saves an extra round of communication within the protocol.
Because he tmpSEQ t''(n)sec'' protocol runs a peer-to-peer key exchange and establishes parallel deniable authentication, we use the adversarial model from [ACMP10] for ''authenticated group key exchange''. This ensures the security of both group and peer-to-peer keys independently. The protocol also takes advantage of "single
round computation of a subgroup key". Meaning that when a participant leaves the session remaining participants can re-establish a (sub)session with only one round of communication. In this circumstance, the model must also consider an adversary's attack against the subgroup key.
===Definition of Adversaries and their advantages===
'''Definition 1''' A ''Confidentiality Adversary'' <math>\mathcal{A}_{conf}</math> is a ppt which can invoke all the functions given in sections [[mpSEQ''(n)sec''#Adversarial_power|IV.1.1.1]] and [[mpSEQ''(n)sec''#Adversarial_power|IV.1.1.3]] with the condition that one of the invocations of TestM is invoked against an instance <math>\Pi^S_i</math> where all instances in session ''s'' are fresh and stay fresh till the end of the game. The game ends when <math>\mathcal{A}_{conf}</math> outputs its guess for ''b'' for that invocation. We say that the protocol is secure if the following function is negligible:
<center>
<math>
==Consistency Adversary==
'''Definition 1''' ''Transcript Consistency Adversary'' <math>\mathcal{A}_{cons}</math> is given the ability to invoke all functions in sections [[mpSEQ''(n)sec''#Adversarial_power|IV.1.1.1]] and [[mpSEQ''(n)sec''#Adversarial_power|IV.1.1.3]]. We say the protocol is secure against ''Consensus Adversary'' if at least two uncorrupted accepted instances <math>\Pi^S_i, \Pi^S_j</math> possess the transcripts chain <math>TransChain_{\Pi^S_i}(l) \neq TransChain_{\Pi^S_j}(l)</math> and they believe they have the <math>TransChain_{\Pi^S_i}(l) = TransChain_{Pi^S_j}(l) with non-negligible probability.
For definition of <math>TransChain_{\Pi^S_i}(l)</math> see Section [[mpSEQ''(n)sec''#Definitions_and_assumptions|VII.4.1]].
= VII. Protocol High Level Design =
<span style="font-size:200%">T</span>o achieve security properties mentioned in [[mpSEQ''(n)sec''#IV._Security_Properties|Section IV]], we break the protocol into the following sub-protocols:
# <span>'''Deniable authenticated signature key and session key exchange'''</span>, where participants deniably authenticate each other and agree on session key(s), while also exchanging ephemeral signing keys.
# <span>'''Transcript consistency verification'''</span>, where parties verify that all have received and seen an identical transcript since the start of the chat session.
Our choice of sub-protocols for mpSEQ ''(n)sec'' has been the use of the same sub-protocols and primitives suggested in [BGB04] and [GUVGC09], except where there has been a practical or security-related reason to deviate from those recommendations.
We have completely replaced the session and signature key establishment protocol. This was done as the original choice of [GUVGC09] for this phase proved impractical in previous implementations. This choice was also motivated by the need to move to a provably secure key exchange. We have moved to elliptic curve cryptography to save on key and signature length in asymmetric primitives.
Following the conclusion of [RGK05] we have dropped forgeability (mandatory publication of ephemeral signature/MAC keys) and malleability. As it is argued in [RGK05] that the deniability of the protocol is based on deniable key exchange. While they increase the complexity of the algorithm, the above properties do not mathematically contribute to deniability. Taking this step also significantly improves the efficiency of the protocol which is a main focus for mpSEQ''(n)sec''. In this sense, although users not participating in session are not be able to forge part of the session transcript, they can forge a whole session with false participants and a complete transcript due to the deniability of the authentication scheme.
We can ensure transcript consistency whenever the underlying transport layer guarantees the reliable delivery of the messages in the same order for all participants.
===VII.1a Sharing a secret among the group===
All AGKE descriptions take the necessary steps to share a common secret confidentially among the group members along side other operations such as authentication and insuring partnership. To insure forward secrecy these methods mostly rely upon a P2P Deffie-Hellman key exchange. Most AGKE descriptions rely on sharing an equation and solving a specific linear system described in [[mpSEQ''(n)sec''#GroupEnc and GroupDec Functions|IX.4]].
We abstract this step as GroupEnc/GroupDec primitive, to allow for alternative designs which do not interact with the rest of the protocol and might offer other benefits. For example the "Naive peer-to-peer" primitive [[mpSEQ''(n)sec''#GroupEnc_and_GroupDec Functions|IX.4]] trades simplicity and generalizability (to a broadcast scheme c.f. [[mpSEQ''(n)sec''#VII.2 Other design possibilities|Section VII.2]]) for bandwidth consumption.
=='''VII.2 Other design possibilities'''==
During the process of designing mpSEQ ''(n)sec'' we have considered, and debated, other design possibilities which we will describe in this section along side our argument in favour of the choice we have made.
==='''VII.2a Group Key Scheme vs Broadcast Scheme'''===
We say a group key scheme (as defined in [[mpSEQ''(n)sec''#V._Chat_Session_Model|Section V]]) is correct if all accepted instances of <math>\Pi^S_i</math> end up with the same participant lists <math>plist_i</math> and compute the same session id.
By contrast, a broadcast scheme refers to a scheme in which each participant is broadcasting a message to a set of participants of their choice from a set of potential participants. Each participant will have its own different <math>plist_i</math> which is able to broadcast as well. <!--In such protocol we define <math>plist_{union} := \cup{i \in {interested participants}} plist_i</math>.-->
Therefore, in the context of a chat room, broadcasting scheme participants do not have the same view of the room and consequently we cannot compute a unified session id <math>sid</math> based on the list of the participants (as opposed to the group key scheme). In a group key scheme, it is the name of the chat room plus a set of ephemeral keys and the set of ephemeral public keys which uniquely identifies the session. There are advantages and disadvantages to each of these schemes, which we enumerate here:
# Chat room simulation: A group scheme simulates a normal chat room in the absence of an authentication adversary, where the participants all have the same view of who is in the chat room when they start talking. This is not the case in a broadcasting scheme as participants keep different participant lists. This is in conflict with the security assumptions of the authentication properties from the original proposal for mpSEQ''(n)sec''.
# Consistency: In a group key exchange, the consistency of the participant list (and session id) is provided by the group key exchange protocol. In such a protocol, extra measures need to be taken only to assure the transcript's consistency, i.e. verification of the consistency of delivery and order of messages exchanged between participants. In a broadcast scheme, a new notion needs to be defined and enforced so that a minimum consistency of a conversation can be simulated. For example, as broadcasting to a subset of potential participants is allowed, the notion needs to deal with a situation in which A receives the DH public key of B but wants to send a message to the "room" before it receives the DH key of C.
# Delayed join and leave: In a group scheme, until all participants confirm their identical view of a new participant list (due to a member joining or leaving the room), they need to assume the status quo. This might delay a new participant from joining a chat or, if no further measure is taken, enable a participant to deny join/leave for the whole group. While various mitigation methods are possible against such attacks (all summarized under the umbrella term "Denial of Service" ) they are not included in threat model considered in mpSEQ ''(n)sec'' protocol.
Based on the above differences, we selected a group key scheme for the proposed protocol. This is primarily because room consistency is one of the main security properties desired. However, when it is critical, the sub-protocol described by [[mpSEQ''(n)sec''#Sending_and_receiving_messages_ while_joining_is__in_progress|VI.II.2b]] allows for communication with users while they are waiting for the join procedure to complete.
===VII.2b Participatory vs individually independent computation of group keys===
== '''VII.3 Message Authentication''' ==
As message authentication needs to be resistant to malicious insiders, following the outline of [GUVGC09], mpSEQ ''(n)sec'' signs each message using a public key signature scheme. The messages are signed with the ephemeral key of the sender. The authenticity of the origin can be verified by the public ephemeral key of the party distributed during the key exchange period.
== '''VII.5 Transcript Ordering and Consistency''' ==
The protocol offered in this document examines the transcript for such consistency. In the case that the underlying transport fails to provide this level of consistency, clearly the consistency test will fail. In this sense, failure of consistency does not distinguish between malicious activities or the absence of a reliable transport.
* We require additionally that message order be preserved for the following reasons:
# XMPP, as the main protocol considered for this design, delivers messages to all clients in the same order.
# The mpSEQ ''(n)sec'' protocol detects if the adversary has manipulated the order of the messages rather than only dropping undesirable messages
# It is simpler to authenticate an ordered transcript compared to an unordered transcript.
As the assumption of having a continuous heartbeat might not be realistic in various asynchronous cases, implementations can assume specific deadlines for dropping users who did not communicate their new keys or shares.
= VIII. mpSEQ ''(n)sec'' Protocol: Step by Step =
<span style="font-size:200%">I</span>n this section we present the mpSEQ ''(n)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].
== '''VIII.1 Schematic view of the key exchange '''==
Although computing a unified session key for all participant is possible, the protocol will compute ''n'' different keys each being used to decrypt the text received from the corresponding participant. In other words, Participant <math>U_i</math> uses key <math>sk_{i,i}</math> to encrypt data. Formally we consider a tuple of <math>sk^S_i := (sk^S_{i,1},sk^S_{i,2},...,sk^S_{i,n})</math> as a session key. This measure has been taken to facilitate the transition to a broadcast use-case where the protocol does not promise same <math>plist</math> for all participants and therefore, it is conceptually impossible to compute a unique key. For more information please see [[mpSEQ''(n)sec''#VII.2b_Participatory_vs_individually_independent_computation_of__group_keys|Section VII2.2b]].
For the high level design of the protocol we do not specify the primitives for ''GroupEnc'' and ''GroupDec'' used in steps 2.4 and -.3. However, we disucss their property and we present some canadidates.
In almost any practical case, participants join the chat sequentially. It is assumed that multiple participants cannot join simultaneously. For the sake of efficiency one can adjust the implementation to have a threshold time to wait and thus start a chat with more participants. However, this makes the implementation significantly more complicated without any evident efficiency benefit.
Therefore, our assumption is that a secure chat is always set up when a participant starts the chat room. Additional participants would be added sequentially using Algorithm [[mpSEQ''(n)sec''#VIII.3_Joining|VIII.3]], as they enter the chat. Algorithm [[mpSEQ''(n)sec''#Chatroom_setup|1]] describes the chat room setup protocol.
'''Algorithm 2'''
=== Join ===
Joining a chat involves two different procedures: the Join procedure, described in Algorithm [[mpSEQ''(n)sec''#Join|2]], which runs on the new participant’s instance, and an Accept New Participant Procedure, described in Algorithm [[mpSEQ''(n)sec''#Protocol_for_other_participants_already_in_the_chat_to_accept_the_newcomer|3]], which runs on the clients of participants that are already in the chat.
When a new participant <math>U_{n+1}</math> joins the chat, current participants can still use their established authenticated ephemeral public key (to derive the <math>sessionKey_{new}</math> and as their signature verification key). Confidentiality of <math>sessionKey_{old}</math> is guarded against the new participant by Diffie-Hellman key shares hashed alongside the session id (which is dependent on the list of participants). The new participant cannot combine the old and new shares to recover <math>sessionKey_{old}</math>. The fact that old participants do not need to compute new ephemeral keys (and re-verify their ephemeral identities) decreases the computational complexity of the protocol.
In situations where a prolonged joining process (due to connection problems or malicious activities) has an adverse effect on the user experience, it might be desirable to enable that joining users can communicate with the parties in the room, while maintaining minimum assurances of authenticity, confidentiality, forward secrecy, as well as consistency only among participants.
Consistency aspects of mpSEQ''(n)sec'', both for the room view (''plist'') and for the transcript, are reached through group agreement. However, there are times when group agreement may be hard or impossible to reach either due to latency in a single participant's connection or due to a single participant broadcasting incorrect confirmation data (such as wrong ''plist'', ''sid'', key share, etc).
We offer an extension to the mpSEQ ''(n)sec'' protocol to tackle this problem during the joining process. When a new participant joins the room, they send their DH key shares to the other participants. The other participants send their ephemeral key in return. They then send their key confirmation and key share. If this extension is to be considered, as soon as each user receives a key confirmation from another user, who is not currently part of the session, mpSEQ ''(n)sec'' displays a message highlighting the fact that although the user is not part of the session the conversation is being shared with them (through P2P encryption using the key derived from DH Key). The protocol, however, does not honour their input in the consistency check until a new session including the new user is set up. Each client can decide whether to disable this option.
The user remains in the list of those not part of the current session, but receives the session messages until a new session is set up. Similarly, when a user receives a message from a user who is not part of the session, mpSEQ ''(n)sec'' will decrypt the message and display it with a disclaimer that the user is not yet part of the session and that some participants may not receive the same message.
In this model, a room is a forwardly secure authenticated communication channel while a session is a subset of the room, which additionally offers a consistent view of the room and consistent messages among participants.
===Leave===
Leaving a chatroom involves a message from a leaving party indicating its intention to leave which, as with all other messages, contains the hash of TranscriptChain and one procedure for those who are staying in the chatroom (Procedure Farewell) which is described in Table [[mpSEQ''(n)sec''#Leave]].
===Farewell===
When the remaining participants receive the farewell message they need to reply with the Hash of TranscriptChain of the last message seen by the leaving user. They also need to re-run the one round key update algorithm. However, they only need a notice from the server that the user is leaving to initiate a subsession excluding the leaving user.
Additionally, failure to receive a heartbeat from a user will result in executing Algorithm [[mpSEQ''(n)sec''#Leave]] excluding users who did not update their key.
'''Algorithm 7'''
=== Secure Send and Receive ===
After the session key is established, participants will use Algorithms [[mpSEQ''(n)sec''#Send|5]] and [[mpSEQ''(n)sec''#Receive|6]] to communicate securely.
On Send, the protocol checks the status of the new ephemeral Diffie-Hellman and key share using messages it receives from participants. It (re)sends any missing pieces. It also informs other participants which part of the key share has been received by the participant. This information is need inorder to enforce in-session forward secrecy. The metadata flag indicates if the message being sent only contains meta data (e.g. heartbeat) or actual user communication.
==IX.1 Hash Function==
SHA256 is being used as the hash function and the random oracle. SHA256 provides a sufficiently secure hash primitive for the level of security provided by mpSEQ ''(n)sec'' and is widely implemented.
==IX.2 Message Origin Authentication ==
<math>GroupEnc((k_{i,1},...,k_{i,n}),z'_i, z'_{i+1}) := z'_{i} \oplus z'_{i+1}</math>
<math>
= X. Conclusion =
<span style="font-size:200%">I</span>n this document, we presented the final draft of mpSEQ''(n)sec''. We hope by receiving public comment on this draft we are able to improve the design. We have referenced the adversarial models which the protocol is supposed to resist. Meanwhile we are working on an implementation of mpSEQ''(n)sec''. We will publish a sequel document which high light the implementation details as well as proof of resistance to the adversarial model presented here.
= XI. References =
</div>
[[Category: mpsecnsec]]
