Re: [MLS] UPKE for X25519/X448

Joel Alwen <jalwen@wickr.com> Tue, 22 October 2019 11:18 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 C236E12081F for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 04:18:31 -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 LxpgwRss6VHK for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 04:18:29 -0700 (PDT)
Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) (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 2A9621201E4 for <mls@ietf.org>; Tue, 22 Oct 2019 04:18:28 -0700 (PDT)
Received: by mail-wm1-x335.google.com with SMTP id r19so16798679wmh.2 for <mls@ietf.org>; Tue, 22 Oct 2019 04:18:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=X3A3E1gAcM8rdlFNx0r0sDotsEKOeK0JD1MzkPF+l8s=; b=L9l9SvtWQ2vhc4tkrxAPy/+51/pHwescqDduBYECqrWuqmEty9R6+K4QhM+BRR7K+H ufBGsYfneD3py+wyXvUTVJl6NdJOmj5TzpUiEPGx4quOFuJzeDArGv9HxhibywDgMiPv f2D7swCj3VWoI4Ld0T59QIMwmre+Qi0A+YPnZX0vI2C5RQR5dmUwcXNXDbUj1Xtd+EE7 GkRpkz54+oLaY+jf7zRcEyfleQk7QMDNZO1HMoJYVp5VgHPJE0wEbKKEad79bzRWam4R xdqLSrGlen17/S+VANvzEXkM3zz5k01yPLSzVItxh3LvKCJCuz1n0+/eii/wTfejOJlc yQFQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=X3A3E1gAcM8rdlFNx0r0sDotsEKOeK0JD1MzkPF+l8s=; b=V+nTB2FZp8rJ6THJNpUQ6pZFF86nB5Yg0q8g5mNR5iKE5I37fX5PO7FlhYabdoFl2K IiTcOK48feery7c7nkf9Zw3cA3c6C9BVvp+3H8zLbk5JDz3vhpmjtgYjcbfndrA6ZPk3 doSo4W/qX4VDSepV89kmYwaDKmTQFDnDaGrVTeNFu6+75LWlbDAmdHbPGjbJZnPle8Sz jtKt4a4qrdk2qiA//B5UCE11n3u/ictJ2JtlvDZ/WfWnS4DrSCRgHq8JcZ9bbNo+OyDE nVuQEXGuhDhqhH2NWxLdGBxKzeOjMPuWELoAjm8w0Seuv/XAMyNF/F4zhNIR4pIawTMf 80IQ==
X-Gm-Message-State: APjAAAXR32JkJTCZDBFdJmliOED/F1UbdxjVVG77mWCQpbQPPa8Xcvb8 vL1xu0gt3JTtbZWWajZSikusFDdYvlE=
X-Google-Smtp-Source: APXvYqy+/frVgSf2MeSOnvntkZZLxgpLBbiLcxbW3EBYtt/U43IJgb94MzwbP/jGqBrmS6rVJCo94w==
X-Received: by 2002:a1c:64d6:: with SMTP id y205mr2382066wmb.136.1571743106177; Tue, 22 Oct 2019 04:18:26 -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 b1sm10434924wru.83.2019.10.22.04.18.25 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 04:18:25 -0700 (PDT)
To: Richard Barnes <rlb@ipv.sx>, 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: <d5a52f39-ac2c-5118-8a15-d7706861dc9b@wickr.com>
Date: Tue, 22 Oct 2019 13:18:26 +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/n1YPHk8oDGJMt29D4IMyxOJOtnQ>
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 11:18:32 -0000

Hey Richard,

Thanks for the code to help testing this stuff!

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.

The reasoning here is based on the view of X25519(pk, s) first does
Clamp(s)->s' and then pk^(s') mod order. So Mult() first maps the scalar
inputs the their clamped representatives and only then does the
multiplication.

But it could be this is not the right view of X25519 (though, in my
defense, Mike H. also seemed to think the construction should work and
he knows way more about this stuff than I do).

> 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?

Indeed, from a formal mathematical point of view Mult() is *not* aiming
to be a multiplicative homomorphism because of some rare exceptions. But
Mike believed that the probability of running into such an output, when
using uniform randomly chosen inputs was around 1/2^{-126} or so.
Moreover, for X448 he thought the probability was 0. To be clear, he
wasn't 100% and recommended testing.

> Also possible that I'm just missing something :)

Yeah, same here. I'll see if I can figure out whats going on here and
get back to the mailinglist if I make any progress.

- Joël

> 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
>