Revision as of 20:09, 22 June 2016

1 Abstract
2 I. INTRODUCTION
3 II. History and literature review
4 III. Design rationale
5 IV. Security Properties
6 V. Chat Session Model
7 VI. Threat Models and Adversarial Goals
8 VII. Protocol High Level Design
9 VIII. (n+1)sec Protocol: Step by Step
10 IX Cryptographic Primitives
11 X. Next Steps
12 XI. Acknowledgements
13 XII. References
14 Appendices
- 14.1 Appendix A: Asynchronous communication and Forward Secrecy
- 14.2 Appendix B: Other design possibilities
  - 14.2.1 Group Key Scheme vs Broadcast Scheme
  - 14.2.2 Participatory vs individually independent computation of group key(s)

Abstract

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 Open Technology Fund and Cryptocat. We include the design rationale, choice of security features, adversarial models, schematic and high level specification of sub-protocols. A subsequent document will present security proofs and implementation details.

I. INTRODUCTION

The (n+1)sec project was inspired by 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 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 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 Discussion page to ask questions and leave comments.

In the following section we summarise relevant publications and describe their influence on this protocol. In Section III, we describe our approach and choice of security features. In Section IV, we review the security properties within this protocol. In Section V we give basic mathematical definition needed to model the chat session and security proofs for various security aspects of the protocol. Section VI provides formal definitions and references to the adversarial models for each property. In Section VII we describe various parts of the protocol and present choices for each sub protocol. In 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 Section IX. Finally, we define the work that remains to be done on this protocol and acknowledge the good people who have helped us get here.

II. History and literature review

Two-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. 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, it has defined the standard for secure Internet chat attracting a lot of academic attention and security analysis. The OTR protocol is now at Version 3 and the 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].

In ^[RGK05], researchers point out that OTR’s approach to authenticate renewed ephemeral session keys is provided by the property of confidentiality and is therefore dependent on the secrecy of the conversation. Hence, breaking the secrecy of the conversation (e.g. by leaking the session key) will lead to false authentication as well. They offer two authenticated deniable key exchange protocols, which also provide forward secrecy, as a replacement for OTR’s original key exchange. Furthermore, they argue that forgeability and malleability do not have any mathematical consequence in improving deniability if the parties have been authenticated by a deniable key exchange scheme. They argue that as these properties pose potential security threats, it is desirable to omit them from the protocol entirely.

An alternative appears in ^[BS07], using the Schnorr zero-knowledge proof and signature algorithm, to introduce a 4-round challenge-based authentication scheme that grants deniability to the two-round authenticated protocol described in ^[BVS05].

^[ACMP10] offers a more efficient protocol than ^[BS07] in the sense that ephemeral Diffie-Hellman elements are reusable to regenerate keys when some of the participants change. As such, it offers a one-round protocol to generate a key for a subgroup of the original conversation.

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

III. Design rationale

Our approach for (n+1)sec design was based on the following requirements, in order of importance:

A protocol that is provably secure in a sufficiently strong adversarial model that addresses confidentiality, authenticity and forward secrecy
Applicable to the Cryptocat XMPP use-case
Providing some degree of deniability when it does not negatively impact usability or our security goals
Addressing security flaws in ^[BGB04] and ^[GUVGC09]

We designate the protocol suggested in ^[GUVGC09] as our starting point and apply various modifications to reach a desirable protocol satisfying the above stated goals.

A significant portion of our research suggested a better performing, more secure alternative to the key exchange protocol suggested in ^[GUVGC09]. Based on conclusions in ^[BM] and ^[RGK05], we are making the following design changes:

Using a more secure deniable key exchange algorithm, instead of naive Diffie-Hellman

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

Using a more practical algorithm, rather than the peer-to-peer signature key exchange

We have chosen the two round SKEME-based Triple Diffie-Hellman deniable key authentication instead of the Schnorr signature scheme suggested in ^[BS07] because it saves us two critical rounds for authentication (even though it offers a slightly weaker form of deniability). We have also modified the protocol to represent the chat condition where participants sequentially join and leave the chat.

Omitting forgeability and malleability from the protocol and refraining from broadcasting the expired ephemeral authentication keys.

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

IV. Security Properties

Following from the design rationales proposed in SectionIII, we give an informal description of the properties which (n+1)sec aims to secure in a multi-party chat session:

Participant deniable authenticity based on their long term persistent identity: While a participant in a chat can be sure of another participant’s authenticity, they cannot prove their confidence to anybody else who has not actively participated in the chat session or who has not interacted with the authenticator prior to the session.
Message origin authenticity against both outsider intrusion and the impersonation of existing participants by other malicious participants in the session. This means that the user can be assured of the authenticity of the sender of each original message even if other participants in the room try to impersonate the sender and send messages on their behalf.
Confidentiality of the conversation so its content is not accessible or readable by an outsider.
Forward secrecy of the conversation, so its content remains inaccessible in the event that the long term private key of a participant (which represents their long term identity) is compromised after session key establishment. In addition in-session forward secrecy means that compromise of the ephemeral keys of a participant, or the session key during chat session which is live for long time, would reveal only a fraction of the transcript.
Room consistency, where all participants are confident that they have been participating in the same room; they are confident that everybody in the room believes that everybody else sees the same participant list as they do.
Transcript consistency, where all participants are confident that they have been participating in the same conversation; as the conversation continues, they are confident that they have been seeing 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 requirements stated in Section III. The next section will introduce formal definitions covering these elements.

V. Chat Session Model

In modelling the chat session, in terms of the adversarial models and protocol specifications, the notation of ^[ACMP10] is followed. This notation is common to other publication on group key exchange such as ^[GBNM11], and is adherred to for consistency.

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

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

Definition V.3 An authenticated group key exchange (AGKE) is Algorithm $\Pi$ 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 $\Pi _{i}^{S}$ (or $\Pi _{i}$ when the underlying session is understood) we are referring to an instance of $\Pi$ which the party $U_{i}$ executes to achieve the collective goal. Further more we define:

Session id as seen by $U_{i}$ : Session id $sid$ will be derived during the execution of the protocol. The session id is computed by $\Pi _{i}^{S}$ (the instance of the protocol run by $U_{i}$ for session S) and is indicated by $sid_{i}^{S}$ , or $sid_{i}$ when there is no concern of confusion
Participant list: $plist_{i}^{S}$ is the list of participants which $U_{i}$ believes are participating in the chat session S. When there is no ambiguity in the underlying session, we simply use $plist_{i}$ notation.
'key id is the serial number given to the P2P keys generated during the process of key exchange, is computed as $Hash(U_{i}|y_{i}|U_{j}|y_{j})$ .
Ephemeral key list: $klist_{i}^{S}$ is the list of ephemeral public key $y_{j}=g^{{x_{j}}}$ 's of all participants which $U_{i}$ believes they are using in the chat session S. When there is no ambiguity in the underlying session, we simply use $klist_{i}$ notation instead. We use the notaion of $plist_{i}|klist_{i}$ to represent ordered concatenation of $U_{i}|y_{i}$ pairs as in $U_{1}|y_{1}|\dots |U_{n}|y_{n}$ . The order is assumed to be computable by all participants (lexicographically ordered using long term public key of participants, for example).
Session key of $\Pi _{j}^{S}$ as seen by $U_{i}$ : $sk_{i}^{S}$ (or $sk_{i}$ ) is the session key of session S as computed by $\Pi _{i}$ . It represents the cryptographic secret computed by AGKE, it can be a set of secrets. The essential defining factor is that it should become common knowledge for the session participants at the end of AGKE execution. Similarly we define $subk_{i}$ to represent the subsession key
Accepted state: A party enters the accepted state if it has computed $sk_{i}^{S}$ and has detected no errors in the protocol.
Partnered instances: Two instances $\Pi _{i}^{S}$ and $\Pi _{j}^{S}$ are considered partnered if and only if both instances have accepted $sid_{i}=sid_{j}$ and $plist_{i}=plist_{j}$ .

A correct AKGE algorithm is an AKGE which, when all $\Pi _{i}^{S}$ instances of AKE algorithm are initiated with access to a network which correctly forwards all messages without modification, all participants ultimately are partnered and all compute equal $sk_{i}^{S}$ ’s.

When underlying session are not considered we may omit the super script $\_^{S}$ from all above notations.

VI. Threat Models and Adversarial Goals

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

Accordingly to the requirements discussed in Section IV, it is necessary to examine the algorithm in terms of following threat cases:

Deniable Authenticated key exchange (including a forward secrecy adversary)
Message origin authenticity
Confidentiality
Transcript consistency

The following sections will define adversarial scenarios which represent the above threats.

Deniable Authenticated Key Exchange Adversary

Following the approach in [BoSt06] the model is divided into two adversaries: Authenticated Group Key Exchange and the Deniability Adversary.

As deniability is not our primary focus, we wil consider a weaker deniability adversarial model, which limits possible input similarly to the limitations considered by [GKR06]. This provision would disallow an input from the 'judge' and therefore saves an extra round of communication within the protocol.

Because he 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 round computation of a subgroup key". Meaning that when a participant leaves the session remaining participants can re-establish a (sub)session with only one round of communication. In this circumstance, the model must also consider an adversary's attack against the subgroup key.

We do not attempt to model resistance against internal key compromise impersonation (KCI) as defined ^[GBNM11].

Authenticated Key Exchange Adversary

Adversarial power

The following set of functions model the AKE adversarial threats. The adversary for the authenticated key exchange can mount an attack through a sequence of call to the functions, outlined below. The limitation on the order and condition of calling these functions is defined per adversary. We will re-use these definitions to demonstrate similar routes for other adversaries considered by the threat models in later sections.

Execute( $plist$ ): asks all parties in the $plist$ to run (a new) AGKE protocol and ${\mathcal {A}}$ will receive the execution transcript, i.e. ${\mathcal {A}}$ can eavesdrop.
Send( $\Pi _{i}^{S},m$ )/( $U_{i},m$ ) sends a message m to the instance $\Pi _{i}^{S}$ . We assume that m contains information to identify the sender $U_{j}$ . ${\mathcal {A}}$ will receive the execution transcript. Specifically, by sending $plist$ messages it forces $U_{i}$ to initiate $\Pi _{i}^{S}$ .
SKE( $\Pi _{i}^{S},spid_{i}$ ): asks $\Pi _{i}^{S}$ to compute the subgroup key for the $spid_{i}$ subsession. In response, $\Pi _{i}^{S}$ will either send a message or compute the subgroup key $k_{{spid_{i}}}$ depending on the state of $\Pi _{i}^{S}$ . This can be invoked only once per input.
RevealGK( $\Pi _{i}^{S}$ ): $\Pi _{i}^{S}$ gives $sk_{i}$ to ${\mathcal {A}}_{a}$ if it has accepted (as defined in Definition III.3).
RevealSK( $\Pi _{i}^{S},T$ ): $\Pi _{i}^{S}$ gives the $subk_{i}^{T}$ to ${\mathcal {A}}_{a}$ if it has been computed for subsession T.
Corrupt( $U_{i}$ ): $U_{i}$ gives its long term secret key to ${\mathcal {A}}_{a}$ (but not the session key).

Adversary's challenges

The following set of functions model the adversary's challenges. These reveal either a random value or a key. The adversary's advantage in distinguishing the cases should be translatable into an attack against the GDH primitive for the protocol to be considered secure.

TestGK( $\Pi _{i}^{S}$ ): To the ultimate goal of challenging the confidentially of $sk_{i}$ , ${\mathcal {A}}$ can run TestGK( $\Pi _{i}^{S}$ ) against U. As a the result a random bit b is chosen, if $b=1$ then ${\mathcal {A}}_{a}$ is given $sk_{i}$ the session key, otherwise a random value from the same probability distribution is given to ${\mathcal {A}}$ . Obviously, this can only be invoked once and only on accepted participants.
TestSK( $\Pi _{i}^{S}$ ): To the ultimate goal of challenging the confidentially of $subk_{i}^{T}$ , ${\mathcal {A}}$ can run TestSK( $\Pi _{i}^{S}$ ) against U. The result depends on a a random chosen bit b, if $b=1$ then ${\mathcal {A}}$ is given $subk_{i}^{{T}}$ the subsession key, otherwise a random value from the same probability distribution is given to ${\mathcal {A}}$ .

Definition of Adversaries and their advantages

The following terminology is useful in simplifying the elimination of trivial adversarial threats.

Definition VI.1 Accepted $\Pi _{i}^{S}$ is fresh if none of the following is true:

RevealGK( $\Pi _{j}^{s}$ ) for $U_{j}\in plist$ .
Corrupt( $U_{j}$ ) invoked for any $U_{j}\in plist$ before any Send( $\Pi _{i}^{S},.$ ).

Definition VI.2 A pair of $\Pi _{i}^{S},spid_{i}^{S}$ is fresh, if $\Pi _{i}^{S}$ is accepted and if none of the following is true:

RevealSK( $\Pi _{j}^{s},spid_{i}^{S}$ ) for $U_{j}\in plist$ .
Corrupt( $U_{j}$ ) invoked for any $U_{j}\in plist$ before any Send( $\Pi _{i}^{S},.$ ).

Definition VI.3 An AKE Adversary for the join key agreement ${\mathcal {A}}_{{join}}$ is a probabilistic polynomial time algorithm (ppt) which can invoke all the functions given above with a condition that the TestGK is invoked at least once against a fresh instance $\Pi _{i}^{S}$ which stays fresh until the end of the game. The game ends when ${\mathcal {A}}_{{join}}$ outputs its guess for b. We say a key exchange protocol is secure if the following function is negligible:

$max_{{\forall {\mathcal {A}}_{{join}}}}|2Pr(Output({\mathcal {A}}_{{join}})=b)-1|$

Similarly we define ${\mathcal {A}}_{{leave}}$ the Adversary leaving the session:

Definition VI.4 An AKE Adversary for the leave key agreement ${\mathcal {A}}_{{leave}}$ is a ppt which can invoke all the functions given above with the condition that one of the invocations of TestSK is invoked against a fresh instance $(\Pi _{i}^{S},spid_{i})$ which stays fresh till the the end of the game. The game ends when ${\mathcal {A}}_{{join}}$ outputs its guess for b for that invocation. We say a key exchange protocol is secure if the following function is negilgible:

$max_{{\forall {\mathcal {A}}_{{leave}}}}|2Pr(Output({\mathcal {A}}_{{leave}})=b)-1|$

Forward Secrecy Adversary

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 without forward secrecy. In this sense, the resistance against forward secrecy adversary is included in AKE adversarial model.

Deniability Adversary

We use the deniability adversary of [BoSt06], however following the path of [GRK06], we limit the security input of the deniability adversary in order to prevent the adversary from receiving input from the judge.

'Definition VI.5 A Deniability Adversary ${\mathcal {A}}_{{deny}}$ with bound $q_{c}$ and security input $Aux$ is a ppt algorithm which can invoke Send and Reveal as desired and Corrupt as many as $q_{c}$ times. At the end, ${\mathcal {A}}_{{deny}}$ will output a transcript $T_{{{\mathcal {A}}_{{deny}}}}(Aux)$ .

Definition VI.6 For each ${\mathcal {A}}_{{deny}}$ , we define a simulator ${\mathcal {S}}_{{deny}}$ , is a ppt algorithm which receives the same input as ${\mathcal {A}}_{{deny}}$ . It can invoke Corrupt $q_{c}$ times in addition to Send and Reveal but only against corrupted instances. It terminates by outputting a transcript $T_{{{\mathcal {S}}_{{deny}}(Aux)}}$ .

Definition VI.7 A deniability judge ${\mathcal {J}}$ with security input $Aux$ is a ppt algorithm which can invoke arbitrary number of deniability adversaries ${\mathcal {A}}_{{deny}}$ with security input $Aux$ . On each execution of ${\mathcal {A}}_{{deny}}$ a corresponding ${\mathcal {S}}_{{deny}}$ runs with the same input. At the end a confidential random bit b is generated, and either $T_{{{\mathcal {A}}_{{deny}}}}(Aux)$ or $T_{{{\mathcal {S}}_{{deny}}}}(Aux)$ is presented to ${\mathcal {J}}$ based on whether $b=1$ or 0 respectively.

Definition VI.8 We call a Group AKE deniable with respect to input set $Aux$ , if the following advantage is negligible: $max_{{\forall {\mathcal {J}}}}|2Pr(Output({\mathcal {J}},Aux)=b)-1|$

Similar to [GRK06], we claim that the AKE presented in this paper is deniable when $Aux$ is equal to the set of valid messages eavesdropped by ${\mathcal {A}}_{{deny}}$ during other sessions. This, in particular, excludes a transcript computed by ${\mathcal {J}}$ such as a group element whose discrete logarithm is only known to ${\mathcal {J}}$ (This means ${\mathcal {A}}_{{deny}}$ is given $g^{a}$ but is unaware of a).

Secure Multiparty Channel Adversary

The desirable way to define an adversary for a multiparty chat session is a secure channel model similar to the two-party secure channels described in ^[CaKr01] and ^[KPW13]. However, defining such a model is outside of our current scope. It is desirable to later improve the security of the protocol bu considering such a model at a later stage. At present, we use a per message model for confidentiality and origin authenticity.

Message Origin Authentication Adversary

As each participant executes a sign and encrypt function before sending their authenticated ephemeral signing key, the message origin adversary model is based on a typical adversary for a signature scheme such as the one presented in [PVY00].

Adversarial power

In addition to adversarial functions defined in section 1.1.1. we must define the following function to allow for the adversary using the chosen-message attack.

MakeSend( $\Pi _{i}^{S},\Pi _{j}^{S},m$ ) causes the $\Pi _{i}^{S}$ to sign and send a valid message m to instance $\Pi _{j}^{S}$ . ${\mathcal {A}}$ will receive the transcript including the signature.

Definition of Adversary

Definition VI.9: Message Origin Authentication Adversary ${\mathcal {A}}$ is a polynomial time algorithm which has access to the Corrupt, Send, Reveal and MakeSend functions. The output of the algorithm should be a message m sent to instance $\Pi _{j}^{S}$ . The scheme is secure against Message Origin Adversary if the probability in which $\Pi _{j}^{S}$ believes that m has originated from an uncorrupted participant $U_{i}$ is negligible.

Message Confidentiality Adversary

The goal of adversary ${\mathcal {A}}_{{conf}}$ is to read, at least, part of the communications transcript during the session.

Adversary's challenges

The following set of functions model the confidentiality adversary's challenges. These reveal either a random value or an encrypted message. The adversary's advantage in distinguishing the cases should be translatable into an attack against the block cipher, AES in this case.

TestM( $\Pi _{i}^{S},m$ ): To the ultimate goal of challenging the indistinguishibility of $E(m)>$ , ${\mathcal {A}}_{{conf}}$ can execute TestM( $\Pi _{i}^{S},m$ ) against $U_{i}$ . As a result a random bit b is chosen, if $b=1$ then ${\mathcal {A}}_{{conf}}$ is given $E_{{s_{k}}}(m)<math>,theencryptedmessage,otherwisearandomvaluefromthesameprobabilitydistributionisgivento<math>{\mathcal {A}}_{{conf}}$ .

Definition of Adversaries and their advantages

Definition 1 A Confidentiality Adversary ${\mathcal {A}}_{{conf}}$ is a ppt which can invoke all the functions given in sections IV.1.1.1 and IV.1.1.3 with the condition that one of the invocations of TestM is invoked against an instance $\Pi _{i}^{S}$ where all instances in session s are fresh and stay fresh till the end of the game. The game ends when ${\mathcal {A}}_{{conf}}$ outputs its guess for b for that invocation. We say that the protocol is secure if the following function is negligible:

$max_{{\forall {A}_{{conf}}}}|2Pr(Output({\mathcal {A}}_{{conf}})=b)-1|$

Consistency Adversary

In (n+1)sec protocol, we attempt to ensure the consistency among participants all along the session incrementally, i.e. assuring consistency after receiving each message in a timely manner. However, we do not model the incremental aspect of consistency into the adversarial model, for the sake of simplicity.

Definition 1 Transcript Consistency Adversary ${\mathcal {A}}_{{cons}}$ is given the ability to invoke all functions in sections IV.1.1.1 and IV.1.1.3. We say the protocol is secure against Consensus Adversary if at least two uncorrupted accepted instances $\Pi _{i}^{S},\Pi _{j}^{S}$ possess the transcripts chain $TransChain_{{\Pi _{i}^{S}}}(l)\neq TransChain_{{\Pi _{j}^{S}}}(l)$ and they believe they have the $TransChain_{{\Pi _{i}^{S}}}(l)=TransChain_{{Pi_{j}^{S}}}(l)withnon-negligibleprobability.Fordefinitionof<math>TransChain_{{\Pi _{i}^{S}}}(l)$ see Section VII.4.1.

VII. Protocol High Level Design

To achieve the security properties listed in Section IV, we break the protocol into the following sub-protocols:

Deniable authenticated signature key and session key exchange, where participants deniably authenticate each other and agree on session key(s), while also exchanging ephemeral signing keys
Communication, where parties send authenticated confidential messages
Transcript consistency verification, where parties verify that all have received and seen an identical transcript in the same order, since the start of the chat session after receiving each messages.

Our choice of sub-protocols for (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.

In the following section we briefly describe our choice of the sub-protocols for each of the required tasks for a multi-party chat session.

VII.1 Design of Deniable Authenticated Signature Key Exchange

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.

For the choice of the base authenticated key exchange protocol, we suggest a variant based on ^[ACMP10]. The rationale for the choice is laid out as follows:

The base design of the protocol in ^[ACMP10] is the same as the base for ^[BVS05] (recommended by ^[Gun13a]). However, the protocol presented in ^[ACMP10] is simpler.
^[ACMP10] offers a peer-to-peer key exchange with no extra rounds, if needed.
^[BVS05] and ^[ACMP10] are superior to the widely studied ^[BCPQ01] and its dynamic variation ^[BCP01] both in security and performance ( $O(1)$ rounds).
^[BVS05] has been suggested by ^[Gun13b] for the reason described in ^[Gun13a]. We believe that the new deniable authentication approach, as it is similar to the SKEME protocol, satisfies the properties of deniability which ^[BVS05] considered crucial aside from the cooperating judge.
Security analysis of ^[GBNM11] and ^[BCGNP08] has found that ^[BVS05] is provably secure against all attacks (including the insider attacks) that the papers consider.
It is a two-round protocol and hence offers competitive efficiency considering the security property that it provides.
^[ACMP10] only needs one round of key re-agreement in the case of a participant leaving the chat, while ^[BVS05] enforces re-computation of Diffie-Hellman ephemeral keys and hence needs a minimum of two rounds plus overhead of re-authenticating the new ephemeral keys. This can significantly improve the efficiency of casual chat sessions where participants frequently enter and exit the chat.
Although the Schnorr based algorithm suggested in ^[BVS05] satisfies a more comprehensible deniable model, 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.
Although key exchange algorithms based on the standard model are considered theoretically more secure than those based on the random oracle model, there has been no proposal for a 2-round protocol in the standard model that promises forward secrecy. Therefore, due to the importance of usability and efficiency in our approach, we opted to for a ROM based protocol such as described by ^[BVS05] and ^[ACMP10].

VII.1a Sharing a secret among the group

All AGKE descriptions take the necessary steps to share a common secret confidentially among the group members along side other operations such as authentication and insuring partnership. To insure forward secrecy these methods mostly rely upon a P2P Deffie-Hellman key exchange. Most AGKE descriptions rely on sharing an equation and solving a specific linear system described in 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 IX.4 trades simplicity and generalizability (to a broadcast scheme c.f. Section VII.2) for bandwidth consumption.

VII.3 Message Authentication

As message authentication needs to be resistant to malicious insiders, following the outline of ^[GUVGC09], (n+1)sec signs each message using a public key signature scheme. The messages are signed with the ephemeral key of the sender. The authenticity of the origin can be verified by the public ephemeral key of the party distributed during the key exchange period.

VII.4 Transcript Ordering and Consistency

Since each message sent by any one participant is signed by the ephemeral private key generated for that 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. The consistency of the transcript (i.e. 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. In other words, we are verifying the reception of the message by the intended recipients.

By assuring transcript consistency, we also preventing $U_{i}$ from sending different messages to $U_{j}$ , $U_{k}$ while they believe they are seeing the same conversation. In absence of transcript consistency, when a central server is managing the chatroom, this attack requires $U_{i}$ to conspire with server, which is permeable in (n+1)sec threat model in accordance with the definition of transcript consistency in ^[GUVGC09].

The protocol offered in this document examines the transcript for such consistency. In the case that the underlying transport fails to provide this level of consistency, clearly the consistency test will fail. In this sense, failure of consistency does not distinguish between malicious activities or the absence of a reliable transport.

(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:

We require additionally that message order be preserved for the following reasons:

XMPP, as the main protocol considered for this design, delivers messages to all clients in the same order.
The (n+1)sec protocol detects if the adversary has manipulated the order of the messages rather than only dropping undesirable messages
It is simpler to authenticate an ordered transcript compared to an unordered transcript.

We also require that each participant updates all other participants about their view of the session transcript every time they send a message, along with requiring heartbeat, this ensures that participants are aware whether or not they are all seeing the same transcript during the session.

There are some cases where XMPP can fail our reliability assumption. In such cases, our consistency checks will fail. More advanced end-to-end recovery techniques are able to rescue such a scenario. We do not specify such techniques currently, though later versions of the protocol may rectify this.

Definitions and assumptions

Transport assumption: We assume the central server reliably delivers messages to everyone, including the original sender, in the same order.

Definition Each message M (sent after session S has been established) has an implicit server-sequence-number seqnum(M), a receive-parent: parent(M) (or recv-parent) the seqnum of last message the sender has received before sending M and a sender-sequence-number own-seqnum(M). We interchangeable use m when refering to both a message and its seqnum.

Once a message M with seqnum m is received by instance $\Pi _{i}^{S}$ from the server (including participants own messages sent), a $TranscriptChain_{i}^{S}[m]$ may be calculated recursively as follows:

$TrascriptChain_{i}^{S}[m]:=(M,Hash(TranscriptChain_{i}^{S}[m-1]))$

(we define TrascriptChain[0] = (sk^S_i, sid_i))

A new message M contains p the seqnum of recv-parent of m, $Hash(TranscriptChain_{i}^{S}[p])$ and own-seqnum(M).

We say instance $\Pi _{i}^{S}$ has accepted message m if it has been received by $\Pi _{i}^{S}$ , then decrypted-verified.

We say instances $\Pi _{i}^{S}$ and $\Pi _{j}^{S}$ have reached mutual consistency for message m if both accepted message m and have calculated the same hash of $TranscriptChain(m)$ and verified $H_{j}(TranscriptChain_{i}^{S}[m]))==H_{i}(TranscriptChain_{i}^{S}[m])$ .

We say session S has reached consistency on message m, if all instances $\Pi _{i}^{S},\Pi _{j}^{S}\in plist^{S}$ , $\Pi _{i}^{S}$ and $\Pi _{j}^{S}$ have reached mutual consistency.

Server order

All clients see the same message order from the server. All messages are sent to all users. Aside from the presence messages (messages which indicate a user is joining or leaving a chatroom or if they have been inactive for a long time) sent by the server, messages are sent by users.

All messages in a room have a unique sequence number (0, 1, ...). We assume that the server is unaware of sequence numbers (e.g. XMPP MUC); clients must allocate them implicitly when receiving messages.

VIII. (n+1)sec Protocol: Step by Step

In this section we present the (n+1)sec protocol in algorithmic format. All user IDs should be considered the modulo number of participants in the room.

Deniable authentication is derived from the Triple Diffie-Hellman algorithm presented in ^[Sys14]. Joining the room is a variation of the two-round mBD+P protocol presented in ^[ACMP10] where the authentication step has been made deniable. Leaving the room is the one-round mBD+S from ^[ACMP10]. In both cases, we have added a key confirmation round (round 3) as recommended by ^[ChMa10] to provide mutual authentication as defined in ^[GBNM11].

VIII.1 Schematic view of the key exchange

The protocol computes a unified session key for all participants. This imposes, in particular, the necessity that all $plist_{i}$ ' is identical for all participants.However, as consistent view is part of (n+1)sec security model, it does not impose extra limitation on the protocol. For more information please see Appendix B: Participatory vs individually independent computation of group keys.

For simplicity, group operation is written multiplicatively (even though it is actually an elliptic curve point operation traditionally represented by addition).

Whenever our design deviates from ^[ACMP10], it is marked in yellow. We have abstracted out the steps mentioned in ^[ACMP10] as an independent primitive in pink, however the resulting computation is identical with the one in ^[ACMP10] protocol:

Algorithm 1

Round	Step	Description	Pseudo-code	Type
1	1	Generate ephemeral DH private key	$x_{i}\leftarrow [0,order(g)]$	Computation
	2	Generate DH key for BD, Triple DH and Signature	$y_{i}\leftarrow g^{{x_{i}}}$	Computation
	3	Broadcast User identity and the DH key	$(U_{i},y_{i})$	Broadcast
2	4	Compute Session Id	$sid_{i}\leftarrow (U_{1}\|y_{1}\|\dots \|U_{n}\|y_{n})$	Receive
	5	Generate Triple Diffie-Hellman P2P keys	$k_{{i,j}}\leftarrow H({y_{j}}^{{LSK_{{U_{i}}}}},LPK_{{U_{j}}}^{{x_{i}}},y_{j}^{{x_{i}}})\;\forall j\neq i$	Computation
	6	Generate key confirmations	$kc_{i}\leftarrow (H(k_{{i,1}},U_{1}),\dots ,H(k_{{i,n}},U_{n}))$	Computation
	7	Generate secret shares	$z'_{i}\leftarrow (H(k_{{i,j}},sid_{i})\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,\dots ,n\})$	Computation
	8	Encrypt shares	$z_{i}\leftarrow GroupEnc(k_{{i,j}}\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,\dots ,n\},z'_{i})$	Computation
	9	Sign identity, shares	$\sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)$	Computation
	10	Broadcast encrypted shares and confirmation	$(U_{i},z_{i},\sigma _{i},$ $kc_{i}$ )	Broadcast
3	11	Check the validity of key confirmation	$H(k_{{j,i}},U_{i}){\stackrel {?}{=}}kc_{j}[U_{i}]\;\forall j\neq k$	Receive
	12	Check signatures	$Verify_{{y_{j}}}(\sigma _{j})\;\forall j\neq i$	Computation
	13	Check Session Ids	$sid_{j}{\stackrel {?}{=}}sid_{i}\;\forall j\neq i$	Computation
	14	Generate session key	$sk_{{i}}\leftarrow H(GroupDec(k_{{i,l}}\forall l,z_{j})\forall j,sid_{i})=H(z'_{1},\dots ,z'_{n},sid_{i})$	Computation
3	15	Broadcast session confirmation	$(sc_{{i}}\leftarrow H(sk_{i},U_{i}),sigma_{i}\leftarrow Sign_{{x_{i}}}(sc_{{i}}))$	Broadcast
-	16	Check the validity of session confirmation	$H(sk_{{i}},U_{j}){\stackrel {?}{=}}sc_{j}\;\forall j\neq i$	Receive
	17	Check signatures	$Verify_{{y_{j}}}(\sigma _{j})\;\forall j\neq i$	Computation

Triple Diffie-Hellman authentication

(n+1)sec uses a varient of Triple Diffie-Hellman (TDH) protocol also employed in Textsecure protocol ^[Mo13] to carry 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, $k_{{i,j}}=k_{{j,i}}$ .

Algorithm 1.1 Triple Diffie-Hellman between $U_{i}$ and $U_{j}$ assuming i < j

Round	Step	Description	Pseudo-code	Type
1	1	Generate ephemeral DH private key	$x_{i}\leftarrow [0,order(g)]$	Computation
	2	Generate ephemeral DH public key	$y_{i}\leftarrow g^{{x_{i}}}$	Computation
	3	Broadcast User identity and the DH key	$(U_{i},y_{i})$	Broadcast
2	4	Receive other party id and ephemeral DH public key	$(U_{j}\|y_{j})$	Receive
	5	Generate Triple Diffie-Hellman P2P keys	$k_{{i,j}}\leftarrow H({y_{j}}^{{LSK_{{U_{i}}}}},LPK_{{U_{j}}}^{{x_{i}}},y_{j}^{{x_{i}}})$	Computation
	6	Send key confirmation to other party	$kc_{i}\leftarrow H(k_{{i,j}},U_{j})$	Broadcast
-	7	Receive and Check the validity of key confirmation	$kc_{j}{\stackrel {?}{=}}H(k_{{j,i}},U_{i})$	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 ${\mathcal {S}}:=\{U_{1},...,U_{n}\}$ and for each $i,j$ , let $k_{{i,j}}$ be a secret shared between and only between $U_{i}$ and $U_{j}$ . The goal of group ${\mathcal {S}}$ is that:

Each member of group $U_{i}$ to generate and share a secret $z'_{i}$ among the member of group G using public channel ${\mathcal {C}}$ .
$z'_{i}$ remains unknown for any ${\mathcal {A}}\not \in G$ eavesdropping the channel ${\mathcal {C}}$ .

To this end each member $U_{i}$ compute $z_{i}:=GroupEnc(k_{{i,j}}\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,...,n\},z'_{i})$ and broadcast $z_{i}$ on ${\mathcal {C}}$ . Later on when $U_{i}$ receives all $z_{j}$ . It recovers all secrets $z'_{i}$ by computing $GroupDec(k_{{i,j}}\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,...,n\},z_{i})$ .

(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 $U_{i}$ and $U_{j}$ . In original, algorithm it is simply $g^{{x_{i}}}{x_{j}}$ . In (n+1)sec, it is the triple DH secret $H({y_{j}}^{{LSK_{{U_{i}}}}},LPK_{{U_{j}}}^{{x_{i}}},y_{j}^{{x_{i}}})$ . 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

In almost any practical case, participants join the chat sequentially. It is assumed that multiple participants cannot join simultaneously. For the sake of efficiency one can adjust the implementation to have a threshold time to wait and thus start a chat with more participants. However, this makes the implementation significantly more complicated without any evident efficiency benefit.

Therefore, our assumption is that a secure chat is always set up when a participant starts the chat room. Additional participants would be added sequentially using Algorithm VIII.3, as they enter the chat. Algorithm 1 describes the chat room setup protocol.

Algorithm 2

Description	Pseudo-code	Type
Generate ephemeral DH private key of the room initiator	$x_{i}\leftarrow [0,order(g)]$	Computation
Generate DH key for BD, Triple DH and Signature	$y_{i}\leftarrow g^{{x_{i}}}$	Computation
Set participant list	$plist\leftarrow [U_{i}]$	Computation

VIII.3 Join

Joining a chat involves two different procedures: the Join procedure, described in Algorithm 2, which runs on the new participant’s instance, and an Accept New Participant Procedure, described in Algorithm 3, which runs on the clients of participants that are already in the chat.

When a new participant $U_{{n+1}}$ joins the chat, current participants can still use their established authenticated ephemeral public key (to derive the $sessionKey_{{new}}$ and as their signature verification key). Confidentiality of $sessionKey_{{old}}$ is guarded against the new participant by Diffie-Hellman key shares hashed alongside the session id (which is dependent on the list of participants). The new participant cannot combine the old and new shares to recover $sessionKey_{{old}}$ . The fact that old participants do not need to compute new ephemeral keys (and re-verify their ephemeral identities) decreases the computational complexity of the protocol.

The new participant needs to authenticate everybody already in the room and hand them their ephemeral key. All the parties already in the room only need to authenticate the new participant and need to send to them their ephemeral DH key. These procedures are described in Algorithm 3 and 4. After initial authentication step, all parties follow the same procedure to initiate a new session following Algorithm 5.

Authentication Step for new Joining party

Algorithm 3

Description	Pseudo-code	Type
Generate ephemeral DH private key	$x_{i}\leftarrow [0,order(g)]$	Computation
Generate DH key for BD, Triple DH and Signature	$y_{i}\leftarrow g^{{x_{i}}}$	Computation
Broadcast User identity and the DH key	$(U_{i},y_{i})$	Broadcast
Receive other users' id/key	$plist_{i}\|klist_{i}\leftarrow (U_{1}\|y_{1}\|\dots \|U_{n}\|y_{n})\cup (U_{i},y_{i})$	Receive
Generate Triple Diffie-Hellman P2P keys	$k_{{i,j}}\leftarrow H({y_{j}}^{{LSK_{{U_{i}}}}},LPK{U_{j}}^{{x_{i}}},y_{j}^{{x_{i}}})$	Computation
Generate key confirmations	$kc_{i}\leftarrow ((U_{1},H(k_{{i,1}},U_{1})),\dots ,(U_{n},H(k_{{i,n}},U_{n})))$	Computation

After this step joining user will proceed to "initiate new session" by Algorithm 5.

Authentication Step for parties in the room

For other participants to a accept a new participant only, the authentication step is different. After current participants authenticate the new user, they proceed to update session.

Algorithm 4

Description	Pseudo-code	Type
broadcast all user's identities	$(U_{1}\|y_{1}\|\dots \|U_{n}\|y_{n})$	Broadcast
Receive other users' id/key and update participant list	$(plist_{i}\|klist_{i})\cup (U_{j}\|y_{j})$	Receive
Generate Triple Diffie-Hellman P2P key for the new participant	$k_{{i,j}}\leftarrow H({y_{j}}^{{LSK_{{U_{i}}}}},LP_{{U_{j}}}^{{x_{i}}},y_{j}^{{x_{i}}})$	Computation
Generate key confirmations	$kc_{{i,j}}\leftarrow (U_{i},H(k_{{i,j}},U_{i}))$	Computation

After this step users will proceed to "initiate new session" using Algorithm 5.

Initiate new session

Algorithm 5

Description	Pseudo-code	Type
Compute Session Id	$sid_{i}\leftarrow H(U_{1}\|y_{1}\|\dots \|U_{n}\|y_{n})$	Computation
Cancel any pending request for establishing a session with the same Id	AxeNewSessionRequestTimer $(sid_{i})$	Computation
Generate secret shares	$z'_{i}\leftarrow (H(k_{{i,j}},sid_{i})\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,\dots ,n\})$	Computation
Encrypt shares	$z_{i}\leftarrow GroupEnc(k_{{i,j}}\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,\dots ,n\},z')$	Computation
Sign identity, shares	$\sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)$	Computation
Broadcast key shares and confirmation (if any)	$(U_{i},z_{i},\sigma _{i},kc_{i})$	Broadcast
Receive other user(s)' key shares and confirmation of unauthenticated users or Time out	Wait to Receive ( $U_{j}\|z_{j},\sigma _{1},kc_{{ji}})$ for $U_{j}$ unauthenticated or Timeout by(2 $\times$ BROADCAST_LATENCY+INTERACTION_GRACE_INTERVAL, Drop inactive users, queue a new session request)	Receive
Check the validity of key confirmation of unauthenticated users	$kc_{j}[U_{i}]{\stackrel {?}{=}}H(k_{{i,j}},U_{i})$ for unauthenticated $U_{j}$	Computation
Check signatures	$Verify_{{y_{i}}}(\sigma _{j})$ for j in {1,...,n}	Computation
Check Session Ids	$sid_{j}{\stackrel {?}{=}}sid_{i}\;\forall j\neq i$	Computation
Generate session key	$sk_{{i}}\leftarrow H(GroupDec(k_{{i,l}}\forall l,z_{j})\forall j,sid_{i})=H(z'_{1},\dots ,z'_{n},sid_{i})$	Computation
Broadcast session confirmation	$(sc_{{i}}\leftarrow H(sk_{i},U_{i}),sigma_{i}\leftarrow Sign_{{x_{i}}}(sc_{{i}}))$	Broadcast
Check the validity of session confirmation	$H(sk_{{i}},U_{j}){\stackrel {?}{=}}sc_{j}\;\forall j\neq i$	Receive
Check signatures	$Verify_{{y_{j}}}(\sigma _{j})\;\forall j\neq i$	Computation
Initiate the TranscriptChain	$TrascriptChain_{i}^{S}[0]\leftarrow (sk_{i}^{S},sid_{i})$	Computation
Initiate the last_sender_seq_num array	$last\_sender\_seq\_num\leftarrow (0,...,0)$	Computation
Initiate the own_seq_num to 0	$own\_seq\_num\leftarrow 0$	Computation

Sending and receiving messages while joining is in progress

In situations where a prolonged joining process (due to connection problems or malicious activities) has an adverse effect on the user experience, it might be desirable to enable that joining users can communicate with the parties in the room, while maintaining minimum assurances of authenticity, confidentiality, forward secrecy, as well as consistency only among participants.

Consistency aspects of (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.

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.

Farewell

Run by exiting user.

Algorithm 6

Description	Pseudo-code	Type
Send farewell message	Send("Leaving!")	Broadcast
Wait to receive hashes of TranscriptChain or Timeout	Wait to Receive() or Timeout by((2 $\times$ BROADCAST_LATENCY)+INTERACTION_GRACE_INTERVAL)	Receive

Shrink

When the remaining participants receive the farewell message they need to reply with the Hash of TranscriptChain of the last message seen by the leaving user. They also need to re-run the one round key update algorithm. However, they only need a notice from the server that the user is leaving to initiate a subsession excluding the leaving user.

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

Algorithm 7

Description	Pseudo-code	Type
Send Hash of TranscriptChain of last message seen by leaving user	Send( $H(TranscriptChain_{i}^{S}[Parent(m_{{farewell}})])$ )	Broadcast
Remove leaving user's id/key and update participant list	$(plist_{i}\|klist_{i})\backslash (U_{j}\|y_{j})$	Computation

Users will proceed to "initiate new session" steps.

VIII.5 Secure Send and Receive

After the session key is established, participants will use Algorithms 5 and 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 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.

On Receive, the protocol updates who has seen which pieces of the key shares. The protocol also generates a new group key if the new key shares have been received from all participants. Those who have not updated their key shares eventually time out via their heartbeat interval.

Send

Algorithm 8

Description	Pseudo-code	Type
prepend session id and sender id	$m\leftarrow (sid,U_{i},m)$	Computation
Generate new DH Key or new secret share if needed and append	$m\leftarrow (m,s)$	Computation
Increment own sequence number	$own\_seq\_num\leftarrow own\_seq\_num+1$	Computation
Append the hash of the TranscriptChain, up to the parent of the message being sent	$m\leftarrow$ (m, $H(H(parent(m)),H(TransciptChain_{i}^{S}[parent(m)-1]))$ , $parent\_id(m)$ , $own\_seq\_num$ )	Computation
Generate a random nonce and append to the message	$m\leftarrow (m,rand(128bit))$	Computation
Sign the message and append the signature	$m\leftarrow (m,Sign_{{x_{i}}}(m))$	Computation
Encrypt	$e\leftarrow Enc_{{k_{{sid}}}}(m)$	Computation
Broadcast the message	$(sid_{i},e)$	Broadcast
Reset Heartbeat timeout timer	ResetHeartbeatTimer()	Computation
Set ACK timeout timer if the message has user content	$meta\_only{\stackrel {?}=}$ False then ResetHeartbeatTimer()	Computation

Receive

Algorithm 9

Description	Pseudo-code	Type
Decrypt message	$sid_{{rec}},sender\_id,m,s,h,parent\_id,sender\_seq\_num,sigma\leftarrow Dec_{k}(m)$	Computation
Check signature	$Verify_{{sender\_id}}(m,\sigma )$	Computation
Compute message sequence number	$seqnum(m)\leftarrow$ ComputeSeqNum(m)	Computation
Verify session id and transcript consistency and sender sequence number, issue a warning in case of failure	$sid_{i}{\stackrel {?}{=}}sid_{{rec}}\;$ and $\;h{\stackrel {?}{=}}H(H(parent(m)),H(TranscriptChain_{i}^{S}[parent(m)-1]))$ and $sender\_seq\_num{\stackrel {?}{>}}last\_own\_seq\_nums[sender\_id]$	Computation
Update TranscriptChain if possible	$TranscriptChain_{i}^{S}[seqnum(m)]=(H(m),H(TranscriptChain_{i}^{S}[seqnum(m)-1]))$	Computation
Update sender sequence number record	$last\_own\_seq\_nums[sender\_id]\leftarrow sender\_seq\_num$	Computation
Update sender's ephemeral key or share secret	$y_{j}\leftarrow s\;{\textrm {or}}\;z_{{j}}\leftarrow s$	Computation
If all users' share are received, generate session key	$sk_{{i}}\leftarrow H(GroupDec(k_{{i,j}},z_{j}\;\forall j),sid_{i},U_{j})\;\forall j\neq i$	Computation
Update ack timeout timer	AxeAckTimeoutTimer $(parent(m),sender_{i})$	Computation
Update rekey timeout timer	ResetRekeyTimeOut( $sender_{i}$ )	Computation
If the message has content set up ACK timer	$meta\_only{\stackrel {?}=}True$ then $SetACKTimer(m)$	Computation
return m	If $meta\_only{\stackrel {?}{=}}False$ then return m	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

Description	Pseudo-code	Type
If we are part of a session id in the room call Send	Send	Broadcast
For all confirmed users not in session call P2P Send	P2P Send	Broadcast

Algorithm 9.2 Extended Receive

Description	Pseudo-code	Type
If m has session id call Receive	if m has sid then Receive	Computation
If m has key id, call P2P Receive	P2P Send	Computation

Algorithm 9.3 P2P Send

Description	Pseudo-code	Type
Prepend key id and sender id	$m\leftarrow (key\_id,U_{i},m)$	Computation
Generate a random nonce and append to the message	$m\leftarrow (m,rand(128bit))$	Computation
Sign the message and append the signature	$m\leftarrow (m,Sign_{{x_{i}}}(m))$	Computation
Encrypt	$e\leftarrow Enc_{{k_{{key\_id}}}}(m)$	Computation
Broadcast the message	$(key\_id,e)$	Broadcast

Algorithm 9.4 P2P Receive

Description	Pseudo-code	Type
Decrypt message	$key_{{id}},sender\_id,m,sigma\leftarrow Dec_{{k_{{key\_id}}}}(m)$	Computation
Check signature	$Verify_{{sender\_id}}(m,\sigma )$	Computation
return m	return m	Computation

VIII.6 Reaching Consistency

The protocol provisions two procedures to reach consistency in different cases: (a) reaching consistency for arbitrary messages during the course of a conversation, and (b) reaching consistency when an instance $\Pi _{i}^{S}$ leaves. Case (b) may be viewed as a special instance of case (a) plus the additional premise that $\Pi _{i}^{S}$ must reach consistency as soon as possible (because they want to leave), and that they don't care about reaching consistency for any subsequent messages that they might receive after their final "farewell" message.

Reaching consistency for arbitrary messages during the course of a conversation:

Algorithm 10

Description	Pseudo-code	Type
Receive m with parent p from $\Pi _{j}^{S}$	$m\leftarrow seqnum(M),p\leftarrow parentnum(m)$	Computation
Compare hash of TranscriptChain_j[p] with own value of it, issue a warning if it fails.	$H(TranscriptChain_{j}^{S}[p]){\stackrel {?}{=}}H(TranscriptChain_{i}^{S}[p])$	Computation
Compute TranscriptChain^S_i[m]	$plist\leftarrow [U_{i}]$	Computation

Case (b): when an instance $\Pi _{i}^{S}$ wants to part, they send a "farewell" message m which contains $Hash(TranscriptChain_{i}^{S}[p])$ .

Everyone should include $Hash(TranscriptChain_{j}[p])$ in their re-key message
When $\Pi _{i}^{S}$ reaches mutual consistency for p may leave or otherwise (if received hashes and their owns are non-matching) shows a warning.
- $\Pi _{i}^{S}$ won't have a chance to reach consistency for the messages receives after p

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

Description	Pseudo-code	Type
Initiate meta data with current state of knowledge of new ephemeral keys and secret shares	$meta\_data\leftarrow ustate_{i}[j]$ for all j in {1,...n}	Computation
Include the new ephemeral key if participant $U_{j}$ has not receive it	If $ustate_{i}[j]{\stackrel {?}{=}}0$ meta_data \leftarrow $y_{{i_{{new}}}}$	Computation
If (all) participants have sent their ephemeral keys compute the shared secret	If $ustate_{{j}}[i]{\stackrel {?}{=}}1$ for all j in {1,...n}, then $meta\_data\leftarrow (meta\_data,GroupEnc(k_{{i_{j}}}\,{\textrm {for}}\,j\neq i\,{\textrm {and}}\,j\in \{1,\dots ,n\},z'))$	Computation
Return meta data	return meta_data	Computation

VIII.8 Heartbeat and Timeout

Heartbeat is an empty message which contains only meta data. The meta data consists of information used to compute a new key and the most updated hash of transcript chain.

The protocol sends a heart beat only if the user has not sent any messages for a specific period of time.

The heartbeat is necessary to ensure three properties:

- Periodic transcript consistency check. - In session forward secrecy. - Freshness

To achieve these goals three time out periods are defined when heart beat sending is required. Additionally, we define an interval to model the latency in the underlying transport. These should be defined to cover common cases (e.g. 95th-percentile):

ACK_GRACE_INTERVAL: When $\Pi _{i}^{S}$ a receives a non-empty message it needs to inform the group about the transcript update no later than ACK_GRACE_INTERVAL time. Therefore if $\Pi _{i}^{S}$ f $U_{i}$ does not send a message ACK_GRACE_INTERVAL seconds after receiving a non empty message, $\Pi _{i}^{S}$ will send a heartbeat.

REKEY_GRACE_INTERVAL, to ensure in session forward secrecy, the protocol requires that each $U_{i}$ updates their DH ephemeral key as well as group key. After a session is established or it was rekeyed, each $\Pi _{i}^{S}$ needs to send its new DH ephemeral key no later than REKEY_GRACE_INTERVAL. Therefore if $\Pi _{i}^{S}$ has not sent any message by that

period of time, it issues an empty message. Similarly after receiving all ephemeral keys from all participants, $\Pi _{i}^{S}$ needs to send its secret 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.

BROADCAST_LATENCY: Modelling the amount of time which a message takes to reach the server and broadcast to the other clients. It should be based on the transport considered.

Failure to heartbeat and inactivity timers

Whenever, a message m is received a timer of (2*BROADCAST_LATENCY)+ACK_GRACE_INTERVAL) period is set. If the $H(Transcript_{j}[m'])$ for a $m'\geq m$ is received from all participants, the timer is cancelled. Otherwise at the time out, the protocol issues a local UI warning and cancel the warning if/when such a hash is received and is consistence among participants.

When a new session key is computed as well as when $\Pi _{i}^{S}$ 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 $\Pi _{i}^{S}$ excludes users who failed to contribute from the $plist$ 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

Description	Pseudo-code	Type
Drop inactive users	$plist_{i}\leftarrow plist_{i}\backslash inactive\_participant\_list$	Computation
Recompute Session Id	$sid_{i}\leftarrow H(U_{1}\|y_{1}\|\dots \|U_{{n_{{active}}}}\|y_{{n_{{active}}}})$	Computation
Set up timer to request a new session	SetTimer(PLIST_UPDATE_GRACE_INTERVAL, initiate new session)	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 value

Shorts (DTSHort):

   2 byte unsigned value, big-endian

Length (DTLength):

   4 byte unsigned value, big-endian

HashBlock (DTHash):

   32 byte data

Opaque variable-length data (DTOpaque):

   4 byte unsigned len, big-endian
   len byte data

All messages have mandatory version and message type fields:

version (DTShort), message type (DTShort), type-specific part

"version" is equal to 0001.

"message type" is chosen from the following list:

   UNKNOWN                     =0x00, //Invalid
   JOIN_REQUEST                =0x0a, //Session establishement
   PARTICIPANTS_INFO           =0x0b,
   JOINER_AUTH                 =0x0c,
   GROUP_SHARE                 =0x0d,
   SESSION_CONFIRMATION        =0x0e, //In session messages
   IN_SESSION_MESSAGE          =0x10,
   P2P_MESSAGE                 =0x20,

many messages use "participant id" which is defined as follows:

   participant nickname, participant fingerprint (DTHash)

participant nickname is a string. Its size can be determined by the length of the participant id - 32. The participant finger print is a 32bit representation of an ed25519 public key.

"participant info" is defined as

   participant id, ephemeral public key (DTHash), authenticated (DTByte)

From the point of view of the sender of the message the participant is authenticated if "authenticated" is 1. Unauthenticated if it is 0.

The following sections will describe the type-specific part for each type of messagee information about the joiner.

Join Request

   participant_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 32bit public key that the user is going to use in the next session.

(n+1)sec in session Message Structure

Every (n+1)sec message sent after establishment of a session has the following format:

   :o3np1sec:Base64EnocodedMessage

The message has the following structure.

    sid (DTHash), Encrypted part of the message, Signature (DTHashx2)

Encrypted message can be decrypted by the session key

   sender_index (DTLength), own_sender_id (DTLength), parent_id (DTLength), hash of TranscriptChain of the message (DTHash), nonce (DTHash), message load

"session ID" and the "sender_index" are prepended in part to address concerns of [Da01].

"own_sender_id" is the sequential id assigned to each message by its sender, used for transcript consistency check.

"parent_id" is the global sequential id of the last message seen by the sender before sending the message.

The message also includes the "hash of TranscriptChain" of the parent of the message as "additional authenticated data".

$H(TransciptChain[parent(m)])$

Note that we send the entry in the chain indexed by $parent(m)$ rather than $m$ . 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.

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.

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.

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.

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.

IX Cryptographic Primitives

IX.1 Hash Function

SHA256 is being used as the hash function and the random oracle. SHA256 provides a sufficiently secure hash primitive for the level of security provided by (n+1)sec and is widely implemented.

IX.2 Message Origin Authentication

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

IX.3 Message Encryption

We are using AES-256 in Galois/Counter Mode (GCM) with a shared group key for message encryption, we are following the suggestion by the original OTR protocol of using counter mode. However, unlike OTR, $(n+1)sec$ 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.

The added authentication, spares P@P send and receive routines from using digital signature.

With GCM mode, the authenticated encryption is generically secure by the result (and assumptions) of ^[Kr00].

IX.4 GroupEnc and GroupDec Functions

The GroupEnc and GroupDec functions defined in Section VIII.1, facilitate the collective generation of a secret(s) shared by the group. Here we mention two examples of such functions, and specify the functions for (n+1)sec' protocol:

Naive peer-to-peer GroupEnc/Dec:

The simplest path to design such primitives is to encrypt $z'_{i}$ using the p2p encryption secret between each pair of participants:

$GroupEnc((k_{{i,1}},...,k_{{i,n}}),z'_{i}):=(E_{{k_{{i,1}}}}(z'_{i}),...,E_{{k_{{i,n}}}}(z'_{i}))$ $GroupDec((k_{{i,1}},...,k_{{i,n}}),(z_{1},...,z_{n})):=(D_{{k_{{i,1}}}}(z_{1}[i]),...,D_{{k_{{i,n}}}}(z_{n}[i]))$

Linear System based GroupEnc/Dec:

Another possibility is that each user generates k linear equations of l variables such if the system of $k.n$ equations has m independent equations then m < l. The remaining equations should be generated using the mutual secrets $k_{{i,j}}$ .

An example of such a system is used by [BuDe95]. In which $k=1,l=n+1,m=n$ as follows:

Each user U_i generate equations (k_{i,i-1}+k_{i,i+1}=a_i) so the system for n equation $n+1$ variable will be:

Failed to parse (unknown function '\matrix'): \matrix{ x_1 + x_2 = a_1 \\ x_2+x_3= a_2 \\ \vdots \\ x_n + x_{n-1} = a_n \\}

Then each participant adds the equation of $x_{i}=k_{{i,i+1}}$ to the system and solves the derived system of $n+1$ -equation $n+1$ -unknown to recover the secrets.

in such a system:

$z'_{i}:=k_{{i,i-1}}=k{i-1,i}$ $GroupEnc((k_{{i,1}},...,k_{{i,n}}),z'_{i},z'_{{i+1}}):=z'_{{i}}\oplus z'_{{i+1}}$

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

$z'_{i}:=H(k_{{i,i-1}},sid_{i})$

While the naive peer to peer primitive is easier to understand and analyse, the second system gives the flexibility for the implementor to decide the trade off between the amount of data (number of equations) vs. the redundancy in the system (if some equations are not delivered the user can still compute a subset of secrets).

X. Next Steps

This 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 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 np1sec software library will be initially implemented in Cryptocat and (with your help) further developed to suit a variety of use-cases in the near future.

XI. Acknowledgements

The eQualit.ie team would like to give special thanks and note to the effort and dedication offered by Trevor Perrin and Ximin Luo to this project. They have been actively involved throughout the year and the result would not have been the same without their contribution. The team would also like to express thanks to Joseph Bonneau for his constructive comment and critisim to improve the protocol and its presentation. George Kadianakis for helping with the security proof and pointing out flaws and attack; Arlo Breault for his work on implementation of the protocol in the np1sec software library; David Goulet for valuable advice as well as continued assistance and support offered to the project; Prof. Payman Mohassel for his help and advice on the security model and 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.

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

^{[Be11] ^} Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin. "High-Speed High-Security Signatures.","CHES","978-3-642-23950-2","http://dblp.uni-trier.de/db/conf/ches/ches2011.html#BernsteinDLSY11". 2011. pages: 124-142","6917","Lecture Notes in Computer Science","Springer".

^{[BS07] ^} ¹ ² ³ ⁴ Bohli, Jens-Matthias, and Rainer Steinwandt. 2007. “Deniable Group Key Agreement.” In VIETCRYPT, edited by Phong Q. Nguyen, 4341:298–311. Lecture Notes in Computer Science. Springer. http://dblp.uni-trier.de/db/conf/vietcrypt/vietcrypt2006.html#BohliS06.

^{[BVS05] ^} ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ Bohli, Jens-Matthias, Maria Isabel Gonzalez Vasco, and Rainer Steinwandt. 2005. “Secure Group Key Establishment Revisited.” IACR Cryptology ePrint Archive 2005: 395. http://dblp.uni-trier.de/db/journals/iacr/iacr2005.html#BohliVS05a.

^{[BM] ^} ¹ ² Bonneau, Joseph, and Andrew Morrison. “Finite-State Security Analysis of OTR Version 2.” http://www.jbonneau.com/doc/BM06-OTR_v2_analysis.pdf

^{[BGB04] ^} ¹ ² ³ ⁴ Borisov, Nikita, Ian Goldberg, and Eric Brewer. 2004. “Off-the-Record Communication, or, Why Not to Use PGP.” In Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society, 77–84. WPES ’04. New York, NY, USA

^{[BCGNP08] ^} Colin Boyd, Yvonne Cliff, Juan Gonzalez Nieto, and KennethG. Paterson. 2008. “Efficient One-Round Key Exchange in the Standard Model.” In Information Security and Privacy, edited by Yi Mu, Willy Susilo, and Jennifer Seberry, 5107:69–83. Lecture Notes in Computer Science. Springer 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.

^{[CaKr01] ^} Ran Canetti, Hugo Krawczyk. 2001. “Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels” “EUROCRYPT Conference. Lecture Notes in Computer Science”. Edited by Birgit Pfitzmann.

^{[ChMa10] ^} Qingfeng Cheng, Chuangui Ma, "Security Weakness of Flexible Group Key Exchange with On-Demand Computation of Subgroup Keys", CoRR, 2010, http://arxiv.org/abs/1008.1221

^{[Da14] ^} George Danezis, Should Group Key Agreement be Symmetric and Contributory, http://conspicuouschatter.wordpress.com/2014/06/28/should-group-key-agreement-be-symmetric-and-contributory/

^{[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\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.

^{[GBN10] ^} M. Choudary Gorantla, Colin Boyd, and Juan Manuel González Nieto. 2010. One Round Group Key Exchange with Forward Security in the Standard Model. http://eprint.iacr.org/2010/083.pdf

^{[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.

^{[Gun13a] ^} ¹ ² ³ Matthew Van Gundy. April 2013. “[OTR-dev] Improved Deniable Signature Key Exchange for mpOTR.” http://matt.singlethink.net/projects/mpotr/improved-dske.pdf

^{[Gun13b] ^} ¹ ² ³ Matthew Van Gundy March 2013. “[OTR-dev] Improved Deniable Signature Key Exchange for mpOTR.” http://lists.cypherpunks.ca/pipermail/otr-dev/2013-March/001676.html.

^{[Kr00] ^}, "Krawczyk, Hugo","The order of encryption and authentication for protecting communications (Or: how secure is SSL?), 2001, Published: Cryptology ePrint Archive, Report 2001/045 http://eprint.iacr.org/

^{[KPW13] ^} Hugo Krawczyk and Kenneth G. Paterson, Hoeteck Wee. 2013. “On the Security of the TLS Protocol: A Systematic Analysis” in IACR Cryptology ePrint Archive.

^{[LVH13] ^} ¹ ² ³ Liu, Hong; Vasserman, Eugene Y.; 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/WhisperSystems/TextSecure/wiki/ProtocolV2.

^{[RGK05] ^} ¹ ² ³ Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. 2005. “Secure Off-the-Record Messaging.” In WPES, 81–89. Alexandria, VA, USA. http://dl.acm.org/citation.cfm?doid=1102199.1102216

^[KiSo00] Song, Boyeon; Kim, Kwangjo, "Two-Pass Authenticated Key Agreement Protocol with Key Confirmation","Progress in Cryptology —INDOCRYPT 2000","978-3-540-41452-0","http://dx.doi.org/10.1007/3-540-44495-5_21","2000"; "237-249",1977 "Lecture Notes in Computer Science",Springer Berlin Heidelber.

^{[Git11] ^} https://github.com/hellais/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 Section V) is correct if all accepted instances of $\Pi _{i}^{S}$ end up with the same participant lists $plist_{i}$ 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 $plist_{i}$ 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.

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 $sid$ 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 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.

[GUVGC09]

[BGB04]

[RGK05]

[BS07]

[BVS05]

[ACMP10]

[BM]

[Gun13a]

[Git11]

[LVH13]

[GBNM11]

[GBN10]

[CaKr01]

[KPW13]

[Gun13b]

[BCPQ01]

[BCP01]

[BCGNP08]

[Sys14]

[ChMa10]

[Mo13]

[BoMa10]

[Da02]

[Be11]

[Kr00]

[ACMP10]

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

[Be11]

[BS07]

2

3

4

[BVS05]

2

3

4

5

6

7

8

9

10

[BM]

2

[BGB04]

2

3

4

[BCGNP08]

[BoMa10]

[BCP01]

[BCPQ01]

[CaKr01]

[ChMa10]

[Da14]

[Da02]

[GUVGC09]

2

3

4

5

6

7

8

9

10

11

12

13

[GBN10]

[GBNM11]

2

3

4

[Gun13a]

2

3

[Gun13b]

2

@@ Line 1,333: / Line 1,333: @@
 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.
-* '''init a session stale session with new user'''
+* '''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.

Difference between revisions of "Np1sec"

Revision as of 20:09, 22 June 2016

Contents

Abstract

I. INTRODUCTION

II. History and literature review

III. Design rationale

IV. Security Properties

V. Chat Session Model

VI. Threat Models and Adversarial Goals

Deniable Authenticated Key Exchange Adversary

Authenticated Key Exchange Adversary

Adversarial power

Adversary's challenges

Definition of Adversaries and their advantages

Forward Secrecy Adversary

Deniability Adversary

Secure Multiparty Channel Adversary

Message Origin Authentication Adversary

Adversarial power

Definition of Adversary

Message Confidentiality Adversary

Adversary's challenges

Definition of Adversaries and their advantages

Consistency Adversary

VII. Protocol High Level Design

VII.1 Design of Deniable Authenticated Signature Key Exchange

VII.1a Sharing a secret among the group

VII.3 Message Authentication

VII.4 Transcript Ordering and Consistency

Definitions and assumptions

Server order

VIII. (n+1)sec Protocol: Step by Step

VIII.1 Schematic view of the key exchange

Triple Diffie-Hellman authentication

GroupEnc and GroupDec functions

(n+1)sec key exchange vs original Flexible Group Key Exchange of [ACMP10]

VIII.2 Chatroom Setup

VIII.3 Join

Authentication Step for new Joining party

Authentication Step for parties in the room

Initiate new session

Sending and receiving messages while joining is in progress

VIII.4 Leave

Farewell

Shrink

VIII.5 Secure Send and Receive

Send

Receive

Out of Session Send and Receive

VIII.6 Reaching Consistency

VIII.7 In-session Forward Secrecy

VIII.8 Heartbeat and Timeout

Failure to heartbeat and inactivity timers

Timing out during an interactive session

Drop inactive users, queue a new session request

VIII.9 (n+1)sec Message Dictionary

Join Request

Participant Info

Joiner Auth

Group Share

Session Confirmation

(n+1)sec in session Message Structure

(n+1)sec P2P Message Structure

VIII.10 (n+1)sec Session Management and Message Handling

Joiner

Confirmed Participant

Session transition

Finite State Table

Explaniantion of the handlers

IX Cryptographic Primitives

IX.1 Hash Function

IX.2 Message Origin Authentication

IX.3 Message Encryption

IX.4 GroupEnc and GroupDec Functions

X. Next Steps

XI. Acknowledgements

XII. References

Appendices

Appendix A: Asynchronous communication and Forward Secrecy

(n+1)sec key exchange vs original Flexible Group Key Exchange of ^[ACMP10]