Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto

"Riad S. Wahby" <rsw@jfet.org> Thu, 25 July 2019 01:53 UTC

Return-Path: <rswatjfet.org@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 0725A12036D for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:53:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.558
X-Spam-Level:
X-Spam-Status: No, score=-1.558 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.091, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 bRW3rBfAhM3B for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:53:04 -0700 (PDT)
Received: from mail-pg1-f180.google.com (mail-pg1-f180.google.com [209.85.215.180]) (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 7805B1200B9 for <cfrg@irtf.org>; Wed, 24 Jul 2019 18:53:04 -0700 (PDT)
Received: by mail-pg1-f180.google.com with SMTP id t132so22122749pgb.9 for <cfrg@irtf.org>; Wed, 24 Jul 2019 18:53:04 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:content-transfer-encoding :in-reply-to; bh=Q1T9Mg8mWIkO0AkW+zYhmkDQ26UOnzdwc9pAUDwEyKk=; b=Rs12vdMbFxA/5vuM+3G4rT/TtxkwhNpBQYHeOrK21IKRuqlP8YO2x3i5iXOtHT9I1P HRNbvlX1iYMC/b6o6Ejn01LAwTBTf/kDFvu3ZKBBaBqi0bjfJfyqn5ZJGOMQf7L/j/QU p/zK0I2H3nQRXTc4nF4ynHWEy4pCVa42rwJ9P6VB2mQiWOgiugpA+GRTPShmYkI4O/Ew bE7DjK4Nx0mhdIEMIddM51In26Ddj9SPMK+I6gyV/h+1alxDy2+04UF6ggZM72vnG4cl 4NqbTHgnhpot20ovPcIqL4bkVHIhNtbGeqbPir7kf68HcLUHAFb0l2yexrq3mITsvnRu mNNQ==
X-Gm-Message-State: APjAAAXiwE2FVcl2qKAgZgpcsVaohakJYdDqj+Uq04xp8Tt6XpFGV7QB RxMI6rNWIWKQM1w6reGg9lHFZhDh
X-Google-Smtp-Source: APXvYqwD4CQRP74jOlObC18H7prEfWvihrMy9Io0XPBgBmWg5vwzqLyH2h5r2evWIT889Cxau70L8Q==
X-Received: by 2002:aa7:8a97:: with SMTP id a23mr13913517pfc.117.1564019584069; Wed, 24 Jul 2019 18:53:04 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id f15sm31350286pgu.2.2019.07.24.18.53.00 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 24 Jul 2019 18:53:02 -0700 (PDT)
Date: Wed, 24 Jul 2019 18:52:59 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: Filippo Valsorda <fv@filippo.io>
Cc: Jack Grigg <ietf@jackgrigg.com>, Jeff Burdges <jeff@web3.foundation>, cfrg@irtf.org, draft-hdevalence-cfrg-ristretto@ietf.org
Message-ID: <20190725015259.betglszxmwpgg7q7@positron.jfet.org>
References: <a505c99b-32a9-447a-9c69-a8efe3ed1b70@www.fastmail.com> <0370cd6b-adf3-4be2-9ab4-79693b9dc096@www.fastmail.com> <B7F73174-29F0-4B83-8AC0-A7D42D372D4A@inf.ethz.ch> <075d43b1-e123-42a9-ccd9-64fe45306f8b@web3.foundation> <20190724212030.ddcswlg5uxm3muzo@positron.jfet.org> <CAPC=aNVCV2cn62rhQsu+RsJsdjt2Dqqw_rqooLsuc8J5v9s3kQ@mail.gmail.com> <20190725004633.l5k7toldcgy7uthb@positron.jfet.org> <a391f8d5-c4c4-4650-9392-860864543198@www.fastmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <a391f8d5-c4c4-4650-9392-860864543198@www.fastmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/WjlYkCpAkooMQy8VTEliDWklxa8>
Subject: Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto
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: Thu, 25 Jul 2019 01:53:06 -0000

Hello Filippo,

Thanks for the email. Answers inline below.

Filippo Valsorda <fv@filippo.io> wrote:
> RSW wrote:
> > OK, but this can't actually be true, because there are other operations
> > alluded to (but not defined) in the document, and without those
> > operations (point addition, point inversion, scalar multiplication)
> > ristretto255 doesn't actually let me do anything.
> 
> The critical section here is Section 3.3 of -01, which reads
> 
> > 3.3.  Operations on internal representations
> >
> >   Group addition, subtraction and (multi-)scalar multiplication are
> >   performed without modification using the internal representations.
> >
> >   Implementations MUST NOT perform any other operation on internal
> >   representations.

Right, this is what is "alluded to" (self-quote above).

The problem, simply put, is that the document does not define how to
do these operations.

(Also: inversion, subtraction, either's fine.)

> The main challenge that we'd appreciate wording help with is that
> of defining the behavior of the group normatively through the example
> of its edwards25519 implementation, while making it clear that the
> edwards25519 internal representatives are an implementation choice,
> and must not be directly generated nor accessed, in order to make
> alternative implementations possible.

I'm super duper willing to help. I want this document to succeed.
But I cannot help when the document as it stands cannot be parsed
except by its authors and/or without some educated guessing.

> I want to mention that there is inherent value in clearly
> defining the public API surface of a cryptographic primitive

Totally agreed! I want to be crystal clear, this is not my complaint.

> We believe sections 3.2 and 3.3 provide all operations necessary to
> implement the "prime order group" interface (and if not, we should
> specify the missing ones).

Here is the problem: Sections 3.2 and 3.3 *do not* provide those
operations. For example, the document does not indicate how to perform
point addition, because nowhere in the document is it made clear that
the output of DECODE as defined in Section 3 is an edwards25519 point.

> (Notwithstanding the fact that someone who read the Decaf paper like
> you might indeed make safe abstraction breaches—modulo alternative
> implementation compatibility. The point is that we are designing a
> primitive that aims to be misuse resistant because it neither requires
> nor allows such attempts.)

I promise, I really don't want to break the abstraction! I'm asking
these questions to try and triangulate what the document and the
claims in this thread mean, because right now it's totally unclear.

Again, thank you (all) for your patience with my questions,

-=rsw