Changes

''In this document we present the first public draft of ''(n+1)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.''

<span style="font-size:200%">T</span>he ''(n+1)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]. ''(n+1)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, ''(n+1)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 libmpotrnp1sec np1sec] on our Github pages. Future protocol iterations will consider a variety of other real-world use cases and be platform independent. Please use the [[Talk:Np1sec|Discussion]] page to ask questions and leave comments.

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._''(n+1)sec''_Protocol:_Step_by_Step|Section VIII]], we present each of the ''(n+1)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 define the work remaining that [[#Next_Steps|remains to be done ]] on this protocoland [[#XI._Acknowledgements|acknowledge]] the good people who have helped us get here.

<span style="font-size:200%">T</span>wo-party Off The Record messaging (OTR) was introduced in [BGB04] as an alternative to PGP for secure casual Internet chat by providing necessary forward secrecy and deniable transcript features. [BGB04] The paper proposes the use of symmetric encryption and message authentication in OTR for confidentiality and integrity, and the Diffie-Hellman key exchange for authenticating the other party in the chat. Since publication in 2004, the paper it has defined the standard for secure Internet chat attracting a lot of academic attention and security analysis. The OTR protocol is now at [https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html Version 3] and the [https://otr.cypherpunks.ca/index.php#downloads libotr software libraries] are continuously updated. Our research and literature review focused on the protocol presented in [BGB04] and the subsequent proposal for a multiparty use-case in [GUVGC09].

An unauthenticated exchange of the OTR version identifier can pose a threat to authenticity as shown in [BM]: the adversary can force clients to downgrade to an older, (potentially insecure ) version of the protocol. They also note the Diffie-Hellman key exchange failure in delivering authentication in the presence of an active adversary. Furthermore, they show that the early publication of MAC keys for the purpose of forgeability can easily enable the active adversary to forge messages during the conversation (instead of the intended forgeability after the conversation has ended). Finally, they argue that in an environment where the adversary is controlling the whole network, she can effectively disarm the protocol of its forgeability property.

Various attempts have been made to construct an efficient multiparty (known as group) authenticated key exchange protocol. OTR authors proposed a generalisation of two-party OTR to a multiparty use-case in [GUVGC09]. However, they did not specify the cryptographic primitives, neither did they give a formal definition of the adversaries nor the proof of the algorithm’s security (reduction). Although a more robust key exchange is proposed, some primary performance analysis of the implementation of the key agreement protocol has been shown to be impractically slow, especially on mobile devices [Gun13a][Git11]. [LVH13] proposes GOTR as an alternative to [GUVGC09] with a goal of improving on some of its security properties. A notable change is the use of p2p private channels to send message digest so as to establish transcript consistency and implicit message origin authenticity between users. GOTR also strives to improve on repudiability by considering deniability against an 'online judge' as well as forgeability for the entire transcript by a single party (this is possible in [GUVGC09] as long as a deniable AKE is being used). The idea of online repudiabilty relies on the judge controlling up to '''N-2''' parties while the two remaining "honest" parties are allowed to collude. This is slightly unusual for both repudiability and honesty. [LVH13] also proposes an involved contributory BD based key agreement scheme, which disregard room consistency and turns GOTR into a broadcast scheme (c.f. [[#Appendix_B:_Other_design_possibilities|Appendix B]]).

<span style="font-size:200%">TO</span>he main motivation driving ''(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 ur approach for ''(n+1)sec'' design was based on the following rationalesrequirements, listed in order of importance:

# A protocol that is provably secure in a sufficiently strong adversarial model which that addresses the most urgent requirement of users in need of security. These are: confidentiality, authenticity and forward secrecy.# Usability according Applicable to real world the [https://github.com/cryptocat/cryptocat/wiki/Design-and-Functionality Cryptocat XMPP use-cases.case]# Providing some degree of deniability when it does not negatively impact usability or our [[#IV._Security_Properties |security goals]]# Addressing security flaws in the OTR protocol.[BGB04] and [GUVGC09]

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 satisfying the above stated goals.

A significant portion of this our research suggests suggested 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 Based on conclusions in [BM] and periodic heartbeats are other major departing points of ''(n)sec'' from mpOTR [GUVGC09RGK05]., we are making the following design changes:

In designing ''(n)sec''’s deniable authentication and key agreement protocol, we have followed the main idea of [ACMP10] in choosing * Using a provably more secure authenticated deniable key exchange method and replacing the signature-based authentication with a deniable one. We have chosen the protocol introduced in [ACMP10] algorithm, instead of [BS07], due to its superior efficiency. We abstract out the method where parties communicate their secret for additional flexibility.naive Diffie-Hellman

We In designing ''(n+1)sec''’s deniable authentication and key agreement protocol, we have chosen followed [ACMP10] by choosing a provably secure authenticated key exchange method and replacing the two round SKEMEsignature-based Triple Diffie-Hellman deniable key authentication with a deniable one. We have chosen the protocol introduced in [ACMP10] 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, due to its superior efficiency. We have also modified abstract out the protocol to represent the chat condition method where participants sequentially join and leave the chatparties communicate their secret for additional flexibility.

Another major difference between ''(n)sec'' and * Using a more practical algorithm, rather than the suggested original protocol for mpOTR in [GUVGC09] is inpeer-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.-peer signature key exchange

Additionally, based on We have chosen the conclusions two round SKEME-based Triple Diffie-Hellman deniable key authentication instead of the Schnorr signature scheme suggested in [BMBS07] 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 [RGK05], we are taking leave the following points into consideration:chat.

* 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 ''(n)sec''.

Following conclusions in [RGK05] we have dropped forgeability (mandatory publication of ephemeral signature/MAC keys) and malleability from our requirements since protocol deniability is based on a deniable key exchange. This significantly improves protocol efficiency, a primary focus for ''(n+1)sec''. The deniability of the authentication scheme prevents users not present in a chat session from forging a part of the transcript, however it allows them to forge a whole session with false participants and a complete transcript. Another major departure from the suggested protocol in [GUVGC09] is in-session transcript authentication, which happens every time a participant receives or sends a message. Transcript authentication (referred to as transcript consistency check from here on) is an optimistic approach based on the assumption that the chat server is mandated to provides a reliable and orderly message delivery, as it is in the case of XMPP protocol. We can ensure transcript consistency whenever the underlying transport layer guarantees the reliable delivery of the messages in the same order for all participants. If however, the underlying protocol does not guarantee reliability either in delivery or order, we report the discrepancy in user's transcript compared to their peers but we do not attempt to correct the transport protocol's action (we offer detection but not recovery). We also equip ''(n+1)sec'' with heartbeat to ensure in-session forward secrecy, periodical consistency check and freshness. We propose the possibility of using block-based, rather than stream-based, encryption for the symmetric encryption primitives.  Finally, other protocol design possibilities considered and the rationale for not pursuing them further is discussed in [[#Appendix_B:_Other_design_possibilities|Appendix B: Other design possibilities]]

<span style="font-size:200%">F</span>ollowing from the original proposal for the mpOTR protoocol proposed in [GUVGC09] and based on our design rationales proposed in Section[[''(n+1)sec''#Design_rationale|III]], we give an informal description of the properties which ''(n+1)sec'' aims to secure in a multi-party chat session:<br /><br />

* <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 requirements stated in [[''(n)sec''#Design_rationale|Section III]]. The next section will introduce formal definitions covering these elements.

<span>'''Definition IIIV.1 Multi-party chat session'''</span>'': Let <math>\mathcal{U} = \{U_1,...,U_m\}</math> be the set of possible participants. A multi-party chat session is an ordered pair <math>S := (\mathcal{S}, sid)</math> in which <math>\mathcal{S} \subset \mathcal{U}</math> and <math>sid</math> is the unique session id. Without loss of generality we assume <math>\mathcal{S} = \{U_1,...,U_n\}</math> and we interchangeably refer to party <math>U_i</math> by index ''i''. Furthermore, it is assumed that party <math>U_i</math> is presented and identified verifiably by a long-term persistence key pair <math>(LPK_{U_i}, LSK_{U_i})</math>.''

<span>'''Definition IIIV.2 sub session'''</span> After session ''S'' is established, A subset of participants <math>\mathcal{T}\subset \mathcal{S}</math> might want to start a session in which parties in <math>\mathcal{T}\backslash\mathcal{S}</math> are excluded (for example when those parties leave the chatroom). In such a setting we say <math>T := (\mathcal{T}, sid^T)</math> is a subsession of ''S''. When there is no need to specify the subsession of choice, we use <math>spid</math> to refer to <math>sid^T</math>.

<span>'''Definition IIIV.3''' ''An'' '''authenticated group key exchange (AGKE)'''</span> ''is Algorithm <math>\Pi</math> which each honest party will execute in order to communicate (by means of sending, receiving or computing) a cryptographic secret - namely a key - among the other parties of a session. By <math>\Pi^S_i</math> (or <math>\Pi_i</math> when the underlying session is understood) we are referring to an instance of <math>\Pi</math> which the party <math>U_i</math> executes to achieve the collective goal. Further more we define'':

* <span>'''Participant list'''</span>'': <math>plist^S_i</math> is the list of participants which <math>U_i</math> believes are participating in the chat session ''S''.''When there is no ambiguity in the underlying session, we simply use <math>plist_i</math> notation.* <span>'''key id'' is the serial number given to the P2P keys generated during the process of key exchange, is computed as <math>Hash(U_i|y_i|U_j|y_j)</math>.* <span>'''Ephemeral key list'''</span>'': <math>klist^S_i</math> is the list of ephemeral public key <math>y_j = g^{x_j}</math>'s of all participants which <math>U_i</math> believes they are using in the chat session ''S''.'' When there is no ambiguity in the underlying session, we simply use <math>klist_i</math> notation instead. We use the notaion of <math>plist_i|klist_i</math> to represent ordered concatenation of <math>U_i|y_i</math> pairs as in <math>U_1|y_1|\dots|U_n|y_n</math>. The order is assumed to be computable by all participants (lexicographically ordered using long term public key of participants, for example).

<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 [[''(n+1)sec''#Security_Properties|IV]], it is necessary to examine the algorithm in terms of following threat cases:

Because he t''(n+1)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

* <span>'''RevealGK(<math>\Pi^S_i</math>)}''': <math>\Pi^S_i</math> gives <math>sk_i</math> to <math>\mathcal{A}_a</math> if it has accepted (as defined in Definition III.3).

condition that the TestSK TestGK is invoked '''at least once''' against a fresh instance <math>\Pi^S_i</math> which stays fresh until the end of the game. The game ends when <math>\mathcal{A}_{join}</math> outputs its guess for ''b''. We say a key exchange protocol is secure if the following function is negligible:

We do not define an independent forward secrecy adversary. Forward secrecy can be derived by resistance against the confidentiality adversary as well incorporating a forward secure key exchange as described in [GBN10]. The adversaries of Definition VI.3 and VI.4, are able to ''Corrupt'' users after the communication of DH secrets. Therefore they can trivially break an AKE which without forward secrecy. In this sense, the resistance against forward secrecy adversary is included in AKE adversarial model.

'''Definition 1''' A ''Confidentiality Adversary'' <math>\mathcal{A}_{conf}</math> is a ppt which can invoke all the functions given in sections [[''(n+1)sec''#Adversarial_power|IV.1.1.1]] and [[''(n+1)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:

'''Definition 1''' ''Transcript Consistency Adversary'' <math>\mathcal{A}_{cons}</math> is given the ability to invoke all functions in sections [[In ''(n)sec''#Adversarial_power|IV.+1.1.1]] and [[''(n)sec''#Adversarial_power|IVprotocol, we attempt to ensure the consistency among participants all along the session incrementally, i.1e.1assuring consistency after receiving each message in a timely manner.3]]. We say However, we do not model the incremental aspect of consistency into the protocol is secure against ''Consensus Adversary'' if at least two uncorrupted accepted instances <math>\Pi^S_iadversarial model, \Pi^S_j</math> possess for 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 probabilitysake of simplicity.

'''Definition 1''' ''Transcript Consistency Adversary'' <math>\mathcal{A}_{cons}</math> is given the ability to invoke all functions in sections [[''(n+1)sec''#Adversarial_power|IV.1.1.1]] and [[''(n+1)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 [[''(n+1)sec''#Definitions_and_assumptions|VII.4.1]].

<span style="font-size:200%">T</span>o achieve the security properties mentioned listed in [[''(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>'''Communication'''</span>, where parties send authenticated confidential messages.# <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 ''(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 # <span>'''Deniable authenticated signaturekey and session key exchange'''</MAC keys) span>, where participants deniably authenticate each other and malleability. As it is argued in [RGK05] that the deniability of the protocol is based agree on deniable session key exchange. While they increase the complexity of the algorithm(s), the above properties do not mathematically contribute to deniability. Taking this step while also significantly improves the efficiency of the protocol which is a main focus for exchanging ephemeral signing keys# <span>''(n)sec'Communication'. In this sense''</span>, although users not participating in session are not be able to forge part of the session transcriptwhere parties send authenticated confidential messages# <span>'''Transcript consistency verification'''</span>, they can forge a whole session with false participants where parties verify that all have received and a complete seen an identical transcript due to in the deniability same order, since the start of the authentication schemechat session after receiving each messages.

We can ensure transcript consistency whenever the underlying transport layer guarantees the reliable delivery Our choice of the messages in the same order sub-protocols for all participants''(n+1)sec'' followed suggestions made in [BGB04] and [GUVGC09], except where there has been a practical or security-related reason to deviate from those recommendations.

We have chosen our deniable signature key exchange protocol following the conclusions in [Gun13b] - by identifying a secure key exchange protocol that satisfies our needs. We then apply the triple Diffie-Hellman authenticated exchange to grant it properties of deniability[Ma13]. Subsequently, one can apply the same approach presented in [Gun13b] to communicate ephemeral signature keys during the key establishment process. However, for efficiency, we use the same ephemeral Diffie-Hellman private and public values used to deniably authenticate users and generate secret shares to produce ephemeral signatures.

* Although the Schnorr based algorithm suggested in [BVS05] satisfies a more comprehensible deniable model, Triple triple Diffie-Hellman authenticated key exchange only needs two rounds of communication and can be done alongside the key agreement steps, while the Schnorr based algorithm of [BVS05] needs four rounds.

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 [[''(n+1)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 [[''(n+1)sec''#GroupEnc_and_GroupDec Functions|IX.4]] trades simplicity and generalizability (to a broadcast scheme c.f. [[''(n+1)sec''#VII.2 Other design possibilities|Section VII.2]]) for bandwidth consumption.

=='''VII.2 Other design possibilities3 Message Authentication'''==During the process of designing ''(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 [As message authentication needs to be resistant to malicious insiders, following the outline of [GUVGC09], ''(n+1)sec''#Vsigns each message using a public key signature scheme._Chat_Session_Model|Section V]]) is correct if all accepted instances of <math>\Pi^S_i</math> end up The messages are signed with the same participant lists <math>plist_i</math> and compute ephemeral key of the same session idsender. The authenticity of the origin can be verified by the public ephemeral key of the party distributed during the key exchange period.

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>= '''VII.-->4 Transcript Ordering and Consistency''' ==

Therefore, in Since each message sent by any one participant is signed by 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 ephemeral private key generated for that specific 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 not possible for the name of the chat room plus internal or external adversary to forge a set message on behalf of ephemeral keys and the set of ephemeral public keys which uniquely identifies the sessionan uncorrupted participant. 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 However, if the absence of an authentication adversaryis controlling the network structure, where the participants all have the same view denial or delay of who service is in the chat room when they start talkingalways possible. 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 ''(n)sec''.# Consistency: In a group key exchange, the The consistency of the participant list transcript (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 all 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, see the notion needs to deal with a situation same transcript in which A receives the DH public key of B but wants to send a message to same order) relies on the "room" before it receives the DH key means of C.# Delayed join and leave: In a group schemetransport guaranteeing reliable delivery, until all participants confirm their identical view of with a new participant list (due to a member joining or leaving the room)single order, they need to assume the status quoevery participant. This might delay a new participant from joining a chat orIn other words, if no further measure is taken, enable a participant to deny join/leave for the whole group. While various mitigation methods we are possible against such attacks (all summarized under verifying the umbrella term "Denial ''reception'' of Service" ) they are not included in threat model considered in the message by the intended ''(n)secrecipients'' protocol.

Based on the above differencesBy assuring transcript consistency, we selected a group key scheme for the proposed protocol. This is primarily because room consistency is one of the main security properties desired. Howeveralso preventing <math>U_i</math> from sending different messages to <math>U_j</math>, when it is critical, the sub-protocol described by [[''(n)sec''#Sending_and_receiving_messages_ while_joining_is__in_progress|VI.II.2b]] allows for communication with users <math>U_k</math> while they believe they are waiting for seeing the join procedure to completesame conversation. ===VII.2b Participatory vs individually independent computation of group keys===Most AKGE offer some degree of contributiveness in computing the group secret. This roughly means that (at least in the In absence of an insider) the group secret transcript consistency, when a central server is derived using contribution from all members of managing the group. There has been criticism of the importance of chatroom, this property such as in [Da14]. In this section we consider briefly the arguments for each side and describe the rational for our choice. == '''VII.3 Message Authentication''' == As message authentication needs attack requires <math>U_i</math> to be resistant to malicious insiders, following the outline of [GUVGC09]conspire with server, which is permeable in ''(n+1)sec'' signs each message using a public key signature scheme. The messages are signed threat model in accordance with the ephemeral key definition 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''' == Because each message sent by each participant is signed by the ephemeral private key generated for the specific session, it is not possible for the internal or external adversary to forge a message on behalf of an uncorrupted participant. However, if the adversary is controlling the network structure, denial or delay of service is always possible. Hence, the transcript consistency of the transcript (meaning that all participants see the same transcript in the same order) relies on the means of transport guaranteeing reliable delivery, with a single order, to every participant. Another way of viewing this is that we are verifying the ''recipients'' of a message[GUVGC09].

''(n+1)sec'' performs transcript authentication whenever a message is received. This is to guarantee consistency and protect the protocol against the transcript consistency attack. The procedure is similar to the procedure described in [GUVGC09], with two major differences:

# The ''(n+1)sec'' protocol detects if the adversary has manipulated the order of the messages rather than only dropping undesirable messages

==''' VII.5 Asynchronous communication and Forward Secrecy '''== The protocol is primarily targeted to synchronous cases, however, with some modification it can be used for asynchronous cases. Provided that the participants are not concerned with authenticating the list of participants (it is OK if Eve impersonates Bob as long as she is unable to read Bob’s messages). Participants can communicate using their pairwise exchanged ephemeral Diffie-Hellman keys until all participants finish the second round of authentication. As soon as a deniable handshake has been established among a set of participants any subset of them can communicate and authenticate their messages using the “session key” and their ephemeral signature key. The protocol does not enforce explicitly a time limit on renewing the session key shares and can be used for an asynchronous high latency transport after the key establishment state. The downside of using a session key for a long time is that a compromised session key will reveal all past communication during that session. This does not pose an imminent threat when the life span of a chat is short. However, in the context of asynchronous high latency transport, it is a more serious concern. The protocol requires the participants to pre-emptively update their ephemeral signature/shares and propagate them as part of the messages they are already sending. Subsequently, they also update their key share with their neighbours as soon as the neighbours also propagate their new ephemeral signature keys. 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. ''(n+1)sec'' Protocol: Step by Step =

<span style="font-size:200%">I</span>n this section we present the ''(n+1)sec'' protocol in algorithmic format. All user Ids 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 '''==

Although computing The protocol computes a unified session key for all participant is possibleparticipants. This imposes, in particular, the protocol will compute ''n'' different keys each being used to decrypt the text received from the corresponding participant. In other words, Participant necessity that all <math>U_iplist_i</math> uses key <math>sk_{i' is identical for all participants.However,i}</math> to encrypt data. Formally we consider a tuple as consistent view is part of <math>sk^S_i := ''(sk^S_{i,n+1})sec'' security model,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 it does not impose extra limitation on 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 [[''(n)sec''#VII.2b_Participatory_vs_individually_independent_computation_of__group_keysParticipatory_vs_individually_independent_computation_of_group_keys|Section VII2.2bAppendix B: Participatory vs individually independent computation of group keys]].

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. Howeversimplicity, we disucss their property and we present some canadidatesgroup operation is written multiplicatively (even though it is actually an elliptic curve point operation traditionally represented by addition).

For simplicity, group operation is written multiplicatively, although it is actually an elliptic curve points operation traditionally represented by addition. Where ever Whenever our design deviates from [ACMP10], it is marked by in {{Font color|black|yellow|yellow}}. Pink means we We have abstracted out the step steps mentioned in [ACMP10] as an independent primitivein {{Font color|black|pink|pink}}, however the resulting computation is identical with the one in [ACMP10] protocol:

!align="center"|RndRound!align="center"|Step

|align="center"|1.1|align="center"|2

|align="center"|1.2|align="center"|3

|-''(n+1)sec''|align="center"|2.1|align="center"|5

|align="center"|2.2|align="center"|6

|align="center"|BroadcastComputation

|align="center"|2.3|align="center"|7

|align="center"|<math>z'_i := \leftarrow (H(k_{i,j}, sid_i) \, \textrm{for } \, j \neq i \, \textrm{and} \, j \in \{1,\dots,n\})</math>

|align="center"|2.4|align="center"|8

|align="center"|{{Font color|black|pink|<math>z_i \leftarrow GroupEnc(k_{i_ji,j} \, \textrm{for } \, j \neq i \, \textrm{and} \, j \in \{1,\dots,n\}, z'_i)</math>}}

|align="center"|2.3|align="center"|9

|align="center"|2.4|align="center"|10

|align="center"|-3|align="center"|11|align="right"|Check the validity of key confirmation|align="center"|{{Font color|black|yellow|<math>kc_k[H(k_{j] ,i},U_i) \stackrel{?}{=} kc_j[kU_i] \; \forall j \neq k</math>}}

|align="center"|<math>Verify_{y_iy_j}(\sigma_j) \; \forall j \neq i</math>

|align="center"|{{Font color|black|pink|<math>sk_{i,j} \leftarrow H(GroupDec(k_{i,jl}\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>}}

== =Triple Diffie-Hellman authentication===''(n+1)sec'VIII' uses a varient of Triple Diffie-Hellman (TDH) protocol also employed in Textsecure protocol [Mo13] to carry 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. In Algorithm 1, TDH and the original group key exchange from [ACMP10] has been combined to provide a deniable authenticated group key exchange. Here, we single out TDH Algorithm 1.1 for better presentation of the protocol for the reader. Note, that the users run step 5 differently based on their order in the group. This measure ensures that the P2P key is computed the same between two parties, i.e, <math>k_{i,j} = k_{j,i}</math>. '''Algorithm 1.1''' Triple Diffie-Hellman between <math>U_i</math> and <math>U_j</math> assuming i < j {| border="1" cellspacing="0" cellpadding="5" align="center"!align="center"|Round!align="center"|Step!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="center"| 1|align="center"|1|align="right"|Generate ephemeral DH private key|align="center"|<math> x_i \leftarrow [0, order(g)]</math>|align="center"|Computation|-|align="center"||align="center"|2 Chatroom Setup|align="right" | Generate ephemeral DH public key|align="center"|<math>y_i \leftarrow g^{x_i}</math>|align="center"|Computation|-|align="center"||align="center"|3|align="right" | Broadcast User identity and the DH key|align="center"|<math>(U_i, y_i)</math>|align="center"|Broadcast|-|align="center"|2|align="center"|4|align="right" |Receive other party id and ephemeral DH public key|align="center"|<math>(U_j|y_j)</math>|align="center"|Receive|-''(n+1)sec' '|align="center"||align="center"|5|align="right"|Generate Triple Diffie-Hellman P2P keys|align="center"|<math>k_{i,j} \leftarrow H({y_j}^{LSK_{U_i}},LPK_{U_j}^{x_i},y_j^{x_i})</math>|align="center"|Computation|-|align="center"||align="center"|6|align="right" |Send key confirmation to other party|align="center"|<math>kc_i \leftarrow H(k_{i,j}, U_j)</math>|align="center"|Broadcast|-|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|} ===''GroupEnc'' and ''GroupDec'' functions===For the high level design of the protocol we do not specify the primitives for ''GroupEnc'' and ''GroupDec'' used in steps '''8''' and '''14''' of Alogrithm 1 as a part of the protocol, as we do not specifies the Hash function and the block cipher. We explain their property here. We choose a candidate in section IX.4. The ''GroupEnc'' and ''GroupDec'' functions are primitives which are called collectively by all instances involved in the session and are supposed to satisfies the following goal: '''Definition''': Let <math>\mathcal{S} := \{U_1,...,U_n\}</math> and for each <math>i,j</math>, let <math>k_{i,j}</math> be a secret shared between and only between <math>U_i</math> and <math>U_j</math>. The goal of group <math>\mathcal{S}</math> is that: # Each member of group <math>U_i</math> to generate and share a secret <math>z'_i</math> among the member of group ''G'' using public channel <math>\mathcal{C}</math>.# <math>z'_i</math> remains unknown for any <math>\mathcal{A} \not \in G</math> eavesdropping the channel <math>\mathcal{C}</math>. To this end each member <math>U_i</math> compute <math>z_i := GroupEnc(k_{i,j} \, \textrm{for} \, j \neq i \, \textrm{and} \, j \in \{1,...,n\}, z'_i)</math> and broadcast <math>z_i</math> on <math>\mathcal{C}</math>. Later on when <math>U_i</math> receives all <math>z_j</math>. It recovers all secrets <math>z'_i</math> by computing <math>GroupDec(k_{i,j} \, \textrm{for} \, j \neq i \, \textrm{and} \, j \in \{1,...,n\}, z_i)</math>. ===(n+1)sec key exchange vs original Flexible Group Key Exchange of [ACMP10]===Although in higher level view of (n+1)sec we generalized the process of key exchange using ''GroupEnc''/''GroupDec'' abstraction, at lower level our choice of primitive for this functions make the group key computation processes of ''(n+1)sec'' and the original key exchange algorithm the same. Hence, the steps marked pink in Algorithm 1, only differ in from [ACMP10] but not in result. (n+1)run a deniable mutual authentication protocol along side with the key exchange protocol, this results in communicating extra key confirmation data along side of other data exchanged during the course of running the protocol. As we will show in the proof, these data has effect on the usual run of the algorithm. The only step that ''(n+1)sec'' runs differently compare to the original algorithm (beside generating extra data), is computation of mutual secret, between <math>U_i</math> and <math>U_j</math>. In original, algorithm it is simply <math>g^{x_i}{x_j}</math>. In ''(n+1)sec'', it is the triple DH secret <math>H({y_j}^{LSK_{U_i}},LPK_{U_j}^{x_i},y_j^{x_i})</math>. We will prove that this change does not compromise any of the protocol proprieties. The main difference between the two key exchange algorithms is in the key used for signature. In original algorithm, parties use their long term private key to sign their contribution, while in ''(n+1)sec'' they use their ephemeral keys. However, because the ephemeral keys has been authenticated before used for verification, we prove that the authenticity of signatures in both algorithms are equivalent under CDH assumption. ==VIII.2 Chatroom Setup==

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 [[''(n)sec''#VIII.3_Joining|VIII.3]], as they enter the chat. Algorithm [[''(n)sec''#Chatroom_setup|1]] describes the chat room setup protocol.

=== VIII.3 Join ===

Joining a chat involves two different procedures: the Join procedure, described in Algorithm [[''(n+1)sec''#Join|2]], which runs on the new participant’s instance, and an Accept New Participant Procedure, described in Algorithm [[''(n+1)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.

==== Authentication Step for new Joining party====

|align="center"|<math>k_{i,j} \leftarrow H({y_j}^{LSK_{U_i}},LPK{U_j}^{x_i},y_j^{x_i})</math>}}

|align="center"|<math>kc_i \leftarrow ((U_1,H(k_{i,1}, U_1)),\dots,(U_n,H(k_{i,n}, U_n)))</math>}}

=== Authentication Step for parties in the room===

|align="center"|<math>kc_{i,j}\leftarrow (U_i,H(k_{i,j}, U_i)) </math>

|align="center"|<math>z'_i := \leftarrow (H(k_{i,j}, sid_i) \, \textrm{for } \, j \neq i \, \textrm{and} \, j \in \{1,\dots,n\})</math>

|align="center"|<math>z_i \leftarrow GroupEnc(k_{i_ji,j} \, \textrm{for } \, j \neq i \, \textrm{and} \, j \in \{1,\dots,n\}, z')</math>

|align="right"| Receive other user(s)' key shares and confirmation of unauthenticated usersor Time out|align="center"|Wait to Receive (<math>\textrm{Receive} (U_j|z_j,\sigma_1,kc_{ji}) \textrm{ </math> for } <math> U_j \textrm{</math> unauthenticated}or Timeout by(2<math>\times</math>BROADCAST_LATENCY+INTERACTION_GRACE_INTERVAL, Drop inactive users, queue a new session request)

|align="right"|Check the validity of key confirmation of unauthenticated users|align="center"|<math>kc_ikc_j[jU_i] \stackrel{?}{=} H(k_{i,j,i}, U_jU_i) \textrm{ </math> for } unauthenticated <math> U_j \textrm{unauthenticated}</math>

|align="center"|<math>Verify_{y_i}(\sigma_j) \textrm{ </math> for } ''j \'' in \{1,\dots...,''n\''}</math>

|align="center"|<math>sk_{i,j} \leftarrow H(GroupDec(k_{i,jl}\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"|<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"|<math>H(sk_{i}, U_j) \stackrel{?}{=} sc_j \; \forall j \neq i</math>|align="center"|Receive|-|align="right"|Check signatures|align="center"|<math>Verify_{y_j}(\sigma_j) \; \forall j \neq i</math>

Consistency aspects of ''(n+1)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 ''(n+1)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, ''(n+1)sec'' displays a message highlighting the fact that although the user is not part of the session part of the conversation (from users' who confirmed the new user's identity) 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, ''(n+1)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 This is less secure model, in which 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.The detail of the process is depicted in Secthoin VIII.5

===VIII.4 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 [[''(n+1)sec''#Leave]].

|align="center"|<math>Send("Leaving!")</math>

|align="right"| Wait to receive hashes of TranscriptChainor Timeout|align="center"|<math>Wait to Receive()or Timeout by((2 <math>\times</math>BROADCAST_LATENCY)+INTERACTION_GRACE_INTERVAL)

Additionally, failure to receive a heartbeat from a user will result in executing Algorithm [[''(n+1)sec''#LeaveShrink]] excluding users who did not update their key.

|align="center"|Send(<math>Send(H(TranscriptChain^S_i[Parent(m_{farewell})]))</math>)

=== VIII.5 Secure Send and Receive ===

After the session key is established, participants will use Algorithms [[''(n+1)sec''#Send|5]] and [[''(n+1)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 needed in order 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.

====Send==== Encrypted messages include a "hash of TranscriptChain" of their parent as "additional authenticated data".  <math>(H(parent(m)), H(TransciptChain[parent(m)-1])))</math> Note that we defined <math>H(parent(m))</math> rather than <math>H(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.

|align="center"|<math> m \leftarrow (sidm, s,m) </math>|align="center"|Computation|-|align="right"| Increment own sequence number|align="center"|<math> own\_seq\_num \leftarrow own\_seq\_num+1 </math>

|align="center"|<math> m \leftarrow </math> (''m'', <math>H(H(parent(m)), H(TransciptChain^S_i[parent(m)-1]))</math>, <math>parent\_id(m)</math>, <math>own\_seq\_num</math>)|align="center"|Computation|-|align="right" |Generate a random nonce and append to the message|align="center"|<math> m \leftarrow (m, rand(128bit)) </math>

|align="right"| Sign the messageand append the signature|align="center"|<math>\sigma m \leftarrow (m, Sign_{x_i}(m))</math>

|align="center"|<math>(sid_i, e, \sigma)</math>

|align="center"|<math> VerifyVerify_{sender\_id}(m,\sigma) </math>|align="center"|Computation|-|align="right"| Compute message sequence number|align="center"|<math> seqnum(m) \leftarrow </math> ComputeSeqNum(''m'')

|align="right"| Update TranscriptChainVerify session id and transcript consistency and sender sequence number, issue a warning in case of failure|align="center"|<math> Insertsid_i \stackrel{?}{=} sid_{rec} \; </math> and <math> \; h \stackrel{?}{=} H(H(parent(m)), H(TranscriptChain^S, S_i[parent(m) -1])) </math> and <math> sender\_seq\_num \stackrel{?}{>} last\_own\_seq\_nums[sender\_id] </math>

|align="right"| decrypt messageUpdate TranscriptChain if possible|align="center"|<math> sid_{rec}, s, TranscriptChain^S_i[seqnum(m)] = (H(m), h, parent\_id \leftarrow Dec_kH(TranscriptChain^S_i[seqnum(m)-1])) </math>

|align="right"| Verify session id and transcript consistency, issue a warning in case of failureUpdate sender sequence number record|align="center"|<math> sid_i last\stackrel{?}{=} sid_{rec} _own\; _seq\textrm{and} \; h \stackrel{?}{=} (H(parent(m)), TranscriptChain^S_i_nums[parent(m)-1sender\_id]) \leftarrow sender\_seq\_num </math>

|align="right"| Update sender 's ephemeral key or share keysecret

|align="center"|<math>sk_{i,j} \leftarrow H(GroupDec(k_{i,j}, z_j \; \forall j),sid_i, U_j) \; \forall j \neq i</math>|align="center"|Computation|-|align="right"| Update ack timeout timer|align="center"|AxeAckTimeoutTimer<math>(parent(m),sender_i)</math>|align="center"|Computation|-|align="right"| Update rekey timeout timer|align="center"| ResetRekeyTimeOut(<math>sender_i</math>)|align="center"|Computation|-|align="right"| If the message has content set up ACK timer|align="center"|<math>meta\_only \stackrel{?}= True</math> then <math>SetACKTimer(m)</math>

|align="center"|If <math>meta\_only \stackrel{?}{=} False</math> then return ''m''|align="center"|Computation

== == Out of Session Send and Receive ====Due to nature of the key exchange algorithm, (n+1)sec support confidential P2P communication. This in particular enables the user to share the conversation with joining user(s) who confirmed their identity to the user but have not established a session yet. It is worth mentioning that every session keeps a ''list future sessions to transition to'' this is equivalent to the list of ''confirmed but yet to join users''. If the extension discussed in section VIII.3 is enabled it will make use of this list to implement the following changes:* When a user send a message ''Extended Send'' is invoked instead, it sends the message to the session using ''Send'' but also to the prospective participants, using ''P2P Send''.* When a message is received, ''Extended Receive'' is called which check if the user has the correct key to decrypt the message. If the message is encrypted by session key and user has the session key then it calls the normal receive. If the message is encrypted by a p2p key that the user share, it calls ''P2P Receive''. Otherwise, it simply ignores the message. '''Algorithm 9.1 Extended Send''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right" | If we are part of a session id in the room call ''Send''|align="center"| Send|align="center"| Broadcast|-|align="right"| For all confirmed users not in session call ''P2P Send''|align="center"| P2P Send|align="center"|Broadcast|} '''Algorithm 9.2 Extended Receive''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right" | If ''m'' has session id call ''Receive''|align="center"| if ''m'' has ''sid'' then Receive|align="center"| Computation|-|align="right"| If ''m'' has key id, call ''P2P Receive''|align="center"| P2P Send|align="center"|Computation|} '''Algorithm 9.3 P2P Send''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right" | Prepend key id and sender id|align="center"|<math> m \leftarrow (key\_id, U_i, m) </math>|align="center"|Computation|-|align="right" |Generate a random nonce and append to the message|align="center"|<math> m \leftarrow (m, rand(128bit)) </math>|align="center"|Computation|-|align="right"| Sign the message and append the signature|align="center"|<math> m \leftarrow (m, Sign_{x_i}(m))</math>|align="center"|Computation|-|align="right"|Encrypt|align="center"|<math>e \leftarrow Enc_{k_{key\_id}}(m)</math>|align="center"|Computation|-|align="right"| Broadcast the message|align="center"|<math>(key\_id, e)</math>|align="center"|Broadcast|} '''Algorithm 9.4 P2P Receive''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right"| Decrypt message|align="center"|<math> key_{id}, sender\_id, m, sigma \leftarrow Dec_{k_{key\_id}}(m) </math>|align="center"|Computation|-|align="right"| Check signature|align="center"|<math> Verify_{sender\_id}(m,\sigma) </math>|align="center"|Computation|-|align="right"| return m|align="center"|return ''m''|align="center"|Computation|} ==VIII.6 Reaching Consistency ==

|align="center"|<math> m \leftarrow seqnum(M), p \leftarrow parentnum(m)</math>

|align="center"|<math>H(TranscriptChain^S_j[p]) \stackrel{?}{== } H(TranscriptChain^S_i[p])</math> for all <math>U_k \in plist^S_i</math>

|align="right"| Compute TranscriptChain^S_i[m]

== VIII.7 In-session Forward Secrecy==To ensure forward secrecy in long living chat sessions, ''(n+1)sec'' provides a session key update throughout the session. Each message sent to the session by each participant contains meta data described in [[#VIII.5.1 (n+1)sec Message Structure]]. Prior to sending any message, ''(n+1)sec'' determines the content of meta data, and piggy backs to that message according to the following algorithm: '''Algorithm 10.1 Compute meta data''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right"| Initiate meta data with current state of knowledge of new ephemeral keys and secret shares|align="center"|<math> meta\_data \leftarrow ustate_i[j]</math> for all ''j'' in {1,...''n}|align="center"|Computation|-|align="right"| Include the new ephemeral key if participant <math>U_j</math> has not receive it|align="center"|If <math>ustate_i[j] \stackrel{?}{=} 0</math> ''meta_data'' \leftarrow <math>y_{i_{new}}</math>|align="center"|Computation|-|align="right"| If (all) participants have sent their ephemeral keys compute the shared secret|align="center"|If <math>ustate_{j}[i] \stackrel{?}{=} 1</math> for all ''j''in {1,...''n}, then <math> meta\_data \leftarrow (meta\_data, GroupEnc(k_{i_j} \, \textrm{for} \, j \neq i \, \textrm{and} \, j \in \{1,\dots,n\}, z'))</math>|align="center"|Computation|-|align="right"| Return meta data|align="center"|return ''meta_data''|align="center"|Computation|} ==VIII.8 Heartbeat and Timeout ==

* REKEY_GRACE_INTERVAL, to ensure in session forward secrecy, the protocolrequires that each <math>U_i</math> updates their DH ephemeral key as well as group key. After a session is established or it was rekeyed, each<math>\Pi^S_i</math> needs to send its new DH ephemeral key no later thanREKEY_GRACE_INTERVAL. Therefore if <math>\Pi^S_i</math> has not sent any message by thatperiod of time, it issues an empty message. Similarly after receivingall ephemeral keys from all participants, <math>\Pi^S_i</math> needs to send itssecret for computation of new key no later than REKEY_GRACE_INTERVAL. * INTERACTION_GRACE_INTERVAL, to ensure establishment of a session in timely manner, when immediate contribution of participants is required (for example sending key confirmation, contribution to the session secret), this values indicate that how long an active participants should wait till it decide to drop the non-contributing inactive participants from the participant list.

When a new session key is computed as well as when <math>\Pi^S_i</math> receives new ephemeral DH values from all users, a timer of (2*BROADCAST_LATENCY)+REKEY_GRACE_INTERVAL) period is set. It is cancelled when all user contributions are received (ephemeral keys or session key secrets). Otherwise, the <math>\Pi^S_i</math> excludes users who failed to contribute from the <math>plist</math> and request a call for leave procedure to exclude those users from the plist and call '''initiate new session'''. This measure is taken to ensure that users do not block in-session forward secrecy due to loss of connection or being under attack. === Timing out during an interactive session === ''(n+1)sec'' by design assumes the participants are trusted in being commited to the goal fo creating a secure chatroom. In this sense, ''(n+1)sec'' provide little defens against party which trying to sabotage a room by mounting various denial of service approaches. However, there are situation where a party is genuinely affected (by external adversary) or by connection problem. Under such assumption, situations we expect that all other parties, reach a consensus, that a participant has connectivity problem and agree on leave them out of the room. Timeout sub protocol is designed to deal with such a situation. When a new session is requested (for join, leave, etc) each participant wait for (2*BROADCAST_LATENCY)+INTERACTION_GRACE_INTERVAL, they omit non-participating participants from the plist, and wait for PLIST_UPDATE_GRACE_INTERVAL. so other participants also reach to the same conclusion and updates their plists, then they initiate a new session. === Drop inactive users, queue a new session request ==='''Algorithm 10.XX''' {| border="1" cellspacing="0" cellpadding="5" align="center"!align="right"|Description!align="center"|Pseudo-code!align="center"|Type|-|align="right"| Drop inactive users|align="center"|<math> plist_i \leftarrow plist_i \backslash inactive\_participant\_list</math>|align="center"|Computation|-|align="right"| Recompute Session Id|align="center"|<math>sid_i \leftarrow H(U_1|y_1|\dots|U_{n_{active}}|y_{n_{active}})</math>|align="center"|Computation|-|align="right"| Set up timer to request a new session|align="center"|SetTimer(PLIST_UPDATE_GRACE_INTERVAL, initiate new session)|align="center"|Computation|} 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 valueShorts (DTSHort): 2 byte unsigned value, big-endianLength (DTLength): 4 byte unsigned value, big-endianHashBlock (DTHash): 32 byte dataOpaque 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_info where the following fields from participant_info submessage:  participant id, ephemeral publick key (DTHash) are representing the joiner's information. the  authenticated (DTByte) is kept only for compatibility with participant_info sub message structure and has no information value. It should be 1 as it represents the state of authentication of the joiner to itself. However, its value will be ignored by the current participants. ===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 32 byte 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 Session Management and Message Handling==(n+1)sec secure conversations are modeled as chat sessions with proven cryptographic properties. A chat session starts with participants run the key agreement protocol and then agree and confirm a shared key. However, the process on how a joining and leaving participants trigger a new chat sessions and how participants need to respond to multiple simultanous joins and leaves requests and the process of establishing multiple chat sessions is managed by (n+1)sec Session Management protocol. This protocol is work in progress to deal with unresponsive participants and those who denial their response to bar the establishment of a session. This section explains the rules - based on which - (n+1)sec currently 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 "confirmed 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. '''FSM message handling''': The basic rule is that 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, for users of joiner or confirmed participant status: ===Joiner=== In current (n+1)sec implementation, this state is implemented as:  user_in_room_state == JOINING * Messages without session id (including JOIN_REQUEST): The Joiner, user in "JOINIG" state will ignores all messages without session id. * If the message has a session id which the joiner has not constructed a session - the joiner will react as follows based on the typ of the message: ** '''Participant Info''': *** If the joiner is mentioned in the participant list, the joiner construct a session with that list. The session will be at the state of JOIN_REQUESTED.*** If the joiner is not mentioned in the plist, the joiner ignores the message (Suggestion: Should the joiner begins a session by appending itself to the list?). ** '''Session Confirmation''': The joiner will mark all its sessions as DEAD and wait for the new participant list (*** should joiner send a new join request?). If the message has session id corresponding to a session that the joiner already constructed (and is in process of joining, i.e. is not DEAD), then the session FSM will deal with the message, as stated above. ===Confirmed Participant=== This state is indicated as follows in the current implementation of (n+1)sec:  user_in_room_state == CURRENT_USER The confirmed participant is a member of a unique session in state of IN_SESSION. This session is indicated as '''active_session'''. All messages participants sends to the room is going to such session. The participant also keeps an indicator named as '''next_in_activation_line'''. Both indicators are pointing to the active_session at the point when the active_session moves to IN_SESSION state. * If the received message has a session id and the participant has constructed a session corresponding to that message. Then the FSM treats the message. * If the received message has a session id, but the confirmed participant does not have a session is not part of the session then the participant will ignore the message, unless the message is of PARTICIPANT_INFO. * If the received message is of PARTICIPANT_INFO for which, the user doesn't have corresponding session then the FSM of next_in_activation_line session will treat the session. For the definition of next_in_activation_line. * If the received message does not have a session id, then it is a JOIN_REQUEST (otherwise marked as invalid). The FSM of next_in_activation_line will treat the session. ===Session transition=== Each confirmed participant (user_in_room_state == CURRENT_USER) keeps to indicators: * '''active_session''' The active_session is the only session which is in IN_SESSION state. A session state moves to IN_SESSION when the user receives session confirmation from all participants. In that case the previously active session state will be DEAD. When a new session get activated, all STALE sessions gets refreshed. That is, all sessions which were requested to be created (due to join or leave) during the creation of the newly active session, will be recreated according to the new participant list. Further more, the next_in_activation_line also points to the newly activated session. * '''next_in_activation_line''' next_in_activation_line is the session which receives requests for new session (join/leave). When new session is activated it also become next_in_activation_line. When a new priority session is constructed it takes the next_in_activation_line pointer. If there is no priority session, then the first session which gets it share key generated becomes the next in activtion. 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. In this case, the session with leaving participant removed becomes the '''next_in_activation_line''' and all live sessions (not DEAD) (beside the active_session) will be marked as stale.  When multiple users are joining, when the confirmed participant receives the first joiner auth, it will halt the protocol for other joining users. That's the session will become the next_in_activation_line, and all live sessions (beside the active_session will bemarked as stale. When the next_in_activation_line session is confirmed and moves to IN_SESSION, the active_session moves to DEAD state. For each stale session, a new participant info list will be generated of the union of the participant in new active session and the participant in the stale session bar the users which left during in process of active_session establishment. The participants info message will be sent to the remaining joining users. Joining user (user_in_room_state == JOINING) does not keep any indicator. ===Finite State Table=== The sesseion finte state machine react based on the following table. A joiner will start a new session with JOIN_REQUESTED after it sends its join request. {| class="wikitable"|-! State/Message !! JOIN_REQUEST !! PARTICIPANTS_INFO !! JOINER_AUTH !! GROUP_SHARE !! SESSION_CONFIRMATION !! IN_SESSION_MESSAGE |-| JOIN_REQUESTED || || authenticate and send share || || || || |-| RE_SHARED || init a stale session with new user || authenticate and store share || authenticate and store share || authenticate and store share || || |-| GROUP_KEY_GENERATED || init a stale session with new user || || || || mark confirmed and may move session || |-| IN_SESSION || init a session with new user || || || || || receive |-| STALE || || || || || || |-| DEAD || || || || || || receive |} If a message is received when there is no handler it will be ignored. ====Explaniantion of the handlers==== * '''authenticate and send share''' called by the joiner, computes authentication token with each of the participants and the user share of the session key and send a JOINER_AUTH Message. Beside generating share it acts like '''authenticate and store share'''. * '''authenticate and store share''' validate the authentication token and store the sent share. If everybody is authenticated and all shares are received, compute the session key and the session confirmation and send of SESSION_CONFIRMATION message. In that case, the session state will be changed to GROUP_KEY GENERATED. Otherwise stays unchanged. If the received PARTICIPANTS_INFO message does not corresponds to the session, it create a new session for that list in stale state. In that case, the state of the receiving session stays unchanged. * '''confirm and may move session'''it validate the session confirmation. If all the participant is confirmed the state will change to IN_SESSION. joiner become confirmed participant. Otherwise it does not change the state of the session. * '''init a session with new user'''When a confirmed participant receive this message start a new session with the joiner added to it. The state of new session will be RE_SHARED. it does not change the state of the session. * '''init a stale session with new user'''It creates a new session with the joiner added to it. The state of new session will be STALE. it does not change the state of the session.

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 ''(n+1)sec'' and is widely implemented.

ED25519 has been chosen as the signature primitive due to its efficiency and more secure implementability over other elliptic-curve digital signature algorithms.[Be11]

We are using AES-256 in counter mode Galois/Counter Mode (GCM) with a shared group key for message encryption, as suggested we are following the suggestion by the original OTR protocolof using counter mode. However, unlike OTR, <math>(n+1)sec</math> does not support per message forgeability (although the whole transcript is forgeable), it is not prohibitive to use the same key for encryption and authentication.

==IX.4 GroupEnc and GroupDec Functions ==The ''GroupEnc'' added authentication, spares P@P send and ''GroupDec'' functions are primitives which are supposed to satisfies the following goal:receive routines from using digital signature.

'''Definition''': Let <math>\mathcal{S} := \{U_1With GCM mode,...,U_n\}</math> the authenticated encryption is generically secure by the result (and for each <math>i,j</math>, let <math>k_{i,j}</math> be a secret shared between and only between <math>U_i</math> and <math>U_j</math>assumptions) of [Kr00]. The goal of group <math>\mathcal{S}</math> is that:

# Each member of group <math>U_i</math> to generate ==IX.4 GroupEnc and share a secret <math>zGroupDec Functions ==The '_i</math> among the member of group 'GroupEnc'G'and ' using public channel <math>\mathcal{C}</math>.# <math>z'_i</math> remains unknown for any <math>\mathcal{A} \not \GroupDec'' functions defined in G</math> eavesdropping the channel <math>\mathcal{C}</math>Section VIII.  To this end each member <math>U_i</math> compute <math>z_i := GroupEnc(k_{i,j} for j \in \{1,...,n\}, z'_ifacilitate the collective generation of a secret(s)</math> and broadcast <math>z_i</math> on <math>\mathcal{C}</math>. Later on when <math>U_i</math> receives all <math>z_j</math>. It recovers all secrets <math>z'_i</math> shared by computing <math>GroupDec(k_{i,j} for j \in \{1,the group...,n\}, z'_i)</math>. Here we mention two examples of such functions, and specify the functions for ''(n+1)sec' protocol:

''(n+1)sec'' uses the modification of the primitive suggested in [ACMP10] to guard the confidentiality of the p2p and the subgroup keys:

= X. Conclusion Next Steps =<span style="font-size:200%">T</span>his document is the first public draft of the ''(n+1)sec'' protocol. We are genuinely hoping to receive a lot of feedback and review on this work and have chosen the wiki format to support [[Talk:Nsec|Discussion]]. Ongoing tasks for the team include mathematical proofs of resistance to the adversarial model presented herein as well as technical implementation details. This is currently scheduled for the end of December, 2014. The [https://github.com/equalitie/np1sec np1sec] software library will be initially implemented in [https://github.com/cryptocat/cryptocat/ Cryptocat] and (with your help) further developed to suit a variety of use-cases in the near future.

<span style="font-size:200%">I</span>n this document, we presented the final draft of ''(n)sec''XI. We hope by receiving public comment on this draft we are able Acknowledgements =The eQualit.ie team would like to give special thanks and note to improve the designeffort and dedication offered by Trevor Perrin and Ximin Luo to this project. We They have referenced been actively involved throughout the adversarial models which year and the protocol is supposed result would not have been the same without their contribution. The team would also like to resistexpress thanks to Joseph Bonneau for his constructive comment and critisim to improve the protocol and its presentation. Meanwhile we are working George Kadianakis for helping with the security proof and pointing out flaws and attack; Arlo Breault for his work on an implementation of ''(n)sec''. We will publish a sequel document which high light the implementation details protocol in the [https://github.com/equalitie/np1sec np1sec] software library; David Goulet for valuable advice as well as proof of resistance continued assistance and support offered to the adversarial project; Prof. Payman Mohassel for his help and advice on the security model presented hereand the proof; Prof. Jermey Clark, Prof. Matthew Green and Frederic Jacobs for their constructive participation in the design debates; Prof. Mark Manulis for suggesting the GKA. eQualit.ie expresses gratitude to Nadim Kobeissi, Cryptocat founder and developer who initiated the project and for sharing his experience and giving advice on secure browser based chat. Last but not least we would like to thank the Open Technology Fund for supporting the project.

= XIXII. References =

[*ACMP10] Michel Abdalla, Céline Chevalier, Mark Manulis, and David Pointcheval. “Flexible Group Key Exchange with on-Demand Computation of Subgroup Keys.” In ''Third African International Conference on Cryptology (AfricaCrypt ’10)'', edited by Dan Bernstein and Tanja Lange, 6055:351–368. LNCS. Stellenbosch, South Africa, 2010: Springer. doi:[http://dx.doi.org/10.1007/978-3-642-12678-9_21 10.1007/978-3-642-12678-9_21].

[*BS07Be11]BohliBernstein, Jens-Matthias, and Rainer Steinwandt. 2007. “Deniable Group Key AgreementDaniel J.” In ''VIETCRYPT''; Duif, edited by Phong Q. NguyenNiels; Lange, 4341:298–311Tanja; Schwabe, Peter; Yang, Bo-Yin. Lecture Notes in Computer Science. Springer"High-Speed High-Security Signatures. ","CHES","978-3-642-23950-2","http://dblp.uni-trier.de/db/conf/vietcryptches/vietcrypt2006ches2011.html#BohliS06BernsteinDLSY11". 2011. pages: 124-142","6917","Lecture Notes in Computer Science","Springer".

[*BVS05BS07]Bohli, Jens-Matthias, Maria Isabel Gonzalez Vasco, and Rainer Steinwandt. 20052007. “Secure “Deniable Group Key Establishment RevisitedAgreement.” In ''IACR Cryptology ePrint ArchiveVIETCRYPT'' 2005, edited by Phong Q. Nguyen, 4341: 395298–311. Lecture Notes in Computer Science. Springer. http://dblp.uni-trier.de/db/journalsconf/iacrvietcrypt/iacr2005vietcrypt2006.html#BohliVS05aBohliS06.

[*BMBVS05]BonneauBohli, JosephJens-Matthias, Maria Isabel Gonzalez Vasco, and Andrew MorrisonRainer Steinwandt. “Finite-State Security Analysis of OTR Version 22005. “Secure Group Key Establishment Revisited.” ''IACR Cryptology ePrint Archive'' 2005: 395. http://wwwdblp.jbonneauuni-trier.comde/docdb/BM06-OTR_v2_analysisjournals/iacr/iacr2005.html#BohliVS05a.pdf

[*BGB04BM] BorisovBonneau, Nikita, Ian GoldbergJoseph, and Eric BrewerAndrew Morrison. 2004. “Off“Finite-the-Record Communication, or, Why Not to Use PGPState Security Analysis of OTR Version 2.” In ''Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society'', 77–84. WPES ’04. New York, NY, USA: ACM. doi:[http://dxwww.doijbonneau.orgcom/10.1145doc/1029179.1029200 10.1145/1029179.1029200]. http://doi.acm.org/10.1145/1029179.1029200BM06-OTR_v2_analysis.pdf

[*BCGNP08BGB04] Colin BoydBorisov, Yvonne CliffNikita, Juan Gonzalez NietoIan Goldberg, and <span>KennethGEric Brewer.</span> Paterson2004. 2008. “Efficient One“Off-Round Key Exchange in the Standard Model-Record Communication, or, Why Not to Use PGP.” In ''Information Security and Proceedings of the 2004 ACM Workshop on Privacyin the Electronic Society'', edited by Yi Mu77–84. WPES ’04. New York, Willy SusiloNY, and Jennifer Seberry, 5107:69–83. Lecture Notes in Computer Science. Springer Berlin Heidelberg. http://dx.doi.org/10.1007/978-3-540-70500-0_6.USA

[*BCP01BCGNP08] Emmanuel BressonColin Boyd, Yvonne Cliff, Olivier ChevassutJuan Gonzalez Nieto, and David Pointcheval<span>KennethG. 2001</span> Paterson. “Provably Authenticated Group Diffie2008. “Efficient One-Hellman Round Key Exchange - in the Dynamic CaseStandard Model.” In ''Advances in Cryptology - Proceedings of ASIACRYPT ’01Information Security and Privacy'', edited by Colin BoydYi Mu, 2248Willy Susilo, and Jennifer Seberry, 5107:290–30969–83. LNCSLecture Notes in Computer Science. Gold Coast, Australia: Springer. doi:[http://dx.doi.org/10.1007/3-540-45682-1_18 10.1007/3-540-45682-1_18]Berlin Heidelberg.

[*BoMa10] Boyd, Colin; Mathuria, Anish. "Protocols for Authentication and Key Establishment","3642077161, 9783642077166",2010, Springer Publishing Company, Incorporated, 1st edition [*BCP01] Emmanuel Bresson, Olivier Chevassut, and David Pointcheval. 2001. “Provably Authenticated Group Diffie-Hellman Key Exchange - the Dynamic Case.” In ''Advances in Cryptology - Proceedings of ASIACRYPT ’01'', edited by Colin Boyd, 2248:290–309. LNCS. Gold Coast, Australia: Springer.  [*BCPQ01] Emmanuel Bresson, Olivier Chevassut, David Pointcheval, and Jean-Jacques Quisquater. 2001. “Provably Authenticated Group Diffie-Hellman Key Exchange.” In ''Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS ’01)'', edited by Mike Reiter, 255–264. Philadelphia, Pennsylvania: ACM Press. doi: [*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://dx.doiarxiv.org/10.1145abs/501983.502018 10.1145/501983.502018]1008.1221

[*Da02] Davis, Don,"Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.","USENIX Annual Technical Conference, General Track","1-880446-09-X","http://dblp.uni-trier.de/db/conf/usenix/usenix2001g.html#Davis01","2002-09-022001", page 65-78 [*GUVGC09] Ian Goldberg, Berkant Ustao<span>\</span>uglu, Matthew D. Van Gundy, and Hao Chen. 2009. “Multi-Party Off-the-Record Messaging.” In ''Proceedings of the 16th ACM Conference on Computer and Communications Security'', 358–368. CCS ’09. New York, NY, USA: ACM. doi:[http://dx.doi.org/10.1145/1653662.1653705 10.1145/1653662.1653705]. http://doi.acm.org/10.1145/1653662.1653705.

[*GBNM11] M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto, and Mark Manulis. 2011. “Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols.” ''ACM Trans. Inf. Syst. Secur.'' 14 (4): 28.http://dl.acm.org/citation.cfm?id=2043628.2043629

[*KLL04Kr00] Hyun-Jeong Kim, Su-Mi Lee"Krawczyk, Hugo","The order of encryption and Dong Hoon Lee. 2004. “Constant-Round Authenticated Group Key Exchange authentication for Dynamic Groups.” In ''ASIACRYPT''protecting communications (Or: how secure is SSL?), 245–259. https2001, Published:Cryptology ePrint Archive, Report 2001/045 http:/www/eprint.iacr.org/archive/asiacrypt2004/33290243/33290243.pdf

[*Man06KPW13] Mark ManulisHugo Krawczyk and Kenneth G. 2006Paterson, Hoeteck Wee. “Security-Focused Survey on Group Key Exchange Protocols2013.” “On the Security of the TLS Protocol: A Systematic Analysis” in''IACR Cryptology ePrint Archive'' 2006: 395. http://eprint.iacr.org/2006/395.

[*PerLVH13] Trevor PerrinLiu, Hong; Vasserman, Eugene Y. “Axolotl Ratchet; Hopper, Nicholas. "Improved Group Off-the-record Messaging" from the ''Proceedings of the 12th ACM Workshop on Workshop on Privacy in the Electronic Society'', 978-1-4503-2485-4, 'ACM', New York, NY, USA. 2013 [*Mo13] Marlinspike, Moxie,"Simplifying OTR deniability" blogpost, Open Whispersystems, https://whispersystems.org/blog/simplifying-otr-deniability/ [*Sys14] Marlinspike, Moxie et al. Whisper Systems. 2014. “TextSecure ProtocolV2.” Accessed March 2. https://github.com/trevpWhisperSystems/axolotlTextSecure/wiki /ProtocolV2.

[*Sys14KiSo00] Whisper SystemsSong, Boyeon; Kim, Kwangjo, "Two-Pass Authenticated Key Agreement Protocol with Key Confirmation","Progress in Cryptology —INDOCRYPT 2000","978-3-540-41452-0","http://dx. 2014doi. “TextSecure ProtocolV2org/10.” Accessed March 21007/3-540-44495-5_21","2000"; "237-249",1977 "Lecture Notes in Computer Science",Springer Berlin Heidelber.  [*Git11] https://github.com/WhisperSystemshellais/TextSecure/wiki/ProtocolV2.cryptocat

=Appendices= ==Appendix A: Asynchronous communication and Forward Secrecy== The protocol is primarily targeted to synchronous cases, however, with some modification it can be used for asynchronous cases. Provided that the participants are not concerned with authenticating the list of participants (it is OK if Eve impersonates Bob as long as she is unable to read Bob’s messages). Participants can communicate using their pairwise exchanged ephemeral Diffie-Hellman keys until all participants finish the second round of authentication. As soon as a deniable handshake has been established among a set of participants any subset of them can communicate and authenticate their messages using the “session key” and their ephemeral signature key. The protocol does not enforce explicitly a time limit on renewing the session key shares and can be used for an asynchronous high latency transport after the key establishment state. The downside of using a session key for a long time is that a compromised session key will reveal all past communication during that session. This does not pose an imminent threat when the life span of a chat is short. However, in the context of asynchronous high latency transport, it is a more serious concern. The protocol requires the participants to pre-emptively update their ephemeral signature/shares and propagate them as part of the messages they are already sending. Subsequently, they also update their key share with their neighbours as soon as the neighbours also propagate their new ephemeral signature keys. 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. ==Appendix B: Other design possibilities==During the process of designing ''(n+1)sec'' we have considered and debated other design possibilities which we will describe in this section along side our arguments in favour of the choices made. ===Group Key Scheme vs Broadcast Scheme===We say a group key scheme (as defined in [[#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. See GOTR by [LVH13] For an example of such scheme where each participant chooses there own circle of audiances. <!--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 ''(n+1)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 ''(n+1)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 [[#Sending_and_receiving_messages_ while_joining_is_in_progress|Section VIII.2 Sending and receiving messages while joining is in progress]] allows for communication with users while they are waiting for the join procedure to complete. ===Participatory vs individually independent computation of group key(s)===Most AKGE offer some degree of contributiveness in computing the group secret. This roughly means that (at least in the absence of an insider) the group secret is derived using contribution from all members of the group. There has been criticism of the importance of this property such as in [Da14]. In this section we consider briefly the arguments for each side and describe the rational for our choice. [[Category: nsecnp1sec]]