Re: [MLS] UPKE for X25519/X448

Richard Barnes <rlb@ipv.sx> Tue, 22 October 2019 04:41 UTC

Return-Path: <rlb@ipv.sx>
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 C42D912008C for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 21:41:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=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=ipv-sx.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 GGhjrrKOCVSH for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 21:41:28 -0700 (PDT)
Received: from mail-ot1-x32c.google.com (mail-ot1-x32c.google.com [IPv6:2607:f8b0:4864:20::32c]) (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 9B9B0120086 for <mls@ietf.org>; Mon, 21 Oct 2019 21:41:28 -0700 (PDT)
Received: by mail-ot1-x32c.google.com with SMTP id 53so1428008otv.4 for <mls@ietf.org>; Mon, 21 Oct 2019 21:41:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=HDb/O27LGAxr+5Q9NggfCk2xEgdA4HiI4D8Oie9/Phg=; b=eKCwtGQzKin7DzzopU8Ga4JqvLqGLKmXJZrc2HA0XhyPj3DSzAEBBs2YyHw3YBUHbD I+qnIuxIVdLl4s0djBDS7CLnb1UR8jVfPIPE23tsCaq2IOBUI1frg2QQbMV80jaZ0uJ5 eP71GthtzP7XYw67bg21VVb5Gr4Ab/G1WUg08Sv9APcmhj1AF7xUVZusYiA8Xy6J/P6S UWPmGn+lrdiJkfuX0dNmkqYIQ7Vl266FC6ktpWY3iBIfY243GqKc47NxJuPCx+5OjJrj HGwrsB00qVuPkoDp9MQZlA2VIvTsOi3iuc4Cg9bRj0a81HKCVlSlsPByv/s1NFpCjl5L zSaw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=HDb/O27LGAxr+5Q9NggfCk2xEgdA4HiI4D8Oie9/Phg=; b=M27S/wo3hhS/fYwm0CdDNTTAg6MhR8m3rR34vA20jn4avO4ahGe/0s/5bJcEPKOQbK e14T6iD31ucZWJPvzVrDcevcbrQN10ECXc1d5nGyF2bKWIVI6JICy6k+7kRVcjJkAvFt jetWy21eRZ14vBX3LcrJ8genZgAaSzNs7Mt3RdvvuhDYnvX/Q+1XASBJUKWGeZ7ZKoP+ 6bSj3xAiZbNp8eNLUj9hrN4x7Rcn+S51PSMettJsPXgM2IcSi15ZUdTQfSiRadtae2/4 ich4AgoXjNknOYE/vI7ataVdkuX7hyId0gEx+eE8OiqL7fM/WiRpHQTE6uIMvHQipenl 8lfQ==
X-Gm-Message-State: APjAAAXvN90+0BXcnTZBEdYsH7qPEn0pwrQjSzLkgsc9DWrXwhAGZscl PzbGJ9S1Ss7PeeINlw8V/Gysl1l69fOwJLK7qs5WGY69rHo=
X-Google-Smtp-Source: APXvYqwzNTFfQw1ud08KV3gh1WADEyVajl9SmfNZC8sxZwY/ZEe1fiQlDT0m9lz+bvg2YuddIz27Af8fSbpH1/GJUs4=
X-Received: by 2002:a05:6830:13d8:: with SMTP id e24mr1057272otq.42.1571719287646; Mon, 21 Oct 2019 21:41:27 -0700 (PDT)
MIME-Version: 1.0
References: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com>
In-Reply-To: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Tue, 22 Oct 2019 00:41:05 -0400
Message-ID: <CAL02cgRDKN9b8eLdh=uCApP7Mi+-JTYo8jxv1AOXR2mxXo=15g@mail.gmail.com>
To: Joel Alwen <jalwen@wickr.com>
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000d3bfbf0595786984"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/K7HcifXj0Z69LLFh2YyaKptudRk>
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 04:41:31 -0000

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