Re: [MLS] UPKE for X25519/X448

Joel Alwen <jalwen@wickr.com> Tue, 22 October 2019 14:47 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 A2809120013 for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 07:47:20 -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 sYVMkMz9CYxz for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 07:47:17 -0700 (PDT)
Received: from mail-wm1-x32b.google.com (mail-wm1-x32b.google.com [IPv6:2a00:1450:4864:20::32b]) (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 83EF2120086 for <mls@ietf.org>; Tue, 22 Oct 2019 07:47:17 -0700 (PDT)
Received: by mail-wm1-x32b.google.com with SMTP id g24so8447334wmh.5 for <mls@ietf.org>; Tue, 22 Oct 2019 07:47:17 -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=IjIT/avS65uPl63N4P097coy5dLcnXtfHyp3CdJChhs=; b=v19FUb842+psnKFBxVZtCkPqbdJ1C6wjMCyjnC1/LdLyiJWJqy2qamlLow+bjiVVqb FAobMQrVgT4SYXLA+xjiK/58WZEcLYnKyPePFEaR98ncc4E6dn5qi+cPTnGt6nSKc5Oa G/wfIVgwBcR2YWQSqjEkGe3oAPPjkf43nStOS3UTqHI2GHwh5+kl26QU0oCmXnZQ3i/W C9wQWlPBpj3vwku4tdsV6qP0TYIn9PcehD87GMN3BcBLA4CFK4bHO9VQCeKmStChj6+1 GqcLneZ87FgpqbYJTS6HP9fs9CwLzkjdMn8q2976/ThvLQ5606011ehuFpWPHZqWQN8S dt8g==
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=IjIT/avS65uPl63N4P097coy5dLcnXtfHyp3CdJChhs=; b=XErgEiSr1Rv2MikqgEdJqrMjFCuuIGGeXlCKl1gUXsIeZ4KkyiN5Z3+h1JXTEJe1tn Govh9/AjZZBghaWrtb5c27YIeyuCFZD866U6r9qcfs81PW8adaYqC76KUjX3dyQjDlL4 TL7K9rjn4Jn/JKZffctskwCBFZTcSmKASwjYLvzXAd5W+Dy/BJ0Bc2KuPV2jZrLU6hWR gLHvvw594Q7n738sG5Pme94BVUakc8oispTvV6GNAVGhhTKpuIWihnU/lu7IhOY58PER cjqxh8jnknvaNsB6RZJ1mHKELPzcZSY1qvqpdvdrVIjRBgLt6P0GMi0aovXClxt5LBBL Y/HQ==
X-Gm-Message-State: APjAAAVQGj6Er/zV5iwDU5uvn7DzbEB9q2su2nsoDxrW/rJL5++0zgjg RGypC6EUu0DLYw9en7sybn1VGXrFgjI=
X-Google-Smtp-Source: APXvYqwpjxbEvPV0xXJfvRoPNPGjP1VwFGlA0Xm8KJC7jp7AjQfkoZAPpu/AagWDjjSdoV3lNXg6Uw==
X-Received: by 2002:a7b:c019:: with SMTP id c25mr3105575wmb.61.1571755635269; Tue, 22 Oct 2019 07:47:15 -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 v10sm11935257wrm.26.2019.10.22.07.47.14 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 07:47:14 -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: <71d9cd8a-4d00-118e-bf03-1c90534dc474@wickr.com>
Date: Tue, 22 Oct 2019 16:47:14 +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/SW0hNjsaRn5UmgxFRPunYWC-cEA>
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 14:47:21 -0000

EUREKA!

I got it to work with the following changes:

1) clamp both scalars befor doing the Mul (instead of just le2bn)
2) using the composite order (n25519*8) instead of prime order (n25519)
3) mul instead of sub
4) condition on bit 254 == 0 instead of 255.

Here's the (now working I think) code. https://play.golang.org/p/UaFVV6HG-Nf

Reasoning for changes:
1) Was as originally intended. Basically X25519 clamps the scalar, then does exponentiation.
2) Mike had already mentioned I should use composite not prime order. I just missed it. more *facepalm*
3) Multiplicative not additive homomorphism
4) Goal here is msb should be set to 1. If it isn't then we need the negative. Basically, msb is bit 254 instead of 255.

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