Re: [MLS] Idea for Issue #33

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.

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=40cloudflare.com@dmarc.ietf.org> 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
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls