learn.equalit.ie

Abstract

In this document we present the first public draft of mpSEQ - 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 mpSEQ project was inspired by Off-The-Record Messaging Protocol and subsequent efforts to explore a multi-party use-case for OTR in . The protocol is currently developed for Cryptocat - a browser based XMPP chat platform and assumes its use-cases. Most importantly, mpSEQ 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 libmpotr on our Github pages. Future protocol iterations will consider a variety of other real-world use cases and be platform independent.

In the following section we skim over relevant publications and their results. In Section III, we describe our approach and choice of security features. In Section IV, we overview the properties that we are aiming for in 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 which will be the base of the security proof for the protocol. 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 mpSEQ protocol steps at various stage in schematic and algorithmic format. We present our choice of primitives in Section IX. Finally, we conclude by describing work remaining to be done on this protocol.

II. History and literature review

Two-party Off The Record messaging (OTR) has been introduced in as a better alternative to PGP for casual Internet chat. OTR authors argue that using PGP for Internet chat is problematic due to the PGP scheme’s lack of forward secrecy and deniable transcript features. These properties are expected in Internet chat, since it mimics casual day-to-day real-world conversations where future deniability is implicit.

offers OTR as an alternative approach to PGP for simulating casual two-party chat on the Internet. While OTR uses symmetric encryption and message authentication to secure confidentiality and message integrity, it uses Diffie-Hellman key exchange as an approach to authenticate the other party in the chat.

There have been various security analyses and some criticisms of OTR since its introduction in 2004. For example, shows that the unauthenticated exchange of the OTR version identifier can pose a threat to authenticity: the adversary can force clients to downgrade to an older, insecure version of the protocol. They also make note of 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.

In , researchers criticize OTR’s approach in which the authenticity of the 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 (by the leak of the session key, for example) 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.

In , the authors offer a generalization of two-party OTR to the multi-party case. However, they do not specify the cryptographic primitives, neither do they give a formal definition of the adversaries nor the proof of 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.

Various attempts have been made to construct an efficient multiparty (known as group) authenticated key exchange protocol. Protocols proposed in and have been shown to be insecure against various adversarial models and . shows that the protocol introduced in is not secure against replaying the user’s message in another chat. The authors offer a slightly modified version of the protocol to remedy this.

Authors of introduce 2 protocols with forward secrecy to replace the vulnerable deniable authentication of OTR. Both and argue that SIGMA does not meet the definition of a truly deniable algorithm and the latter shows how it fails the deniability adversarial model introduced in . Alternatively , using the Schnorr zero-knowledge proof and signature algorithm, introduces a 4-round challenge-based authentication scheme that grants deniability to the two-round authenticated protocol described in .

offers a more efficient protocol than , 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.

III. Design rationale

The main motivation driving mpSEQ development is the lack of a provably secure and implementable multiparty chat protocol offering end-to-end encryption and applicable to a variety of use-cases. Our approach for mpSEQ design was based on the following rationales, listed in order of importance:

1. A protocol that is provably secure in a sufficiently strong adversarial model which addresses the most urgent requirement of users in need of security. These are: confidentiality, authenticity and forward secrecy.
2. Usability according to real world use-cases.
3. Providing some degree of deniability when it does not negatively impact usability or our [#IV._Security_Properties security goals]
4. Addressing security flaws in the OTR protocol.

To achieve these goals, we focused our studies on the OTR protocol and various subsequent protocols evolved from OTR such as the TextSecure protocol , as well as papers offering security analysis of the original OTR protocol. We designate the protocol suggested in as our starting point and apply various modifications to reach a desirable protocol which satisfies our goals.

A significant portion of this research suggests a better performing, more secure alternative to the key exchange protocol suggested in which is considered by various researchers to be one of the most troubling and inefficient aspects of the proposal. In-session transcript consistency and periodic heartbeats are other major departing points of mpSEQ from mpOTR .

In designing mpSEQ’s deniable authentication and key agreement protocol, we have followed the main idea of in choosing a provably secure authenticated key exchange method and replacing the signature-based authentication with a deniable one. We have chosen the protocol introduced in instead of , due to its superior efficiency. We abstract out the method where parties communicate their secret for additional flexibility.

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

Another major difference between mpSEQ and the suggested original protocol for mpOTR in is in-session transcript authentication, which happens every time a participant receives or send a message. The transcript authentication, which we refer to as transcript consistency check throughout this document, is an optimistic approach based on the assumption that the XMPP server provides a reliable and orderly message delivery.

Additionally, based on the conclusions of and , we are taking the following points into consideration:

• Using a more secure deniable key exchange algorithm, instead of naive Diffie-Hellman, and a more practical algorithm, rather than the peer-to-peer signature key exchange suggested in .
• Omitting forgeability and malleability from the protocol as recommended by and refraining from broadcasting the expired ephemeral authentication keys. We propose the possibility of using block-based, rather than stream-based, encryption for the symmetric encryption primitives.
• Offering provably secure models for every aspect of the algorithm which formalizes the critical security properties of mpSEQ.

We also equip mpSEQ with heartbeat to ensure in-session forward secrecy, periodical consistency check and freshness.

IV. Security Properties

Following the original proposal for the mpOTR protoocol proposed in and based on our rationales proposed in SectionIII, we give an informal description of the properties which mpSEQ 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; they are confident that they have seen the same sequence of messages.

For each of these requirements, it is necessary to formalize the above mentioned properties against an adversarial model which addresses the elements discussed in 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 is followed. This notation is common to other publication on group key exchange such as , and is adherred to for consistency.

Definition III.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 III.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 III.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.
• 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:

1. Deniable Authenticated key exchange (including a forward secrecy adversary)
2. Message origin authenticity
3. Confidentiality
4. 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 tmpSEQ protocol runs a peer-to-peer key exchange and establishes parallel deniable authentication, we use the adversarial model from 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 .

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 TestSK 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 . The adversaries of Definition VI.3 and VI.4, are able to Corrupt users after the communication of DH secrets. Therefore they can trivially break an AKE which without forward secrecy. In this sense, the resistance against forward secrecy adversary is included in AKE adversarial model.

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

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 security properties mentioned in Section IV, we break the protocol into the following sub-protocols:

1. 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.
2. Communication, where parties send authenticated confidential messages.
3. Transcript consistency verification, where parties verify that all have received and seen an identical transcript since the start of the chat session.

Our choice of sub-protocols for mpSEQ has been the use of the same sub-protocols and primitives suggested in and , except where there has been a practical or security-related reason to deviate from those recommendations.

We have completely replaced the session and signature key establishment protocol. This was done as the original choice of for this phase proved impractical in previous implementations. This choice was also motivated by the need to move to a provably secure key exchange. We have moved to elliptic curve cryptography to save on key and signature length in asymmetric primitives.

Following the conclusion of we have dropped forgeability (mandatory publication of ephemeral signature/MAC keys) and malleability. As it is argued in that the deniability of the protocol is based on deniable key exchange. While they increase the complexity of the algorithm, the above properties do not mathematically contribute to deniability. Taking this step also significantly improves the efficiency of the protocol which is a main focus for mpSEQ. In this sense, although users not participating in session are not be able to forge part of the session transcript, they can forge a whole session with false participants and a complete transcript due to the deniability of the authentication scheme.

We can ensure transcript consistency whenever the underlying transport layer guarantees the reliable delivery of the messages in the same order for all participants.

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 - 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. Subsequently, one can apply the same approach presented in 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 . The rationale for the choice is laid out as follows:

• The base design of the protocol in is the same as the base for (recommended by ). However, the protocol presented in is simpler.
• offers a peer-to-peer key exchange with no extra rounds, if needed.
• and are superior to the widely studied and its dynamic variation both in security and performance ($O(1)$ rounds).
• has been suggested by for the reason described in . We believe that the new deniable authentication approach, as it is similar to the SKEME protocol, satisfies the properties of deniability which considered crucial aside from the cooperating judge.
• Security analysis of and has found that 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.
• only needs one round of key re-agreement in the case of a participant leaving the chat, while 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 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 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 and .

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.2 Other design possibilities

During the process of designing mpSEQ we have considered, and debated, other design possibilities which we will describe in this section along side our argument in favour of the choice we have made.

VII.2a Group Key Scheme vs Broadcast Scheme

We say a group key scheme (as defined in 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.

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:

1. Chat room simulation: A group scheme simulates a normal chat room in the absence of an authentication adversary, where the participants all have the same view of who is in the chat room when they start talking. This is not the case in a broadcasting scheme as participants keep different participant lists. This is in conflict with the security assumptions of the authentication properties from the original proposal for mpSEQ.
2. 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.
3. Delayed join and leave: In a group scheme, until all participants confirm their identical view of a new participant list (due to a member joining or leaving the room), they need to assume the status quo. This might delay a new participant from joining a chat or, if no further measure is taken, enable a participant to deny join/leave for the whole group. While various mitigation methods are possible against such attacks (all summarized under the umbrella term "Denial of Service" ) they are not included in threat model considered in mpSEQ 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 VI.II.2b allows for communication with users while they are waiting for the join procedure to complete.

VII.2b Participatory vs individually independent computation of group keys

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 . In this section we consider briefly the arguments for each side and describe the rational for our choice.

VII.3 Message Authentication

As message authentication needs to be resistant to malicious insiders, following the outline of , mpSEQ signs each message using a public key signature scheme. The messages are signed with the ephemeral key of the sender. The authenticity of the origin can be verified by the public ephemeral key of the party distributed during the key exchange period.

VII.5 Transcript Ordering and Consistency

Because each message sent by each participant is signed by the ephemeral private key generated for the specific session, it is not possible for the internal or external adversary to forge a message on behalf of an uncorrupted participant.

However, if the adversary is controlling the network structure, denial or delay of service is always possible. Hence, the consistency of the transcript (meaning that all participants see the same transcript in the same order) relies on the means of transport guaranteeing reliable delivery, with a single order, to every participant. Another way of viewing this is that we are verifying the recipients of a message.

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.

mpSEQ 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 , with two major differences:

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

1. XMPP, as the main protocol considered for this design, delivers messages to all clients in the same order.
2. The mpSEQ protocol detects if the adversary has manipulated the order of the messages rather than only dropping undesirable messages
3. 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.

VII.5 Asynchronous communication and Forward Secrecy

The protocol is primarily targeted to synchronous cases, however, with some modification it can be used for asynchronous cases.

Provided that the participants are not concerned with authenticating the list of participants (it is OK if Eve impersonates Bob as long as she is unable to read Bob’s messages). Participants can communicate using their pairwise exchanged ephemeral Diffie-Hellman keys until all participants finish the second round of authentication.

As soon as a deniable handshake has been established among a set of participants any subset of them can communicate and authenticate their messages using the “session key” and their ephemeral signature key.

The protocol does not enforce explicitly a time limit on renewing the session key shares and can be used for an asynchronous high latency transport after the key establishment state.

The downside of using a session key for a long time is that a compromised session key will reveal all past communication during that session. This does not pose an imminent threat when the life span of a chat is short. However, in the context of asynchronous high latency transport, it is a more serious concern.

The protocol requires the participants to pre-emptively update their ephemeral signature/shares and propagate them as part of the messages they are already sending. Subsequently, they also update their key share with their neighbours as soon as the neighbours also propagate their new ephemeral signature keys.

As the assumption of having a continuous heartbeat might not be realistic in various asynchronous cases, implementations can assume specific deadlines for dropping users who did not communicate their new keys or shares.

VIII. mpSEQ Protocol: Step by Step

In this section we present the mpSEQ 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 . Joining the room is a variation of the two-round mBD+P protocol presented in where the authentication step has been made deniable. Leaving the room is the one-round mBD+S from .

VIII.1 Schematic view of the key exchange

Although computing a unified session key for all participant is possible, the protocol will compute n different keys each being used to decrypt the text received from the corresponding participant. In other words, Participant $U_{i}$ uses key $sk_{{i,i}}$ to encrypt data. Formally we consider a tuple of $sk_{i}^{S}:=(sk_{{i,1}}^{S},sk_{{i,2}}^{S},...,sk_{{i,n}}^{S})$ as a session key. This measure has been taken to facilitate the transition to a broadcast use-case where the protocol does not promise same $plist$ for all participants and therefore, it is conceptually impossible to compute a unique key. For more information please see Section VII2.2b.

For the high level design of the protocol we do not specify the primitives for GroupEnc and GroupDec used in steps 2.4 and -.3. However, we disucss their property and we present some canadidates.

For simplicity, group operation is written multiplicatively, although it is actually an elliptic curve points operation traditionally represented by addition. Where ever our design deviates from , it is marked by yellow. Pink means we have abstracted out the step mentioned in as an independent primitive:

Algorithm 1

Rnd	Description	Pseudo-code	Type
1	Generate ephemeral DH private key	$x_{i}\leftarrow [0,order(g)]$	Computation
1.1	Generate DH key for BD, Triple DH and Signature	$y_{i}\leftarrow g^{{x_{i}}}$	Computation
1.2	Broadcast User identity and the DH key	$(U_{i},y_{i})$	Broadcast
2	Compute Session Id	$sid_{i}\leftarrow (U_{1}|y_{1}|\dots |U_{n}|y_{n})$	Receive
2.1	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
2.2	Generate key confirmations	$kc_{i}\leftarrow (H(k_{{i,1}},U_{1}),\dots ,H(k_{{i,n}},U_{n}))$	Broadcast
2.3	Generate secret shares	$z'_{i}:=\leftarrow (H(k_{{i,j}},sid_{i})forj\in \{1,\dots ,n\})$	Computation
2.4	Encrypt shares	$z_{i}\leftarrow GroupEnc(k_{{i_{j}}}forj\in \{1,\dots ,n\},z')$	Computation
2.3	Sign identity, shares	$\sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)$	Computation
2.4	Broadcast encrypted shares and confirmation	$(U_{i},z_{i},\sigma _{i},$$kc_{i}$)	Broadcast
-	Check validity of key confirmation	$kc_{k}[j]{\stackrel {?}{=}}kc_{j}[k]\;\forall j\neq k$	Receive
	Check signatures	$Verify_{{y_{i}}}(\sigma _{j})\;\forall j\neq i$	Computation
	Check Session Ids	$sid_{j}{\stackrel {?}{=}}sid_{i}\;\forall j\neq i$	Computation
	Generate session key	$sk_{{i,j}}\leftarrow H(GroupDec(k_{{i,j}},z_{j}\;\forall j),sid_{i},U_{j})\;\forall j\neq i$	Computation

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

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 (H(k_{{i,1}},U_{1}),\dots ,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 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
Generate secret shares	$z'_{i}:=\leftarrow (H(k_{{i,j}},sid_{i})forj\in \{1,\dots ,n\})$	Computation
Encrypt shares	$z_{i}\leftarrow GroupEnc(k_{{i_{j}}}forj\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	${\textrm {Receive}}(U_{j}|z_{j},\sigma _{1},kc_{{ji}}){\textrm {for}}U_{j}{\textrm {unauthenticated}}$	Receive
Check validity of key confirmation of unauthenticated users	$kc_{i}[j]{\stackrel {?}{=}}H(k_{{j,i}},U_{j}){\textrm {for}}U_{j}{\textrm {unauthenticated}}$	Computation
Check signatures	$Verify_{{y_{i}}}(\sigma _{j}){\textrm {for}}j\in \{1,\dots ,n\}$	Computation
Check Session Ids	$sid_{j}{\stackrel {?}{=}}sid_{i}\;\forall j\neq i$	Computation
Generate session key	$sk_{{i,j}}\leftarrow H(GroupDec(k_{{i,j}},z_{j}\;\forall j),sid_{i},U_{j})\;\forall j\neq i$	Computation
Initiate the TranscriptChain	$TrascriptChain_{i}^{S}[0]\leftarrow (sk_{i}^{S},sid_{i})$	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 mpSEQ, both for the room view (plist) and for the transcript, are reached through group agreement. However, there are times when group agreement may be hard or impossible to reach either due to latency in a single participant's connection or due to a single participant broadcasting incorrect confirmation data (such as wrong plist, sid, key share, etc).

We offer an extension to the mpSEQ protocol to tackle this problem during the joining process. When a new participant joins the room, they send their DH key shares to the other participants. The other participants send their ephemeral key in return. They then send their key confirmation and key share. If this extension is to be considered, as soon as each user receives a key confirmation from another user, who is not currently part of the session, mpSEQ displays a message highlighting the fact that although the user is not part of the session the conversation is being shared with them (through P2P encryption using the key derived from DH Key). The protocol, however, does not honour their input in the consistency check until a new session including the new user is set up. Each client can decide whether to disable this option.

The user remains in the list of those not part of the current session, but receives the session messages until a new session is set up. Similarly, when a user receives a message from a user who is not part of the session, mpSEQ will decrypt the message and display it with a disclaimer that the user is not yet part of the session and that some participants may not receive the same message.

In this model, a room is a forwardly secure authenticated communication channel while a session is a subset of the room, which additionally offers a consistent view of the room and consistent messages among participants.

Leave

Leaving a chatroom involves a message from a leaving party indicating its intention to leave which, as with all other messages, contains the hash of TranscriptChain and one procedure for those who are staying in the chatroom (Procedure Farewell) which is described in Table mpSEQ#Leave.

Farewell

Run by exiting user.

Algorithm 6

Description	Pseudo-code	Type
Send farewell message	Failed to parse (lexing error): Send("Leaving!")	Broadcast
Wait to receive hashes of TranscriptChain	$Receive()$	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 mpSEQ#Leave 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.

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 need inorder to enforce in-session forward secrecy. The metadata flag indicates if the message being sent only contains meta data (e.g. heartbeat) or actual user communication.

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

Encrypted messages include a "hash of TranscriptChain" of their parent as "additional authenticated data".

$(H(parent(m)),H(TransciptChain[parent(m)-1])))$

Note that we defined $H(parent(m))$ rather than $H(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.

Algorithm 8

Description	Pseudo-code	Type
Generate new DH Key or new secret share if needed and append	$m\leftarrow (sid,s,m)$	Computation
Append the hash of the TranscriptChain, up to the parent of the message being sent	$m\leftarrow (m,(H(parent(m)),H(TransciptChain_{i}^{S}[parent(m)-1]),parent\_id(m)))$	Computation
Sign the message	$\sigma \leftarrow Sign_{{x_{i}}}(m)$	Computation
Encrypt	$e\leftarrow Enc_{{k_{{sid}}}}(m)$	Computation
Broadcast the message	$(sid_{i},e,\sigma )$	Broadcast

Receive

Algorithm 9

Description	Pseudo-code	Type
Check signature	$Verify(m,\sigma )$	Computation
Update TranscriptChain	$Insert(TranscriptChain^{S},m)$	Computation
decrypt message	$sid_{{rec}},s,m,h,parent\_id\leftarrow Dec_{k}(m)$	Computation
Verify session id and transcript consistency, issue a warning in case of failure	$sid_{i}{\stackrel {?}{=}}sid_{{rec}}\;{\textrm {and}}\;h{\stackrel {?}{=}}(H(parent(m)),TranscriptChain_{i}^{S}[parent(m)-1])$	Computation
Update sender key or share key	$y_{j}\leftarrow s\;{\textrm {or}}\;z_{{j}}\leftarrow s$	Computation
If all users' share are received, generate session key	$sk_{{i,j}}\leftarrow H(GroupDec(k_{{i,j}},z_{j}\;\forall j),sid_{i},U_{j})\;\forall j\neq i$	Computation
return m	m

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($	Computation
Compare hash of TranscriptChain_j[p] with own value of it, issue a warning if it fails.	$H(TranscriptChain_{j}^{S}[p])==H(TranscriptChain_{i}^{S}[p])$ for all $U_{k}\in plist_{i}^{S}$	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

Heartbeat

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.

• 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$ and request a call for leave procedure to exclude those users from the 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.

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

IX.3 Message Encryption

We are using AES-256 in counter mode with a shared group key for message encryption, as suggested by the original OTR protocol.

IX.4 GroupEnc and GroupDec Functions

The GroupEnc and GroupDec functions are primitives which 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:

1. 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}}$.
2. $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}}forj\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}}forj\in \{1,...,n\},z'_{i})$.

Here we mention two examples of such functions:

• 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}}$

mpSEQ uses the modification of the primitive suggested in 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. Conclusion

In this document, we presented the final draft of mpSEQ. We hope by receiving public comment on this draft we are able to improve the design. We have referenced the adversarial models which the protocol is supposed to resist. Meanwhile we are working on an implementation of mpSEQ. We will publish a sequel document which high light the implementation details as well as proof of resistance to the adversarial model presented here.

XI. References

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

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.

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.

Bonneau, Joseph, and Andrew Morrison. “Finite-State Security Analysis of OTR Version 2.” http://www.jbonneau.com/doc/BM06-OTR_v2_analysis.pdf

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: ACM. doi:10.1145/1029179.1029200. http://doi.acm.org/10.1145/1029179.1029200.

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. http://dx.doi.org/10.1007/978-3-540-70500-0_6.

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. doi:10.1007/3-540-45682-1_18.

Emmanuel Bresson, Olivier Chevassut, David Pointcheval, and Jean-Jacques Quisquater. 2001. “Provably Authenticated Group Diffie-Hellman Key Exchange.” In Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS ’01), edited by Mike Reiter, 255–264. Philadelphia, Pennsylvania: ACM Press. doi:10.1145/501983.502018.

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/

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. doi:10.1145/1653662.1653705. http://doi.acm.org/10.1145/1653662.1653705.

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

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

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

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.

Hyun-Jeong Kim, Su-Mi Lee, and Dong Hoon Lee. 2004. “Constant-Round Authenticated Group Key Exchange for Dynamic Groups.” In ASIACRYPT, 245–259. https://www.iacr.org/archive/asiacrypt2004/33290243/33290243.pdf

Mark Manulis. 2006. “Security-Focused Survey on Group Key Exchange Protocols.” IACR Cryptology ePrint Archive 2006: 395. http://eprint.iacr.org/2006/395.

^[Per] Trevor Perrin. “Axolotl Ratchet.” https://github.com/trevp/axolotl/wiki

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

Whisper Systems. 2014. “TextSecure ProtocolV2.” Accessed March 2. https://github.com/WhisperSystems/TextSecure/wiki/ProtocolV2.