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

Watson Ladd <watsonbladd@gmail.com> Tue, 05 November 2019 03:08 UTC

Return-Path: <watsonbladd@gmail.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 6EF09120073 for <cfrg@ietfa.amsl.com>; Mon, 4 Nov 2019 19:08:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, 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=gmail.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 h9Yxzmby8dG2 for <cfrg@ietfa.amsl.com>; Mon, 4 Nov 2019 19:08:10 -0800 (PST)
Received: from mail-lf1-x134.google.com (mail-lf1-x134.google.com [IPv6:2a00:1450:4864:20::134]) (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 DD98312006F for <cfrg@ietf.org>; Mon, 4 Nov 2019 19:08:09 -0800 (PST)
Received: by mail-lf1-x134.google.com with SMTP id v8so13834801lfa.12 for <cfrg@ietf.org>; Mon, 04 Nov 2019 19:08:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=gWRCMKpqO1tHxGqn050QhQ+iMsrMO2rG1JG/rxL/akg=; b=rAvaJb2fnJ9G2KMcN5iLKawo/0NyPKPqL2D/HbjVvFPtOZ3Jxw04d8FCT3lOYECa6f 5eDW8MhuezxSPSKyvITHXZFV8y2Yj9adLpqeP6+4NSZeCBXGaZaebDsfFqKQCee3Yn5Y hVeOA/yqC54ldnMtp+4pZvESIoRREE1mFZ1eBMM7jnnemXcYoKe83uI9fsQCYUSltnl+ CyQK65aEkkoFntJObY0i3djpKQZuyEDAH8ViVG1T95AY48IatstwZvHWYDqfJ79ntFWy PrMOim4tU6gj/CcA/suOTDpOFYB+L22zYKy2tLt8QxsyNG3eHICwrKo0XIm+pcPZ3oVQ fQKQ==
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=gWRCMKpqO1tHxGqn050QhQ+iMsrMO2rG1JG/rxL/akg=; b=K6roHWJcQpyd54x+eZKBWb3AFeQHjy7hKoDpPF+sbrPFHJwrG7Ikvx5ixaK20jtbuM hTKDKKcuoJovkmGim4sKRQ9YIdUtv5al715tFCgWbWYD594xwuU0h0OVkIg8rxnHqfYs NtxXmF2MtomJ0DR3jOfA4uR/DHtrRjX61myw2aEKZ/cW2xhkGWbToFSwiIDoyXoICAff HZeLni3S19RaloeqJojmwoJvS3AE+vQRM+qsA3l6qjigOC7Ekvzx/xZlr7nX/V3vvJ74 KGMccPgmHEi/5xLXxOsXENDrqvCL1FYfp/0EP5feN3TYP44oWBsBmhVWu/9R2c6vojq7 zb/A==
X-Gm-Message-State: APjAAAWptSpY1iKwP0LSuPAeuxOpOVSs4pXoOHhJn72iL08meJF0SBkg BnxmPACv5cihCRY7Ki6YTpyUXF0EwbO2PrtMUgc=
X-Google-Smtp-Source: APXvYqyDt+7Z6YqG/HHKfnQVibDK7xMiAuo7ODx2vqOON7mH/5LsB1cBlec93TQv4seFbdB7xu3wq41TKjKSq9ON7ow=
X-Received: by 2002:a19:40cf:: with SMTP id n198mr18944839lfa.189.1572923287869; Mon, 04 Nov 2019 19:08:07 -0800 (PST)
MIME-Version: 1.0
References: <157291108173.13892.5112993721217644254.idtracker@ietfa.amsl.com> <CAL02cgSgLaU4VMqnzvFyr_v3vErdc_mv5=E_gjgAofa2dmGg2w@mail.gmail.com>
In-Reply-To: <CAL02cgSgLaU4VMqnzvFyr_v3vErdc_mv5=E_gjgAofa2dmGg2w@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
Date: Mon, 4 Nov 2019 22:07:56 -0500
Message-ID: <CACsn0cn7dvgWg59FXBdH+YP9iaDbR9=MfJuzAh4hAOeadpRNuA@mail.gmail.com>
To: Richard Barnes <rlb@ipv.sx>
Cc: cfrg@ietf.org, Sandro Coretti <corettis@gmail.com>, Joel Alwen <jalwen@wickr.com>
Content-Type: multipart/alternative; boundary="000000000000d520a7059690bd90"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/6KLEoOoKXVvJRhxgu_ggV9IdXj0>
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 03:08:13 -0000

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.