[MLS] Prevent/Reduce collisions of commit_secrets

Cornelissen Eric <eric.cornelissen@aalto.fi> Mon, 07 September 2020 14:15 UTC

Return-Path: <eric.cornelissen@aalto.fi>
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 472563A0D7E for <mls@ietfa.amsl.com>; Mon, 7 Sep 2020 07:15:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fqvS8xwWPM0c for <mls@ietfa.amsl.com>; Mon, 7 Sep 2020 07:15:06 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (smtp-out-01.aalto.fi [130.233.228.120]) (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 EDE3C3A0D7C for <mls@ietf.org>; Mon, 7 Sep 2020 07:15:05 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (localhost.localdomain [127.0.0.1]) by localhost (Email Security Appliance) with SMTP id C3C85115763_F564063B for <mls@ietf.org>; Mon, 7 Sep 2020 14:14:59 +0000 (GMT)
Received: from exng3.org.aalto.fi (exng3.org.aalto.fi [130.233.223.22]) (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 68CE911572C_F564063F for <mls@ietf.org>; Mon, 7 Sep 2020 14:14:59 +0000 (GMT)
Received: from exng4.org.aalto.fi (130.233.223.23) by exng3.org.aalto.fi (130.233.223.22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1979.3; Mon, 7 Sep 2020 17:14:59 +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; Mon, 7 Sep 2020 17:14:59 +0300
From: Cornelissen Eric <eric.cornelissen@aalto.fi>
To: "mls@ietf.org" <mls@ietf.org>
Thread-Topic: Prevent/Reduce collisions of commit_secrets
Thread-Index: AQHWhQeTmA+/88t920GdxdAI8L1FyA==
Date: Mon, 7 Sep 2020 14:14:59 +0000
Message-ID: <87a306b5ec5d4a73a03e14526ad8ab59@aalto.fi>
Accept-Language: en-US, fi-FI
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [130.233.0.5]
Content-Type: multipart/alternative; boundary="_000_87a306b5ec5d4a73a03e14526ad8ab59aaltofi_"
MIME-Version: 1.0
X-SASI-RCODE: 200
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=7O5+omu0M/sLG0qfs/MnmGQH7E2XBA55iSVMK/7mOgc=; b=LcFQ2J1AIeuKlZHUVpXBtYSUVMDNcRNViWRrAOu94jRGCp6gyYUs1OV8nPpBcBwqXBvVpZpjBqxFAgwC2pE6AHPgkhZBAMLB4wDPBCVo/0vMXdhYGfHBToU/YVhsaQB0181FDnA7d4F/rqi5I2PCaO+qbEmIYnmL73oz8YR/JJqcgv8oFGOjqdz96KLF6Dwilqq1twZ65dJIMHLoPK1ffxaBvbJD+iOCTxbuLpQ4P5LYTNG/DVuqKH+M9LdqkpmbvKEtSR9BU+cN2PqnkG1rCvgAUms7BBmpZIVoE3FOTzx6yMVKYfBBexDqpFGM2yFIbcmST1i1aJuGP/I32Q1Tew==
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/bz9ilEweiQDUvzKu6yP8Y7tncUw>
Subject: [MLS] Prevent/Reduce collisions of commit_secrets
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: Mon, 07 Sep 2020 14:15:08 -0000

Hi all,


I want to propose a slight modification to the direct_path derivation to prevent (to some extend) collisions at the root of the tree. In short, an adversarial group member can pre-compute a direct_path for a lower level and use the path_secret of its current node as the leaf_secret for the current direct_path derivation. The result is that the root_secret will be the same between two trees with a (significantly) different structure.


We can resolve this problem in a couple of ways (for concreteness I added the derivation logic at the end of this message) (clearly, this list is not exhaustive):

  1.  Add an increasing counter, starting from the leaf, to the path_secret derivation (*)
  2.  Add the node index of each node in the direct_path to the path_secret derivation
  3.  Add the node hash of each node in the direct_path to the path_secret derivation
  4.  Add (something derived from) the previous epoch's path_secret of each node in the direct_path to the path_secret derivation (**)

All of these solution guarantee that the adversary has to find collisions to cause the same commit_secret.  Additionally, the first two solutions prevent collisions within a group, the other two solutions potentially prevent collisions between groups as well.


Regards,

Eric


(*) Note that an increasing counter starting from the root won't work because it would be the same between the two trees I described in the attack.

(**) This is based on an earlier proposal raised by Joël & Sandro in the mailing list, see <https://mailarchive.ietf.org/arch/msg/mls/ZR84smU5xeLrziNTk5W1P1Z1nQI/> https://mailarchive.ietf.org/arch/msg/mls/ZR84smU5xeLrziNTk5W1P1Z1nQI/ (the MLS Specific Fix). I simplify the proposal here as the specifics can be found there and I think any discussion regarding it belongs in that thread.


----------


Below you can find concrete derivation of each proposal, For simplicity I use the context of ExpandWithLabel to include the additional information.

1. counter
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", 0, KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", n, KEM.Nh)

2. node index (where index(node[i]) returns the node index of node i)
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", index(node[0]), KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", index(node[n]), KEM.Nh)

3. node hash (where hash(node[i]) returns the node index of node i)
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", hash(node[0]), KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", hash(node[n]), KEM.Nh)

4. previous epoch path_secret (where path_secret[e, i] is path_secret[i] in epoch e), ignoring blanks for simplicity
    path_secret[e+1, 0] = ExpandWithLabel(leaf_secret, "path", path_secret[e, 0], KEM.Nh)
    path_secret[e+1, n] = ExpandWithLabel(path_secret[n-1], "path", path_secret[e, n], KEM.Nh)