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

Richard Barnes <rlb@ipv.sx> Wed, 05 August 2020 15:59 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6806E3A0B3D for <mls@ietfa.amsl.com>; Wed, 5 Aug 2020 08:59:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=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=ipv-sx.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HJCn77tah7Sv for <mls@ietfa.amsl.com>; Wed, 5 Aug 2020 08:59:09 -0700 (PDT)
Received: from mail-qk1-x72c.google.com (mail-qk1-x72c.google.com [IPv6:2607:f8b0:4864:20::72c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 083E73A0CA4 for <mls@ietf.org>; Wed, 5 Aug 2020 08:59:03 -0700 (PDT)
Received: by mail-qk1-x72c.google.com with SMTP id d14so42096602qke.13 for <mls@ietf.org>; Wed, 05 Aug 2020 08:59:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=lr0ux52+MyK1znCeM/FD3rimV2ctYTuyMcr2Pq6Jsyw=; b=f3OtCViTSRUhnxx4Zv1DruR1UdTmi9eQ3zC91sknT4PNXvMZVV4WuriN7oCJSeWK/s IqSYW12bNijxsCZHEBnkcHf31C3mP0QXxQBQTJQD7qMTdsCoAMrjxWuqY8gMQs1ZiyFO gt4fz5tloD8T7EWRMax21k72+YWN0odcEYw0Mc3vlC/ym32v/M3bG2NweTa6VCcXSPKk YlMqinUNUVHIl0k+L0C2TPTF5Y1fA+5XlUoNWAMGsIZiKGSTf7vH+/hqyj0Of16ayiSK cjrGnt9eksOuxvlD/aq83AiFGTrdVzbCpJhAibEQv3deNjlwGl8cGEis9QiRb6j0UkqO D1hQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=lr0ux52+MyK1znCeM/FD3rimV2ctYTuyMcr2Pq6Jsyw=; b=H6NxE1yOw9GVOrDdm5MDy++9oIKhusaeMzTe9XjdY5njPC8++LH0R1v8n3BYadnGxn CeYwGrBIvGJQVu4mMbFmBFGZTOBRTK93ycUb3hnJlufk/KM63XGAyoYN7y8Fk1es2mVp al5+253i+rzZNtlGQrZpcAAVKCEE330ioNev4sErCtNylXDmgdSzIL9FE7McUJrRkByD G44TkJel7KypAWHqr5q8cNBCUEi+5NfwnLFPHqBavvswhE315Dw3JaSuluA2jrWV+f3E 6AeSWSIJ4keRhmtHyMMCUQ6e5ACs1Re1Y0mgYrIjgPA0J3DOL2Mxa3v8tEYPNToUSxqY jeFA==
X-Gm-Message-State: AOAM530w23LTk0PdaqNv75rh8C0gpOxt93k7b70WAPbAJXGIds6iQRKI qoj4P/8C7LhgHlU2LIzwwG1DTtZZaKpv49Ds0n+BPw==
X-Google-Smtp-Source: ABdhPJwGn2Lc6UORGmPQZUtj7Xuhav3KH1ZzZJfY8QbLE2XQ6RbRzP1XesMYcP+ZYb4JgOWRBr1ApOGUMsUf3AjGTTs=
X-Received: by 2002:a05:620a:63a:: with SMTP id 26mr4159836qkv.490.1596643142777; Wed, 05 Aug 2020 08:59:02 -0700 (PDT)
MIME-Version: 1.0
References: <e0d6ff151c464d9d9cf49af054df6cdf@aalto.fi>
In-Reply-To: <e0d6ff151c464d9d9cf49af054df6cdf@aalto.fi>
From: Richard Barnes <rlb@ipv.sx>
Date: Wed, 5 Aug 2020 11:58:49 -0400
Message-ID: <CAL02cgR286OaG9Sq3s86-dycGcnw5VYc+DqOxLstSyhMShDrzg@mail.gmail.com>
To: Cornelissen Eric <eric.cornelissen@aalto.fi>
Cc: "mls@ietf.org" <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000005c104105ac237337"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/qrpAoK7aNSzKxX4O60pOLvM3cp8>
Subject: Re: [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 15:59:16 -0000

Hi Eric,

Thanks for the analysis, and the detailed, clear writeup.  I agree that
there are some real issues here, and with the solution approach.  Just to
align on a couple of details:

#1 is clearly a problem.  Good catch.

#2 is less clear to me.  You lose me when you say ""add-only" commits allow
new group members (ONLY) to learn the value at the root of the TreeKEM
tree".  How do you think this happens?  As I understand the spec, this is
not the case.  New members are added to the "unmerged_leaves" array at the
root, but they are not told the root secret or root private key.

In any case, I agree that we should change the initial init_secret from
being zero to being random.  I think I had set it to zero out of a general
caution against requiring fresh entropy, and likely under the theory that
the first commit would change it (before `path` was optional).  But it is
clearly necessary now.  If you would like to send a PR, I would be happy to
review.

Thanks,
--Richard



On Wed, Aug 5, 2020 at 9:27 AM Cornelissen Eric <eric.cornelissen@aalto.fi>
wrote:

> 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.
>
>
> Eric.
>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>