Re: [MLS] Idea for Issue #33

[Nick Sullivan <[e-mail]>]

On Wed, Jan 23, 2019 at 7:02 PM Yevgeniy Dodis <[e-mail]> 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=[e-mail]> 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.
> >
> > 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
> >
> >
> > _______________________________________________
> > MLS mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/mls
>