[MLS] Potential issues with "add-only" commits in young groups

Cornelissen Eric <eric.cornelissen@aalto.fi> Wed, 05 August 2020 13:27 UTC

Return-Path: <eric.cornelissen@aalto.fi>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id CDA4E3A0143 for <mls@ietfa.amsl.com>; Wed, 5 Aug 2020 06:27:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=aalto.fi
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id JtgwUi8Te8UU for <mls@ietfa.amsl.com>; Wed, 5 Aug 2020 06:27:19 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (smtp-out-01.aalto.fi []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B31D63A077E for <mls@ietf.org>; Wed, 5 Aug 2020 06:27:15 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (localhost.localdomain []) by localhost (Email Security Appliance) with SMTP id 501B41158B5_F2AB3AFB for <mls@ietf.org>; Wed, 5 Aug 2020 13:27:11 +0000 (GMT)
Received: from exng3.org.aalto.fi (exng3.org.aalto.fi []) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (Client CN "exng3.org.aalto.fi", Issuer "org.aalto.fi RootCA" (not verified)) by smtp-out-01.aalto.fi (Sophos Email Appliance) with ESMTPS id 899141158B3_F2AB3AEF for <mls@ietf.org>; Wed, 5 Aug 2020 13:27:10 +0000 (GMT)
Received: from exng4.org.aalto.fi ( by exng3.org.aalto.fi ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1979.3; Wed, 5 Aug 2020 16:27:10 +0300
Received: from exng4.org.aalto.fi ([fe80::4047:1ae:cfdf:c1a8]) by exng4.org.aalto.fi ([fe80::4047:1ae:cfdf:c1a8%18]) with mapi id 15.01.1979.003; Wed, 5 Aug 2020 16:27:10 +0300
From: Cornelissen Eric <eric.cornelissen@aalto.fi>
To: "mls@ietf.org" <mls@ietf.org>
Thread-Topic: Potential issues with "add-only" commits in young groups
Thread-Index: AQHWaysOYLkshmHVlE2/Q1XWhkDVcg==
Date: Wed, 5 Aug 2020 13:27:10 +0000
Message-ID: <e0d6ff151c464d9d9cf49af054df6cdf@aalto.fi>
Accept-Language: en-US, fi-FI
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/mixed; boundary="_005_e0d6ff151c464d9d9cf49af054df6cdfaaltofi_"
MIME-Version: 1.0
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aalto.fi; h=from:to:subject:date:message-id:content-type:mime-version; s=its18; bh=wW2vfpILo8Pm02V/n8oLfFQDZQTzcCdm4oyreZ00uE4=; b=cjl09kb5e+An0MtOFBMrDIhoO1c6ruOS1WlIbiE9Ks5HItvFyxs4EiBwuVlLClKIYDzlvH28NA5zj48sFKzbHTU8ehVrXAQlSMaTv1IqWuwaYpfE8kvCuKIzW16/Klb4fMzoxtYpTiFq8K7yTrIHNMZ33Wn85epeiIPLbSTsBvoSYvmMFP+1HpVMtew7HAN4HKAdyCHXgE+TrIcDkWc/qvWwsCqlE9PuTi8uGQedIGGi09gMXMJykt6jU02yT2FPZMPBNP6KELtEo32wlOXaC7C5OgkZxAgwt+NlxhipCk0A0CmYJbiMKUdsUGHNKhV52V1vVsy2p7lfoT1I2+QuQg==
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/LtfodwWfdl36Y1FIbRAXHXDmCeU>
Subject: [MLS] Potential issues with "add-only" commits in young groups
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 Aug 2020 13:27:22 -0000

Hi All,

Quick introduction: my name is Eric, I have submitted a few issues in the MLS GitHub and I did an analysis of MLS for my Master's thesis last academic year, now I'm doing a research project related to MLS with C. Bruzska.

During this project I found a potential issues with "add-only" commits if used in the early lifetime of a group. I found two particular issues that I think are most important to look at and which I will describe both here.

Note 1: Neither of the issues I describe hold when a PSK is used, hence I will only consider scenarios where PSKs are not used.

Note 2: In both attacks the attacker must record the (encrypted) Welcome message(s) send out for a group (i.e. I'm assuming a network adversary).

Note 3: I use "add-only" commit to denote an commit that does not populate the path value of a commit and "full" commit to denote a commit that does populate the path vale of a commit. This, I suppose, deviates slightly from the draft.

Note 4: I attached diagrams explaining the attacks, I hope they are understandable :)

  1.  When using an "add-only" commit for the first commit (see attachment 01.jpg for a diagram)

The first issue is w.r.t. using an "add-only" commit as the very first commit of a new group. To the best of my knowledge this would result in the input to the key schedule being to two all-zero vectors. Namely, the init_secret for the first commit is always the all-zero vector and the commit_secret will be an al-zero vector because an "add-only" commit was used.

Now, this would allow ANYONE to derive the joiner_secret and welcome_secret for the first commit. With the welcome_secret we can decrypt the Welcome message for the user(s) being added to the group. From the Welcome message we can construct the GroupContext that is used in the key schedule (GroupContext_[n] is a subset of the GroupInfo in the Welcome message).

With all this information ANYONE can compute all of the keys produced by the key schedule for the first epoch and read any communication that happens in this epoch. Furthermore, if another "add-only" commit is used the input to the key schedule for the next epoch is also known to the attacker(!) as commit_secret will again be an al-zero vector, and we know the init_secret.

  1.  When using a "Full" commit followed by "add-only" commits (see attachment 02.jpg for a diagram)

The second issue arises from the fact that "add-only" commits allow new group members (ONLY) to learn the value at the root of the TreeKEM tree in some earlier epoch E. In general this is not a problem, because they won't know the init_secret for epoch E-1. However, if only the very first commit for a group is a "full" commit new group members do know the init_secret for epoch E-1, as it is always the all-zero-vector.

>From here the attack proceeds very similarly to the other attack. Imagine a group is created by Alice. Alice adds Bob to the group with a "full" commit (hence init_secret = 0 and commit_secret ≠ 0). Next, Alice adds Charlie to the group with an "add-only" commit (not updating the TreeKEM tree). Next, Alice adds Eve to the group also with an "add-only" commit (again not updating the TreeKEM tree).

At this point, Eve learn sthe value at the root of the TreeKEM tree. Since this hasn't changed since the first epoch, Eve can find the commit_secret for the first commit of the group. This, together with the fact that init_secret is the all-zero vector, allows Eve to compute the joiner_secret and welcome_secret for the first commit. Hence, Eve can now carry out the attack described first to obtain all the keys for the epoch in which Bob was added.

Furthermore, because the commit_secret for the next commit is the all-zero vector, Eve can compute the joiner_secret and welcome_secret for the second commit as well. Hence, Even can carry out the attack described first again. In fact, even is able to do this until she reaches the commit in which she was added herself.

I believe the easiest way to mitigate these attacks (and any attacks like it) is by requiring that the init_secret of the first commit is a randomly sampled value. Alternatively, the first two commits of a group could be required to be "full" commits.