Subject: [MLS] Idea for Issue #33

From: Nick Sullivan <[email-masked]>
Date: Wed, 23 Jan 2019 17:34:02 -0800

Hello all,

Relaying some ideas that I posted in the Github issue that allow a
participant that was maliciously removed from the group by a bad update
message to publicly prove that it was given an inconsistent update. This is
an idea based on lightweight zero-knowledge proofs.

https://github.com/mlswg/mls-protocol/issues/21

Recall the following from ECIES:
Say that you are encrypting a ciphertext *X* to a user with private key *a*,
public key *A* (= aP) and elliptic curve base point *P*. The ECIES
ciphertext is the pair *(rP, c)* where *r* is a randomly-chosen scalar and
*c* is the encryption of X with a key derived from *k*=KDF(rA)=KDF(raP).

The key to this mechanism is revealing enough to prove to a third party
that an update received by the user is decrypted to an inconsistent X than
an update received by another participant, but without revealing the
private key *a *(which would compromise the confidentiality of previous
messages).

Proposed modifications of the protocol:
1) Add a mechanism that allows a party with access to a supposed secret
value of a node to validate the consistency of the chain of hashed derived
from that secret. This could be implemented by creating a public value that
consists of a KDF of the secret value with a known public value for every
node that is being updated. To check a secret value, the validating party
needs to compute the KDF for every node up the tree to the root and compare
with the published values.

The KDF acts as sort of a public integrity hash of to the node's secret
value.

2) Add a Schnorr NIZK of knowledge (RFC 8235) of the random value r with
every ECIES ciphertext. This proves that the r used in the ECIES encryption
is known to the updater and rP is not trivially derived from some other
previously sent r'P.

For one participant to prove that they were given an update message that
did not include the correct node secret, that participant can reveal the
following:
arP, DLEQ(arP:rP :: P:aP)

Where a is the node's private key, and DLEQ is a discrete log equivalence
proof that shows that arP is rP multiplied by the private key *a* of the
user.

So in summary, we would add:
- Proof of knowledge of the randomness used in ECIES
- Public KDF of each node's secret value
and then a member could prove to an auditor that it was given the wrong
secret by revealing:
- an intermediate calculation of the ECIES decryption, a DLEQ proof that
the right key was used

I'm eager for this proposal to have some holes shot in it.

Nick

---

From: Richard Barnes <[email-masked]>
Date: Thu, 24 Jan 2019 09:22:21 -0500

Hey Nick,

If I'm understanding this correctly, I'm not sure it adds much new.

W.r.t (1), the public keys in the path already provide this function, since
they're a public value derived from the node's secret.  Similarly, w.r.t.
(2), the public key rP commits to the secret value r.

So if the desire is to allow a third party to verify that an update is bad,
and we're OK revealing one of the (previously) encrypted node secrets, we
may have the machinery we need.  The reporter can reveal the ECIES secret
value r, and the verifier can first check that r matches the
ECIESCiphertext, then decrypt the ciphertext and check the rest of the path.

It seems like the only way you could do better than this is if you could do
reporting without revealing any node secrets (even the inconsistent ones).
But that seems appreciably more difficult.

--Richard

On Wed, Jan 23, 2019 at 8:34 PM Nick Sullivan <nick=
[email-masked]> wrote:

> <https://github..com/mlswg/mls-protocol/issues/21>
>
> Say that you are encrypting a ciphertext *X* to a user with private key
> *a*, public key *A* (= aP) and elliptic curve base point *P*. The ECIES
> ciphertext is the pair *(rP, c)* where *r* is a randomly-chosen scalar
> and *c* is the encryption of X with a key derived from *k*
> =KDF(rA)=KDF(raP).
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Nick Sullivan <[email-masked]>
Date: Thu, 24 Jan 2019 08:58:25 -0800

Hi Richard,

You’re right, the KDF part is not necessary, the verifier can just compare
the public key. Scratch that part.

However, revealing r is not an option for the participant who was given the
wrong key share, only the participant who created the bad key share. They
may be offline or claim to have deleted it for forward secrecy reasons.
This is why you need the zero-knowledge machinery.

Nick
On Thu, Jan 24, 2019 at 6:22 AM Richard Barnes <[email-masked]> wrote:

> W.r.t (1), the public keys in the path already provide this function,
> since they're a public value derived from the node's secret.  Similarly,
> w.r.t. (2), the public key rP commits to the secret value r.
>
> So if the desire is to allow a third party to verify that an update is
> bad, and we're OK revealing one of the (previously) encrypted node secrets,
> we may have the machinery we need.  The reporter can reveal the ECIES
> secret value r, and the verifier can first check that r matches the
> It seems like the only way you could do better than this is if you could
> do reporting without revealing any node secrets (even the inconsistent
> ones).  But that seems appreciably more difficult.
>
> --Richard
>
>
>> <https://github...com/mlswg/mls-protocol/issues/21>
>>

---

From: Nick Sullivan <[email-masked]>
Date: Thu, 24 Jan 2019 09:13:11 -0800

On Wed, Jan 23, 2019 at 7:02 PM Yevgeniy Dodis <[email-masked]> wrote:

> Hi Nick.
>
> As I told Jon and you in Mountain View, this is a really nice idea.
>
> A couple of concerns regarding the specific proof of DLEQ by the
> receiver. Effectively, a malicious sender
> can send a ciphertext of the form <Q, garbage> for any value Q of its
> choice (not necessarily the one where he
> knows r such that Q = rP, and the receiver will "complain" by opening
> the value aQ. In crypto terms, this corresponds
> to CDH (computational diffie-hellman) oracle: given (P, P' = aP) fixed
> and any value Q, return aQ.
>
> There is an old paper of Maurer and Wolf which shows CDH and discrete
> log (DL) are polynomially equivalent in certain groups:
> ftp://ftp.inf.ethz.ch/pub/crypto/publications/MauWol99b.pdf
> I think standard groups we use do not fall there, but I did not check
> the paper in more detail.
>
> Of more immediate concern, this opens the following simple chosen
> ciphertext attack. Malicious sender wants
> to decrypt some old valid ciphertext (C=rP, D). He wants to obtain D /
> xC, so suffices to compute xC.
> He generates random r', and submits ciphertext (C' = r' C, garbage).
> Receiver will complain by opening
> x C' =  r' (xC), from which can raise to 1/r' to recover xC, and hence
> D/xC.
>
> Is this chosen ciphertext attack possible? What might save us is that
> the only people who encrypt to node with public
> key aP, are the nodes in the subtree rooted by the sibling of a, since
> only then a is on the co-path. And these nodes anyway should be
> allowed to decrypt all ciphertexts encrypted using aP to the subtree
> rooted at a. But I feel we might concoct a scenario where this attack
> could be relevant. Not sure now, just pointing out this concern.

The hope was that by requiring the sender to create a Schnorr NIZK that
they know r for rP that you couldn’t construct a Q for which revealing aQ
does not reveal anything about a previous Q (=r’P without knowing r’). Is
it really possible to do this without solving the DLP for Q with respect to
P?

I guess if the participant sending the bad update was the one to send r’
previously then they could construct this proof (for r’+1, for example) and
force the target to reveal a previous group state. This is one of the
downsides of TreeKEM’s non-contributiveness, I guess.

>
>
> In general, one malicious insiders are allowed, my feeling is that we
> need some kind of CCA protection, and basic ElGamal will not be
> secure.
>
> Still, I love the idea, and hope we can make it work...
> Yevgeniy
>
>
>
>
>
> On Wed, Jan 23, 2019 at 8:34 PM Nick Sullivan
> <nick=[email-masked]> wrote:
> >
> > Hello all,
> >
> > Say that you are encrypting a ciphertext X to a user with private key a,
> public key A (= aP) and elliptic curve base point P. The ECIES ciphertext
> is the pair (rP, c) where r is a randomly-chosen scalar and c is the
> encryption of X with a key derived from k=KDF(rA)=KDF(raP).
> >
> private key a (which would compromise the confidentiality of previous
> messages).
> >
> > Where a is the node's private key, and DLEQ is a discrete log
> equivalence proof that shows that arP is rP multiplied by the private key a
> of the user.
> >
> >

---

From: Yevgeniy Dodis <[email-masked]>
Date: Wed, 23 Jan 2019 22:01:47 -0500

Hi Nick.

x C' =  r' (xC), from which can raise to 1/r' to recover xC, and hence D/xC.

On Wed, Jan 23, 2019 at 8:34 PM Nick Sullivan
<nick=[email-masked]> wrote:
>
> Hello all,
>
> Relaying some ideas that I posted in the Github issue that allow a participant that was maliciously removed from the group by a bad update message to publicly prove that it was given an inconsistent update. This is an idea based on lightweight zero-knowledge proofs.
>
> Say that you are encrypting a ciphertext X to a user with private key a, public key A (= aP) and elliptic curve base point P. The ECIES ciphertext is the pair (rP, c) where r is a randomly-chosen scalar and c is the encryption of X with a key derived from k=KDF(rA)=KDF(raP).
>
> The key to this mechanism is revealing enough to prove to a third party that an update received by the user is decrypted to an inconsistent X than an update received by another participant, but without revealing the private key a (which would compromise the confidentiality of previous messages).
>
> 1) Add a mechanism that allows a party with access to a supposed secret value of a node to validate the consistency of the chain of hashed derived from that secret. This could be implemented by creating a public value that consists of a KDF of the secret value with a known public value for every node that is being updated. To check a secret value, the validating party needs to compute the KDF for every node up the tree to the root and compare with the published values.
>
> The KDF acts as sort of a public integrity hash of to the node's secret value.
>
> 2) Add a Schnorr NIZK of knowledge (RFC 8235) of the random value r with every ECIES ciphertext. This proves that the r used in the ECIES encryption is known to the updater and rP is not trivially derived from some other previously sent r'P.
>
> For one participant to prove that they were given an update message that did not include the correct node secret, that participant can reveal the following:
> Where a is the node's private key, and DLEQ is a discrete log equivalence proof that shows that arP is rP multiplied by the private key a of the user.
>
>
> and then a member could prove to an auditor that it was given the wrong secret by revealing:
> - an intermediate calculation of the ECIES decryption, a DLEQ proof that the right key was used
>
>