The Messaging Layer Security (MLS) protocol currently developed by the Internet Engineering Task Force (IETF) aims at providing a secure group messaging solution. MLS aims for end-to-end security, including Forward Secrecy and Post Compromise Secrecy, properties well studied for one-to-one protocols. It proposes a tree-based regular asynchronous update of the group secrets, where a single user can alone perform a complete update. A main drawback is that a malicious user can create a denial of service attack by sending invalid update information.

In this work, we propose a solution to prevent this kind of attacks, giving a checkpoint role to the server that transmits the messages. In our solution, the user sends to the server a proof that the update has been computed correctly, without revealing any information about this update. We use a Zero-Knowledge (ZK) protocol together with verifiable encryption as building blocks. As a main contribution, we provide two different ZK protocols to prove knowledge of the input of a pseudo random function implemented as a circuit, given an algebraic commitment of the output and the input.

Authors and Affiliations

1. DGA Maîtrise de l’information, Bruz, France

   Julien Devigne & Céline Duguey

2. Irisa, Rennes, France

   Julien Devigne, Céline Duguey & Pierre-Alain Fouque

3. Univ Rennes1, CNRS, Rennes, France

   Pierre-Alain Fouque

Corresponding author

Correspondence toCéline Duguey.

Editors and Affiliations

1. Purdue University, West Lafayette, IN, USA

   Elisa Bertino

2. National Research Center for Applied Cybersecurity ATHENE, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

   Haya Shulman

3. National Research Center for Applied Cybersecurity ATHENE, Technische Universität Darmstadt, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

   Michael Waidner

A Key Size and Group Orders in MLS Updates

In [7], several suitable cipher suites are described. We focus on one of them for a practical example, for a 128-bit security level. This suite uses X25519 for ECDH computation and SHA256 as a hash function (and base function for HKDF implementation). Following [24], the private keysk is obtained from a 256-bit string of secure random data\((sk[0], sk[1],\dots , sk[255])\) by applying the following transform:\( sk[0] \& =248\),\( sk[31] \& = 127\) and\(sk[31] |=64\). One obtains, when interpreted as an integer value in little endian, a scalar of the form\(2^{254}+8\cdot \ell , \ell \in \llbracket 0;2^{251}-1\rrbracket \). We design by\(\mathsf {deriveSK}\) the application of\(\mathsf {SHA256}\) followed by the above transformation such that for any 32-byte sequence of random data X,\(\mathsf {deriveSK(X)}\) is a valid secret key for X25519. This encoding can be integrated in the circuit computing the last derivation. The public key is obtained by multiplying the secret key by the base point of the curve: given a 32-byte secretX,\(\mathsf {DeriveKeyPair}(X) = (\mathsf {deriveSK}(X), \mathsf {deriveSK}(X)P)\). We adopt this notation independently from the curve targeted.

Group Order and Commitments. In our proofs, we consider commitments and discrete logarithm proofs in cyclic groups of orderq, and circuits input and output that naturally lie in\(\mathsf {F}_q\). This may not be the case. Considering X25519 key derivation derived above, a new user’s secret\(ps_B'\) is a random element in\(\{0,1\}^{256}\), which, when interpreted as an integer, can be larger thanq. As explained in [6], it is possible to consider\(ps_B' \mod q\) for the commitment and to include to a modular computation in the circuit. Ifq is close enough to\(2^{256}\) then it is a simple comparison and subtraction. This requires around 2 000 gates, which is negligible compared to our circuit size. Another solution is to directly sample\(ps_B'\) in\(\mathsf {F}_q\). This can be done by rejection sampling or as follow: sampleX sufficiently big compared to\(\log _2(q)\) (\(\log _2(X)> \log _2(q)+64\) as advised by the NIST for instance), then simply considering\(X \mod q\) can be done with a negligible bias. For all the intermediate values in the tree, the first method can be applied. The last step is the commitment of the secret key\(sk = \mathsf {Encode}(X)\). For this element, we directly consider the encoding provided with the curve. The commitment\(C_{sk}\) ofsk in a group of orderq will result in the same implicit reduction moduloq than the computation of the public key. Then we can produce an AND ZK proof that the value committed to in\(C_{sk}\) is the discrete log of thepk:\(PK\{sk: C_{sk} = skP+rQ \wedge pk = skP\}\).

B Security of Our Zero-Knowledge Protocols

We present a sketch of proof for the security of\(\mathtt {CopraZK}\) given in Theorem2. It is settled on two properties for the function familyf. Firstly, we need its dual function\(\tilde{f}\) to be correlation intractable with respect to the family of relations\(\mathcal {R}_{a,b}:\{x,y: y=ax+b\}\) fora, b random values. Correlation intractability was introduced in [15] and says that, for any relation in the family\(\mathcal {R}_{a,b}\), for any random keyx, an adversary has a negligible probability to find an inputm such that (m,f(x, m)) satisfies the relation. Secondly, we need to be sure that the tag does not leak information on the key. We define a general linear input deviation resistant PRF (\(\mathsf {glider}\text {-}\mathsf {PRF}\)) as follows:

Definition 1

(\(\mathsf {glider}\text {-}\mathsf {PRF}\)security). A function family\(f \in \mathsf {FF}(\mathcal {K},\mathcal {D},\mathcal {R})\) (with appropriate domain and range) is said to be a\(\mathsf {glider}\text {-}\mathsf {PRF}\) if for all PPT adversary\(\mathcal {A}\), and a random, there exists a negligible function\(\mathsf {negl}\) such that:

As we use Fiat-Shamir to get an non interactive protocol, our proof is settled in the Random Oracle Model (ROM), which would satisfy our hypothesis. However, it seems contradictory to idealize as a random oracle the PRFf that is concretely described as a circuit in the ZKBoo part of the protocol. Hence, the ROM hypothesis only applies to the hash function\(\mathsf {h}\) that generates the challenge and the correlation intractability and\(\mathsf {glider}\text {-}\mathsf {PRF}\) properties provide a way to formalize a security proof when only some properties of the random oracle are needed. The correctness of the protocol follows by inspection.

3-Special Soundness. From the 2-special soundness of the Sigma protocol\(\varPi \), one extract\(\tilde{x},\tilde{y}, \tilde{r_x}, \tilde{r_y}\) such that\(C_x = \tilde{x}P+\tilde{r_x}Q, C_y = \tilde{y}P + \tilde{r_y}Q\) and\(t = \alpha \tilde{x} + \tilde{y}\). From the 3-special soundness of ZKBoo, one extracts\(x'\) such that\(t=f(x',m)+\alpha x'\), wheret is a fixed value, the same as the one for the proof\(\varPi \). Correlation intractability of\(\tilde{f}\) ensures that\(x' \ne \tilde{x}\) happens with negligible probability. We note that the correlation intractability of\(\tilde{f}\) requires the input off to be randomized. In MLS, this supposes considering a random value (for instance the hash of the tree view) instead of the constant 0.

Zero Knowledge. We build a simulator\(\mathcal {S}im\) as follows:\(\mathcal {S}im\) sample a random value. Then he calls the Simulator of ZKBoo,\(\mathcal {S}im_{ZKBoo}\), as a subroutine and obtains a transcript\((a_{ZKBoo, e, z_{ZKBoo}})\). Then he calls the simulator for the Sigma protocol\(\varPi \),\(\mathcal {S}im_\varPi \), as a second subroutine, on the challengee and obtains a second transcript\((a_{\varPi }, e, z_{\varPi })\) (as\(\mathcal {S}im_\varPi \) shall work for any challenge). Iff is\(\mathsf {glider}\text {-}\mathsf {PRF}\)-secure, then sampling a randomt is indistinguishable from the real distribution oft and finally, the output distribution of\(\mathcal {S}im\) is indistinguishable from the real execution output. In the context of MLS, the tagt must be accessible to the server only. A user who would receive its valid update and access the tag could compute the secret of its child, which he should not.

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics