Re: [MLS] UPKE for X25519/X448

Benjamin Beurdouche <benjamin.beurdouche@inria.fr> Mon, 21 October 2019 21:57 UTC

Return-Path: <benjamin.beurdouche@inria.fr>
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 0D027120AA0 for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:57:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.9
X-Spam-Level:
X-Spam-Status: No, score=-6.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 OC_v6iI1Mdkr for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:57:19 -0700 (PDT)
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) (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 3D4E9120A7F for <mls@ietf.org>; Mon, 21 Oct 2019 14:57:19 -0700 (PDT)
X-IronPort-AV: E=Sophos;i="5.67,325,1566856800"; d="scan'208";a="323592350"
Received: from 37-166-43-191.coucou-networks.fr (HELO [172.20.10.9]) ([37.166.43.191]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Oct 2019 23:57:17 +0200
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.0 \(3594.4.19\))
From: Benjamin Beurdouche <benjamin.beurdouche@inria.fr>
In-Reply-To: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com>
Date: Mon, 21 Oct 2019 23:57:12 +0200
Cc: ML Messaging Layer Security <mls@ietf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <8E0E25A7-2839-4D45-8C8E-07B79637FABC@inria.fr>
References: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com>
To: Joel Alwen <jalwen@wickr.com>
X-Mailer: Apple Mail (2.3594.4.19)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/tdQ2eoGyxipHb9kNHm64hCGz6dU>
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: Mon, 21 Oct 2019 21:57:27 -0000

That look excellent !
If that works as expected, that would indeed be very nice… : )

B.

> On Oct 21, 2019, at 11:20 PM, Joel Alwen <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\2019\1189.
> 
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls