Re: [MLS] UPKE for X25519/X448

Joel Alwen <jalwen@wickr.com> Tue, 22 October 2019 13:19 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 8CF2B120802 for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 06:19:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 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, URIBL_BLOCKED=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 jWzQgBariWL3 for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 06:19:37 -0700 (PDT)
Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) (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 A05131200F6 for <mls@ietf.org>; Tue, 22 Oct 2019 06:19:36 -0700 (PDT)
Received: by mail-wr1-x42f.google.com with SMTP id l10so17629645wrb.2 for <mls@ietf.org>; Tue, 22 Oct 2019 06:19:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=qb29iRnrqlX84EDkTUNNpubrroomaheQTDW3GsJK/Tw=; b=K3BsLLSbrwHl2hqrPQpK+qjDv0I//NuQe0TEN3ejTN8GrUyHVYUBsLAM7wc77DEqHi c6VDlon8ZI+0y6yVxKvzZ3uUt0AsFmjZqMBMMj/ZIo93SUjPg1a9ISIJv8sK4wgvte5w BlB277xsbNLKf14QB02HrCHO362uAQTLs5L0pN1w/Y+cYiuxdpUwPg/vT4DUjgwEouJ1 BgS8FDTusVJd0ZRHhFEIT+eDj0DR/tLzZ9B3NWZt41vD7eZqCZfu71I0WIbnq9wXyEWY 14vczQ2ZlmW3qUM3c7oq5JHvEwWhp7MK6u1tTwKbyOGDHoPO+vXgVjqny9gQwubxc2La EYgA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=qb29iRnrqlX84EDkTUNNpubrroomaheQTDW3GsJK/Tw=; b=Kpf4STbUBzu4EPspYB+pSrhM1rWkC0WCrQ3eCNgahp4b9T8R8ta4opUB0RfLXSu+lW cOMo1fU9sSwLTxy05Lly+dXhNO9B5TjQBZS8IosxhuskQvYip74vSVp8UAM/u+oA3mU9 3q7XmapSZqYCXYnh0OWsisiW457Md477AM6KNgwZkPJZRRXMKrS6ntVpRDq9Ga/El3RV yEMkZ9jlYQTiDdncd2wWUW715CZSE3R7e6sJgwNmVU43r1v/Ixs9h0UriF3IFWoCRiB0 SVqqjYEqk24k5nm03bSw08oekvNV+Tprn4uuIQLEW1XDlvtyieJYDNisK6zug8VUjvaA 4FfA==
X-Gm-Message-State: APjAAAVY6yYQXgKRv6t1F8zIwGZ5+1Z3ugCsmP8uUDNYjA9wGHAAOpyB A59CdmhvpdIp4fTxUTfQGniWj3wVmUI=
X-Google-Smtp-Source: APXvYqwPKHfB/dEp2bHFqFVhEuQGQve4GXhlR306zxx6+HHkRUuPPjeOm4i8T/sWrrCKfpL4wq0HYQ==
X-Received: by 2002:adf:dc42:: with SMTP id m2mr3690190wrj.314.1571750374426; Tue, 22 Oct 2019 06:19:34 -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 a3sm16372697wmc.3.2019.10.22.06.19.33 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 06:19:33 -0700 (PDT)
To: Richard Barnes <rlb@ipv.sx>
Cc: Messaging Layer Security WG <mls@ietf.org>
References: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com> <CAL02cgRDKN9b8eLdh=uCApP7Mi+-JTYo8jxv1AOXR2mxXo=15g@mail.gmail.com>
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: <fd1956c3-3c48-877d-ceab-221cda615a85@wickr.com>
Date: Tue, 22 Oct 2019 15:19:32 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <CAL02cgRDKN9b8eLdh=uCApP7Mi+-JTYo8jxv1AOXR2mxXo=15g@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/YHEjTKtnLKASoUeE1iZ2_V8FvGc>
Subject: Re: [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: Tue, 22 Oct 2019 13:19:39 -0000

Ah crap. I had a typo in my original email in this thread. Mult() is supposed to _multiply_ the clamped values, not
subtract them. *facepalm*

So the correct pseudocode for Mult() is:

 Mult(a,b) {
   c = (Clamp(a) * Clamp(b)) mod order
   if msb(c) = 0
     c = (order - c) mod order
   return c
 }

Sorry about that. Unfortunately, I think the code *still* doesnt give us what we want though. I'll keep playing with this...

- Joël

On 22/10/2019 06:41, Richard Barnes wrote:
> FWIW, I tried to update this and it appears not to work, either in the sense of pk' = pk(sk'), or in the sense of pk'
> and sk' producing equivalent DH results.
> 
> https://gist.github.com/bifurcation/795dd09ca399acfda5db87bc825a90ca
> 
> It seems odd to me that the *Mult* functions computes Clamp(a) - Clamp(b), instead of multiplying ... well anything. 
> But even when I changed the Sub to a Mul in my test code, things still didn't work.
> 
> The problem I observed in the CFRG thread on this long ago is that there are X25519 DH outputs that are not valid public
> keys, which I think implies that you can't have any homomorphism in which the DH function is the public transformation. 
> Maybe that's what we're running into here?
> 
> Also possible that I'm just missing something :)
> 
> On Mon, Oct 21, 2019 at 5:21 PM Joel Alwen <jalwen@wickr.com <mailto:jalwen@wickr.com>> wrote:
> 
>     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 <http://ia.cr>\2019\1189.
> 
>     _______________________________________________
>     MLS mailing list
>     MLS@ietf.org <mailto:MLS@ietf.org>
>     https://www.ietf.org/mailman/listinfo/mls
>