Re: [MLS] Malicious user segmenting the group

[Raphael Robert <[e-mail]>]

I’d like to second that this is an active issue. I think there are two kinds of attacks an ill-intentioned member could do (for an Update HS):

 a) Send the wrong public keys
 b) KEM values that not part of a valid hash chain

In both cases, not everyone can detect these attacks. Members can only detect malformed values between the intersection node and the root. The intersection node is the node where the direct paths of the updating node and the member’s leaf node intersect. Any malformed value that are below the intersection cannot be verified.

This can lead to different reactions from members:

 1. Some will detect that values are malformed, discard the HS message altogether and keep the current epoch secret
 2. Some will not detect the attack and hash up from a faulty value to derive a new root secret (attack b)
 3. Some will not detect the attack and hash up from a correct value, but will later KEM to a faulty public key (attack a)

In all cases this leads to partition with no obvious ways of reconciliation. For case 1 members will know who the culprit was, which is marginally better than case 2 and 3, where they don’t know. For case 1 the attack could be surfaced to the user as some sort of warning, so that users can manually resolve the situation by ultimately removing the attacker from the group.
Case 2 can be addressed with the key confirmation in [1], because members will not derive the same root secret and fail on the HMAC verification. They will thus also know who the culprit is.

It would be interesting to see if efficient ZKPs exist, so that clients can always come to the same conclusion on whether or not a message is valid.
There might also be another use case, where the verification could be done by the server (assuming unencrypted handshake messages). This would allow the server to discard faulty messages right away without forwarding them to clients. It would also potentially address the bottleneck situation we currently have with Welcome messages. In such a scenario the server could cache the public keys of the tree nodes and make them available to newcomers. This is obviously a complex subject with some intricacies that should be discussed separately, but since this is yet another reason to have ZKPs to verify handshake messages, I wanted to mention it here.

Finally, I wanted to mention that concept of ACK/ NACK messages adds a notion of interaction and inter-client consensus that hasn’t existed so far. Since there is no guarantee that clients who are theoretically able to detect a faulty message will ever come online to warn others, the group state could advance for quite some time and lead to partition.


[1] https://github.com/mlswg/mls-protocol/pull/72

> On 22 Oct 2018, at 20:10, Richard Barnes <[e-mail]> wrote:
> 
> Hi Jon,
> 
> This is definitely an active issue.  See my message earlier today about authentication / key confirmation.
> 
> There have been some discussions of ZKPs for this, but AFAIK, no workable proposal has emerged.  The problem is that what you want to prove is that a sequence of keys are the result of transforming a chain of hashes from hash outputs to key pairs -- if you want to do a ZKP with a general hash function, the ZKP is very expensive, and if you adapt the hash function to have nicer proof properties, you lose some of the cryptographic properties you would want.
> 
> My current thinking is that we should probably try to address this at the protocol level.  In some of the pre-BoF discussions, we had talked about doing some specification of ACK / NACK messages.  Now that at least some endpoints can recognize a bad message, it seems like we could define a NACK that says "that handshake message was invalid" and basically let endpoints veto invalid messages.
> 
> If someone wants to come up with a concrete proposal, I would love to discuss further.
> 
> --Richard
> 
> On Mon, Oct 22, 2018 at 1:37 PM Jon Toohill <jtoohill=[e-mail] <mailto:[e-mail]>> wrote:
> Hey MLS folks,
> 
> I'm still skimming through the mailing list archives to get up to speed, so apologies if this has already been discussed & solved. I saw the following note in a recent version of the protocol draft:
> 
> [[ OPEN ISSUE: It is not possible for the recipient of a handshake message to verify that ratchet tree information in the message is accurate, because each node can only compute the secret and private key for nodes in its direct path. This creates the possibility that a malicious participant could cause a denial of service by sending a handshake message with invalid values for public keys in the ratchet tree. ]]
> 
> It seems like this could be solved by having the handshake message sender prove in zero knowledge (i.e. without revealing their secret or the parent secret) that they derived the parent public key correctly. ZK-SNARKs are one way of doing that, but my admittedly weak understanding is that generating proofs might be too computationally expensive for mobile devices. Does this seem like a worthwhile direction to investigate? Does anyone know of a more efficient construction that could be used in MLS?
> 
> -Jon Toohill
> _______________________________________________
> MLS mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls