Re: [Cfrg] Call for adoption: draft-hdevalence-cfrg-ristretto-01

Alex Davidson <alex.davidson92@gmail.com> Mon, 30 September 2019 11:37 UTC

Return-Path: <alex.davidson92@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 0A93A12022C for <cfrg@ietfa.amsl.com>; Mon, 30 Sep 2019 04:37:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.748
X-Spam-Level:
X-Spam-Status: No, score=-1.748 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no 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 OurIIYz5xdSY for <cfrg@ietfa.amsl.com>; Mon, 30 Sep 2019 04:37:08 -0700 (PDT)
Received: from mail-vs1-xe2a.google.com (mail-vs1-xe2a.google.com [IPv6:2607:f8b0:4864:20::e2a]) (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 87AB912021D for <cfrg@irtf.org>; Mon, 30 Sep 2019 04:37:08 -0700 (PDT)
Received: by mail-vs1-xe2a.google.com with SMTP id b123so6506380vsb.5 for <cfrg@irtf.org>; Mon, 30 Sep 2019 04:37:08 -0700 (PDT)
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=/9Ei9fKnpwDDHw5yne9bD425dSUzh24lRiJTHeCuUz8=; b=IPhi1/sjb3tV3d8vK9VnA9CeLoKtPvo2R5yafTu+HRAsaBjM97vC7LMoHnD3AUSDVw VRrc1xDnyVPslcE50XcaX1F7CIOcq3jaeuFSqvc8wqM0whJHr4Ga1+545ll+M85poG5p lFfMT7YzjufCQSpp/KgJHsnoMubheYV2IcVQF2TIZ2DFd3hzzEE65vYeTLUQ1FSt3dgT sIvl9uQ61JeVoxw25bTn751w4O1wPBuhopBSdoQIxn/ESLESvkO91Ymf/xPkLD2tmSxz 2gk/4CqE2RYCT4bfpYZECHFmLokiOMT9SjRLRR+jXQUiuhW65rSeqRzxuXu6ioXhWX+f xThw==
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=/9Ei9fKnpwDDHw5yne9bD425dSUzh24lRiJTHeCuUz8=; b=F3zok8O+nwbaqW+c1En1b8OqaouEkfIMbGBRssi+ag2XJkuVhhlQxt+DSGPEIPrW9N or3b6ZqiC8BXcCAJ8estrtN9Zc4NR94Vkv/rBBJEHJBH5cRQeDtZpUXqLe9MPSmZssX0 Igiq9/+QqRShO55/pZaU8/b7iD1mkNL6myoG4Etks8dEkHyLRuFO56KgTidnyVvu5GAC hz0lcd/WGh9kiWD4NjM4PP2QOHUEn/4o4lbmYKLQNVMTG2OiFoLG+iTNjDmDApFTRjlb fiGh4CErwUsPXNLZLrpJ8SrLSbZvTTQfXP3BmJVd6g4mdwsosfI2H/TW5gFz+q55wS9V tkfw==
X-Gm-Message-State: APjAAAUfiiBPCxUWq9gKINfIvPGdgGaZ0k/3wuL4wp+R/kzbFlg8eIDP /TjGNq96mRHP+aLER95l+d4gcFvpK8qhlkbvXe7WtgEZEA==
X-Google-Smtp-Source: APXvYqzh9QvXVhi92fELeL/OS7oFJ31va/YyIN6/QrGjT+sVrNNr1OCcMtM5y/Ib3h9r4Ff6xQ+ASrJhvTL0S/ZgB5c=
X-Received: by 2002:a67:d594:: with SMTP id m20mr9728834vsj.144.1569843427494; Mon, 30 Sep 2019 04:37:07 -0700 (PDT)
MIME-Version: 1.0
References: <e43c34da-1e2c-d1b5-9fc1-5bcc8373ebc8@isode.com> <CAL02cgQorNKVrOPvqZQtDQNK-F0nH_dwj3i39zadkBKM1O0U5A@mail.gmail.com> <161fc653-2cab-4c6d-812b-92d2e426719d@www.fastmail.com> <6be1dbd1-308c-4e32-98e3-f02dbceefa4d@www.fastmail.com>
In-Reply-To: <6be1dbd1-308c-4e32-98e3-f02dbceefa4d@www.fastmail.com>
From: Alex Davidson <alex.davidson92@gmail.com>
Date: Mon, 30 Sep 2019 12:36:56 +0100
Message-ID: <CAD5V+fPL+OAoQu_emTSULvv=-hUsrQx97y-7EoeKsfoXH=NTbA@mail.gmail.com>
To: Filippo Valsorda <filippo@ml.filippo.io>
Cc: cfrg@irtf.org, draft-hdevalence-cfrg-ristretto.authors@ietf.org
Content-Type: multipart/alternative; boundary="000000000000d950bd0593c3a7d1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/R5z1Guhm2BVf6msWWycVM8XjDj4>
Subject: Re: [Cfrg] Call for adoption: draft-hdevalence-cfrg-ristretto-01
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: Mon, 30 Sep 2019 11:37:10 -0000

I would like to include my support for the adoption of this draft. From the
perspective of the ongoing effort for standardising the construction of
OPRFs in
prime-order groups (draft-irtf-cfrg-voprf-01), the abstraction of the
elliptic
curve interface made by Ristretto is much more preferable than interacting
with
Curve25519-type curves directly. In particular removing the necessity to
check
whether points are actually defined in the prime-order group, which is a
frequent source of errors.

Apart from this, I have a few points about how certain aspects of this
draft may
have implications for the OPRF use-case going forward.

Firstly, it has been noted recently that OPRFs can be used to instantiate an
oracle for constructing q-Strong-DH samples [1]. This leads to attacks that
can
reduce security by up to log_2(m) bits where m queries are made [2,3]. A
future
OPRF draft will address this by declaring ciphersuites with curve choices
that
provide > 128 bits of security. With this in mind, it would be useful if
Ristretto groups could also be defined for curves with larger security
parameters (such as providing an interface for Curve448). I'm not sure if
this
is a direction that is currently being considered?

Secondly, and to add to the discussion on the FROM_UNIFORM_BYTES API, I
agree
that it would be useful to refactor some form of this functionality to
match the
expectations set out in the hash-to-curve draft. This would then provide a
single point of reference for developers/other drafts to implement moving
from
bytes to group elements. However, my concern is that if the API remains as
it is
specified in the current I-D, then this may rule out valid applications of
OPRFs
where the input bytes are not uniformly distributed. If the only way to move
from bytes to a Ristretto group is to use the FROM_UNIFORM_BYTES function,
then
this means that we would have to define a separate interface for Ristretto
ciphersuites in the OPRF draft for extracting random bytes from potentially
non-uniform inputs. If so, this will produce somewhat incompatible
Ristretto and
non-Ristretto ciphersuite configurations, which is something that we may
want to
avoid going forward.

For the second point, there is a possible solution in defining a FROM_BYTES
API
function as part of the Ristretto interface. This would take non-uniform
bytes,
transform them to uniform bytes, and then invoke FROM_UNIFORM_BYTES on the
output of this transformation. For ristretto255 it would be fine to use
SHA512,
but if we want to support larger groups then this would not be enough. In
these
cases, it would be necessary to use something like HKDF_Expand to expand the
output of SHA512 to the appropriate level. This sort of transformation would
also be valid in ristretto255, and would appear to be quite similar to the
hash_to_base function defined in the hash-to-curve draft.

With the above in mind, it could be worth realigning the Ristretto point
encoding mechanism around hash-to-curve by running hash_to_base and then
calling
an appropriate hash_to_curve method for producing similar outputs to those
given
by FROM_UNIFORM_BYTES. Since these outputs appear to be even Edwards points
(unless I'm mistaken), then this could potentially be achieved by running
edwards25519-SHA256-EDELL2-RO and then doubling the output point?

Happy to discuss these points further.

Thanks,
Alex

[1]: http://ai.stanford.edu/~xb/eurocrypt04a/bbsigs.pdf
[2]: https://eprint.iacr.org/2004/306
[3]: https://www.iacr.org/archive/eurocrypt2006/40040001/40040001.pdf