[MLS] UPKE for X25519/X448

Joel Alwen <jalwen@wickr.com> Mon, 21 October 2019 21:20 UTC

Return-Path: <jalwen@wickr.com>
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 6ADD812001A for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:20:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.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 o_zmWZZglwxC for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:20:45 -0700 (PDT)
Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) (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 5DC50120019 for <mls@ietf.org>; Mon, 21 Oct 2019 14:20:45 -0700 (PDT)
Received: by mail-wm1-x32f.google.com with SMTP id r141so4572236wme.4 for <mls@ietf.org>; Mon, 21 Oct 2019 14:20:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:from:subject:openpgp:autocrypt:message-id:date:user-agent :mime-version:content-language:content-transfer-encoding; bh=a1QBPnMIhQmuQK58B397uI+ZdUVu7MHKSl6zeNAFGqA=; b=fXpVhneDcVMDEvcUf+J548KVcINd8Y25wE36OaoW8Djla50RQIB+SgrG/nc2O+YzDw RWW+SedYX1YOH66AfWztj9JEU15k83w+kmQ3AvwkT+WbHklj87zBKxjrQKDM8SJAo10n qY2XKN6zt82pqmkFq4q9FHkNcBrMyAlYNNRn6Hl1cWfEwjBdIixwgJ/kzPsojD6ImBGn NGTjPuzlkP8MUoU7JFUWlGasUc0XxnMhr4o8pxcvrjClSZfdaUnqRDP2e2TZfRluooAX IHY7EDNhVduTqwbUooRRc3/MZM/CpwHGine9eg8NSUuzOvc9PHPGeMBh1zz1fdi9QF0q g4kw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:openpgp:autocrypt:message-id :date:user-agent:mime-version:content-language :content-transfer-encoding; bh=a1QBPnMIhQmuQK58B397uI+ZdUVu7MHKSl6zeNAFGqA=; b=tmUxE+GlOJqh0thfdb3/5f/5dUCM01RVQw3yn79jiVykAtNabGzdETtkb74I7HpdP6 E/JJ/w1+uEdMWdxSvmUN/eU8EMiFvgVGU+zw41Aqhhtyq0CuXFF/9n8H4V1rGDjhbiw3 cLRlisSWXIPnJM5TN+XiNS0lNIrU7Y7OPmx31GVlTP3BhS8DcigDmDMepsHNc/KSHblq PWute99+a7FSitveJGP3HBi5F/1C+YZ116OvyapRTtvFUDzJu7cyTbCGSVuHhAxP6pPS u/0MM1/svjj8tgQTdbT42lJOe8TdcIfGJ8ImMqhBkZ9XvdxQXUR5EWXY33Ja32D3N6zx PQHA==
X-Gm-Message-State: APjAAAWgknIdacE7BwQ4/vklYelnoCrl3XtAKLh43d5fVOyLGhXwlSuG tJoYA1uP8QJglEh7obwZbXIKwVWuR9Q=
X-Google-Smtp-Source: APXvYqxxRCg37Xf4YUZPUFuU6pMehA7LStZz0qGP7ybW/e276Ba+5M+zLXJFTDZS7RupItOPpVftag==
X-Received: by 2002:a05:600c:2c2:: with SMTP id 2mr23394wmn.112.1571692843330; Mon, 21 Oct 2019 14:20:43 -0700 (PDT)
Received: from [192.168.1.137] (84-114-27-5.cable.dynamic.surfer.at. [84.114.27.5]) by smtp.gmail.com with ESMTPSA id v10sm13239002wmg.48.2019.10.21.14.20.42 for <mls@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 21 Oct 2019 14:20:42 -0700 (PDT)
To: mls@ietf.org
From: Joel Alwen <jalwen@wickr.com>
Openpgp: preference=signencrypt
Autocrypt: addr=jalwen@wickr.com; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x 3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46 4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7 vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP 2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt 0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com>
Date: Mon, 21 Oct 2019 23:20:42 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/y5ikXqQh7VAojXrNSt9odxgNVmE>
Subject: [MLS] UPKE for X25519/X448
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, 21 Oct 2019 21:20:47 -0000

Hey,

This is a follow up to the earlier Re-Randomized TreeKEM email. (Its a
separate thread as it changes whats in that first email and I didn't
want it getting lost in the other thread when people evaluate whether to
adopt RTreeKEM for MLS.)

In short, after some very helpful back and forth with Mike Hamburg, it
is looking like we have a reasonable way to do Re-randomizable TreeKEM
(RTreeKEM) based on the X25519/X448 ciphersuits. That would mean we no
longer have to choose between RTreeKEM and those suits. IMO that removes
the biggest barrier to using RTreeKEM.

To be clear, we're still doing a some coding & testing to build
confidence. And we will also run it past the CFRG / a few more ECC
experts besides Mike, to make absolutely sure it works as intended.
But at this point we are pretty optimistic already.

The rest of this email contains the details for how RTreeKEM can be made
to work with the X* groups.

- Joël

-----------------------------------------------------------


Essentially, all we really need for RTreeKEM is to build "Updateable
Public Key Encryption" (UPKE) as defined in [1].

Rather than the construction in [1] which is based additive
key-homomorphism we can use the following construction based on a
multiplicative key-homomorphism. (It turns out the later is easier to
implement for X* groups than the former.)

To minimize the diff between current TreeKEM and this new variant of
RTreeKEM, the new construction is formulated it to use HPKE and HKDF as
black boxes.

Inherited from Cipher Suite
---------------------------
- sksize = # of bits for secret key scalars. (e.g. 32 for X25518)
- order = order of prime-order subgroup (e.g. as in RFC 7748)
- DH(A,b) : A Diffie-Hellman function. (E.g. X25519 or X448)
- Mult(a,b) : Multiplication of secret keys. See below.


Multiplication
--------------
- NIST curves : Mult(a,b) = a*b mod order.
- X25519 : let Clamp(k) = decodeScalar25519(k) as in RFC 7748.
- X448 : let Clamp(k) = decodeScalar448(k) as in RFC 7748.

For both X25519 & X448 use
 Mult(a,b) {
   c = (Clamp(a) - Clamp(b)) mod order
   if msb(c) = 0
     c = (order - c) mod order
   return c
 }


UPKE Construction (from HPKE & HKDF)
------------------------------------
- UPKE-KeyGen = HPKE-KeyGen

- UPKE-Encrypt(pk, m):
  d'  <-- {0,1}^secpar
  d   := HKDF(sksize, d', "", "derive UPKE delta")
  c1, context := HPKE.SetupBaseI(pk, "")
  c2  <-- context.Seal("", d' || m)
  pk' := DH(pk, d)
  return ((c1, c2), pk')

- UPKE-Decrypt(sk, (c1, c2)):
  epk, context := HPKE.SetupBaseR(c1, sk, "")
  d' || m := context.Open("", c2)
  d := HKDF(sksize, d', "", "derive UPKE delta")
  sk' := Mult(sk, d)
  return (m, sk')


References
----------
[1] http:\\ia.cr\2019\1189.