Re: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt

Joel Alwen <jalwen@wickr.com> Tue, 05 November 2019 15:16 UTC

Return-Path: <jalwen@wickr.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id ABF7F120090 for <cfrg@ietfa.amsl.com>; Tue, 5 Nov 2019 07:16:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 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_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 cFORlUIpKMl1 for <cfrg@ietfa.amsl.com>; Tue, 5 Nov 2019 07:16:37 -0800 (PST)
Received: from mail-qt1-x82e.google.com (mail-qt1-x82e.google.com [IPv6:2607:f8b0:4864:20::82e]) (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 14ECE1200B3 for <cfrg@ietf.org>; Tue, 5 Nov 2019 07:16:37 -0800 (PST)
Received: by mail-qt1-x82e.google.com with SMTP id h2so16590738qto.1 for <cfrg@ietf.org>; Tue, 05 Nov 2019 07:16:36 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=y6F9XjKwUuX5wkyxuhp9O+U3AKqOva0JikLYBeXDtCw=; b=arX5dDAuduGIvVXc9uT7EOfqgztwo9RjHsNX0dbw2DAl0rWuea04/87cT2Joymr29x kH0qOup1I6u6Uug1uxn8C8EVxXOAmqYXjv0qFF6Khs3qTgQ1cEDEvRYYsXhDzLl8wbCq oPmGTSna8RnxR5Fjx4I+dWJK8Z9ug5iWLx6r6lmLLHQlkkzVN+i2WSzSmZxYVGlHUeDV CahH9Dirjg0paUCV7nw3RfVl9f+OH0dFd2gzk6Ba5vu6aQTiYwBBUiJVegOnfFe9+kGt 51TYSbU5y+2tYR2OUSApE2vwINlgO59Q/5vgUIC34TxBHIzcgz3lasIYOC+yijcKWTBL 6lzw==
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=y6F9XjKwUuX5wkyxuhp9O+U3AKqOva0JikLYBeXDtCw=; b=TcfK+v4eyeheV8+RcZxqJXY6dvUx2ro7B+odP9sCiag1/MvEuj4O39rSAMatBVfIhE 4NVBUkjc9aGJFhtANeETjAnbpCAYoYAHfMaYKcCNFJlzCMbvC0PCAp1Zo/tWGqDvyIDp +gmIjCVQpq2uJ66lHGmzq7CBH3Z2AZHHwPbnwFaF9svqNjRBGBLxRj1/SqcgJRy7acRz IQ2ehb0IlQ93HJbNliOuChsoAGZPVjs3H/mYBhGSG0/a1wiSYVsVXboNgV4462H6rFF1 ltlqN9807VgWodaGvlkffqb4fI7dfnsO5EXnkSKxzcVES1gHrt5/lLwjV+KvnNai6sba Ngwg==
X-Gm-Message-State: APjAAAXjHiihxhmtK4zPNkiTD0PU7KAQ7KQaph2aAysBbTftdF9WOtep nlDxRXgWh7O45nI4dWIQ/1EHbpaWTJb3WnRFWPzeug==
X-Google-Smtp-Source: APXvYqwm36LBfg5uesSx/PEpIRqPF0Sbrb+M/22Gj/Pfuahf5UoZLmlSTItz2uquZ001DUG1bv57qhdkJhn6DXrWQuE=
X-Received: by 2002:ac8:7655:: with SMTP id i21mr18341323qtr.53.1572966994908; Tue, 05 Nov 2019 07:16:34 -0800 (PST)
MIME-Version: 1.0
References: <157291108173.13892.5112993721217644254.idtracker@ietfa.amsl.com> <CAL02cgSgLaU4VMqnzvFyr_v3vErdc_mv5=E_gjgAofa2dmGg2w@mail.gmail.com> <CACsn0cn7dvgWg59FXBdH+YP9iaDbR9=MfJuzAh4hAOeadpRNuA@mail.gmail.com>
In-Reply-To: <CACsn0cn7dvgWg59FXBdH+YP9iaDbR9=MfJuzAh4hAOeadpRNuA@mail.gmail.com>
From: Joel Alwen <jalwen@wickr.com>
Date: Tue, 5 Nov 2019 16:16:20 +0100
Message-ID: <CANYP6035orzAcukza4a8ij7GD-MCG853r67aMa-+puwstvs0cg@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Cc: Richard Barnes <rlb@ipv.sx>, cfrg@ietf.org, Sandro Coretti <corettis@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000f9aaf505969aeaae"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/7-by0F3dAPtbcRITm6aOCOiTLaQ>
Subject: Re: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 05 Nov 2019 15:16:41 -0000

>  What's the application where you cannot modify the implementation to
compute n*X for any n, not just one of a particular length?

The idea is for key updates/re-randomization to be implemented as a (thin)
layer on-top of an arbitrary X25519/X448 implementations. To me, this seems
like a significantly less risky approach than to expect implementers to
correctly modify the (often pretty complex) X25519/X448 implementations. In
particular, if I'm not mistaken, then what you are proposing would require
digging in to the montgomery ladder code. The second concern I'd have with
your suggest is it requires modifying otherwise standard libraries which
means people would have to backport those changes to every new version of
the library (or worse, not update).

>  Secondly the calculation assumes d uniformly random

Yes, that is the intended instantiation here. But depending on the
application it could be relaxed in one of two ways. For key updates as used
in BIP32 style Hierarchical Deterministic Key Derivation [2] and Tor's
Hidden Service Identity Blinding [3] I believe its sufficient that d simply
has negligible probability of hitting the "failure set" F. Thus d's
distribution could be very far from uniform and still be fine. However, for
the Updateable-PKE application as being considered for MLS [1] we also want
an extra forward secrecy type of property. Namely, given the old pk and the
updated key pair it should be infeasible to compute the old sk (more
precisely, the old sk should still have CPA security). Formally, that
probably means d should be (close to) uniform.

Having said this, we actually expect d to be chosen by first sampling some
input(s) to a cryptographic hash function and setting d to be the output.
I.e. choose d' and set d:=truncate(H(d'), |d|). With this approach I
believe it would in fact be secure to have d' chosen adversarially (up to a
large number of updates). After all, modeling H as a RO means the
likelihood any given d' hits F is at most 2^{-125} for X25519 (and much
smaller for X448) so even trying say 2^{45} different d' values still only
has a 2^{-80} probability of finding a single d \in F. (Not to mention that
given only the pk its not at all clear to me if its even feasible to
determine what the corresponding set F looks like.) All three applications
above use some variant of this technique for sampling d.

In any case, to be clear, AFAIK adversarially chosen d is outside the
target adversarial model for MLS.

- Joël



[1] https://mailarchive.ietf.org/arch/msg/mls/y5ikXqQh7VAojXrNSt9odxgNVmE
[2] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[3] https://www-users.cs.umn.edu/~hoppernj/basic-proof.pdf


On Tue, 5 Nov 2019, 04:08 Watson Ladd, <watsonbladd@gmail.com>; wrote:

>
> On Mon, Nov 4, 2019 at 6:53 PM Richard Barnes <rlb@ipv.sx>; wrote:
>
>> Hi CFRG folks,
>>
>> This draft is a proposal to address a deficiency in X25519 and X448 that
>> has been noted a couple of times on this list (e.g., [1]), namely the fact
>> that multiplication of scalars and point multiplication do not commute.
>> While looking into applications of updateable public-key encryption in the
>> context of MLS [2], my co-authors came upon a solution that while not
>> perfect, works in all but a statistically insignificant number of cases.
>>
>
> If you have a ladder that doesn't require the high bit to be in any
> particular place, then you're fine.  What's the application where you
> cannot modify the implementation to compute n*X for any n, not just one of
> a particular length? Secondly the calculation assumes d uniformly random:
> but if d is say 2, then whether or not the generation fails is entirely
> dependent on the second bit of y if we write sk=2^254+8y, as 2*sk is
> 2^255+8*2*y, which if it's in the fail range proves y<x/2, which is true
> for about half the possibly y if I understand the notation correctly. What
> I don't know is if you can do this again, and extract another bit, and
> another, etc.
>
>
>
>> The draft describes how to do scalar multiplication in a way that is
>> compatible with point multiplication in the X25519 and X448 groups,
>> describes the cases where these algorithms can fail, and provides methods
>> for detecting failure.  While "move to Ristretto" is also a solution to
>> this problem, it seemed like a solution for X25519 / X448, even if partial,
>> might have a slightly faster path to deployment.
>>
>> As with any -00 draft, feedback is very welcome!  If Go is your preferred
>> medium, we've also implemented the relevant concepts in the corresponding
>> GitHub repo [3].
>>
>> Thanks,
>> --Richard
>>
>> [1]
>> https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ
>> [2] https://eprint.iacr.org/2019/1189
>> [3] https://github.com/bifurcation/draft-barnes-cfrg-mult-for-7748/
>>
>>
>> ---------- Forwarded message ---------
>> From: <internet-drafts@ietf.org>;
>> Date: Mon, Nov 4, 2019 at 6:44 PM
>> Subject: New Version Notification for
>> draft-barnes-cfrg-mult-for-7748-00.txt
>> To: Richard L. Barnes <rlb@ipv.sx>;, Joël Alwen <jalwen@wickr.com>;,
>> Sandro Corretti <corettis@gmail.com>;
>>
>>
>>
>> A new version of I-D, draft-barnes-cfrg-mult-for-7748-00.txt
>> has been successfully submitted by Richard L. Barnes and posted to the
>> IETF repository.
>>
>> Name:           draft-barnes-cfrg-mult-for-7748
>> Revision:       00
>> Title:          Homomorphic Multiplication for X25519 and X448
>> Document date:  2019-11-04
>> Group:          Individual Submission
>> Pages:          10
>> URL:
>> https://www.ietf.org/internet-drafts/draft-barnes-cfrg-mult-for-7748-00.txt
>> Status:
>> https://datatracker.ietf.org/doc/draft-barnes-cfrg-mult-for-7748/
>> Htmlized:
>> https://tools.ietf.org/html/draft-barnes-cfrg-mult-for-7748-00
>> Htmlized:
>> https://datatracker.ietf.org/doc/html/draft-barnes-cfrg-mult-for-7748
>>
>>
>> Abstract:
>>    In some contexts it is useful for holders of the private and public
>>    parts of an elliptic curve key pair to be able to independently apply
>>    an updates to those values, such that the resulting updated public
>>    key corresponds to the updated private key.  Such updates are
>>    straightforward for older elliptic curves, but for X25519 and X448,
>>    the "clamping" prescribed for scalars requires some additional
>>    processing.  This document defines a multiplication procedure that
>>    can be used to update X25519 and X448 key pairs.  This algorithm can
>>    fail to produce a result, but only with negligible probability..
>>    Failures can be detected by the holder of the private key.
>>
>>
>>
>>
>> Please note that it may take a couple of minutes from the time of
>> submission
>> until the htmlized version and diff are available at tools.ietf.org.
>>
>> The IETF Secretariat
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> --
> "Man is born free, but everywhere he is in chains".
> --Rousseau.
>