Re: [MLS] Re-randomized TreeKEM

Richard Barnes <rlb@ipv.sx> Fri, 25 October 2019 21:44 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 CC97812008F for <mls@ietfa.amsl.com>; Fri, 25 Oct 2019 14:44:13 -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 S4jq_WfrFbfa for <mls@ietfa.amsl.com>; Fri, 25 Oct 2019 14:44:09 -0700 (PDT)
Received: from mail-oi1-x22e.google.com (mail-oi1-x22e.google.com [IPv6:2607:f8b0:4864:20::22e]) (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 B16FE12004A for <mls@ietf.org>; Fri, 25 Oct 2019 14:44:09 -0700 (PDT)
Received: by mail-oi1-x22e.google.com with SMTP id a15so2590339oic.0 for <mls@ietf.org>; Fri, 25 Oct 2019 14:44:09 -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=snVuOSeiRtrgtAo+pS3BDk3VKlmImB3uuU+KFU22pwk=; b=zL3duBJllMtX3YtHWna2lkqeQkVlt4o+jSjqn4+ypnvX6YJ/2jL9P9DIqcuT6v/wng YI5ttLMmv6Ky/Cz3eHwsIpV9eZ5oQaxMWuF6UmP7DdzRAvD3sYNxOPFLMpnjoLlHVajj kzMXQ0azPQoGvnxc5Ae6IU8cH1lk9qjLgcIFwFNoog2qAW6l5NGttOsco6ZaHFOv7S77 Pc9zg4ssJjM0QaFAZy3OvzohYxWlZsAZ/5BBtGr9pthiGZMVuOygQYgPxs6xMhU2gaJl fbmSm7C9oJKJjYv2PEYNk5p61+8fw6cAjMKGqDvZQhKIU7MrAhURXq/BH+HE8216cyDe GjNA==
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=snVuOSeiRtrgtAo+pS3BDk3VKlmImB3uuU+KFU22pwk=; b=qoxayDOa5IejidkBZcXoB2Gaqitoz9Fu5ptenNfoTFcNPC4/iTtIVRtbhl2p7Dkb8E Sjg1X00wLOkiIULDczv6vjM0oUgyfjGxeoNFGPrD/gXabaQrj+jvMz5CtKE5iWZughf/ P4zdxBMwyXVrnpyV58N6VI/jeDjlhplDlWI5WC7FQ9cKerePrIptdwSwdLrreSPXpFfC U9wJvOEOKlrrzLnxWZWuJQrMRxSaa07vdkzVuxU8VJZITcX9agnHrXI9N5QnNvx1PU1+ AOwuDe3OCjJeUFJNUJOCI5tkixR1+M6elLjEz8zydlXPBGstwOUmCCUQ0VGzGe43B5A0 YV8Q==
X-Gm-Message-State: APjAAAWkWLq8dtXOFY5S6EfIDRpQ4CrNtJaKbFf9fp/ixHn8lbX7JUCZ Wrx+mLKxofHKpukAMyVr937Q+cxLGoDF/zZ3f9UvOQ==
X-Google-Smtp-Source: APXvYqzyabdS8KranwUtzGWzZVkseIkaaBOVmeleq535E3JZsE3syBjE0XQDWTVFtsl+nGhgqLZseV+8uYSqCzMQdKE=
X-Received: by 2002:aca:810:: with SMTP id 16mr4645310oii.149.1572039848563; Fri, 25 Oct 2019 14:44:08 -0700 (PDT)
MIME-Version: 1.0
References: <CAL02cgSykPGZhaS26MuR78XBS9OVfBzGYVEzcRRROqbP-P-t6A@mail.gmail.com> <3B5BE109-6C78-474F-A0E5-138DE6931CF6@inria.fr> <6E36D92F-E700-4B57-9784-CFD366ECA912@wire.com> <3b841c7a-07c6-d415-825f-fc930831a78b@wickr.com>
In-Reply-To: <3b841c7a-07c6-d415-825f-fc930831a78b@wickr.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Fri, 25 Oct 2019 17:43:47 -0400
Message-ID: <CAL02cgR+_VzJUZYp3Za1qzmqPPbtamRoyKW3GBTsjAPCseTq-A@mail.gmail.com>
To: Joel Alwen <jalwen@wickr.com>
Cc: Raphael Robert <raphael@wire.com>, Benjamin Beurdouche <benjamin.beurdouche@inria.fr>, Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>, Messaging Layer Security WG <mls@ietf.org>, Yevgeniy Dodis <dodis@cs.nyu.edu>
Content-Type: multipart/alternative; boundary="000000000000bf27cd0595c30cdb"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/9wDz0hu62OSui0W3rOxfIat1V04>
Subject: Re: [MLS] Re-randomized TreeKEM
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: Fri, 25 Oct 2019 21:44:14 -0000

FWIW: I did a quick PoC implementing the update primitive on top of
OpenSSL, within the crypto framework of mlspp.  It wasn't trivial, but it
wasn't too painful.  It is almost certainly not constant-time.

https://github.com/cisco/mlspp/pull/59/files#diff-8c57ca8ea136d0bb8c846c77ae5b9e78R665

On Thu, Oct 24, 2019 at 4:19 PM Joel Alwen <jalwen@wickr.com>; wrote:

> On 24/10/2019 12:09, Raphael Robert wrote:
> > This means that vendors/implementors have to implement something at a
> new layer that is somewhere in between the crypto library and the protocol
> layer.
>
> Yeah, thats a good point. To me, proposing a reasonable way to build UPKE
> on top of, say, libsodium is one of the main
> things I want to figure out right now (along with better understanding of
> how Mult() for X25519 can fail). Basically,
> this means implementing Mult() from, say, libsodium as going from Mult()
> -> multiplicative UPKE should be very
> straightforward using what I'd expect even the most basic interface for
> any X25519 implementation to provide. I guess
> the challenge here is going to be that both clamp() and the composite
> order are neither exported nor directly accessible
> in libsodium?
>
> In any case, if Mult() needs implementing from scratch then some of the
> risks I see here are:
> - Side-Channels: Mult() operates on secret keys so really it should be
> implemented with side-channel free code (e.g.
> constant time, memory access, etc.). We could mitigate this by proposing a
> specific implementation similar to whats done
> in RFC 7748.
> - Memory management: Secret keys being exported out of an X25519 library
> need to be handled safely in memory (e.g. 0-ed
> out before free, don't swap to disk, etc.) Libsodium does provide some
> memory-management functions for this very purpose.
> - Good Entropy: The re-randomizer d' needs to be sampled uniformly and
> independently. (Again I think most crypto
> libraries provide functions to do this.)
>
> Probably a naïve attempt at such a list of risks & mitigations. But making
> this stuff explicit seems useful for later on
> if we put this into the MLS RFCs (not to mention for a separate addendum
> RFC for 7748 describing the key-rerandomization
> technique on its own). So any input on the expected risks (and possible
> mitigations) would be very appreciated!
>
>
> On 24/10/2019 12:09, Raphael Robert wrote:
> > Finally I also understand that because of the clamping the actual
> security level of DH operations with curve 25519 is
> > not as clearly understood as it is the case with X25519 now.
>
> Not sure I follow what you mean here. One the one hand the UPKE
> construction is built on top of the X25519 (or X448)
> group not just Curve25519. In particular, Mult() uses the same point
> representation, clamping of scalars and scalar
> multiplication as specified in RFC 7748.
>
> On the other hand, if anything, I'd have thought questions about exact bit
> security are the other way round. It's X25519
> that does the clamping so that's where the question about exact bit
> security would arise no? Clamping isn't inherent to
> Curve25519 though; rather its just one way to do scalar multiplication
> mapping into a prime order sub-group based on the
> composite order Curve25519 group. But, as shown by Ristretto, other
> methods are possible that completely avoid clamping
> (and also happen to be both additively and multiplicatively homomorphic).
> In particular, I believe CDH, DDH and all the
> other usual crypto hardness assumptions are equivalent for Curve25519's
> prime order subgroup and for the Ristretto
> group. Not sure thats true for X25519 though.
>
> In any case, I'm no expert on this stuff so feel free to correct me if I'm
> wrong. :-)
>
> - Joël
>