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

From: Greg Hudson <[email-masked]>
Date: Wed, 2 Oct 2019 12:49:50 -0400

[I wrote:]>>     Hashing non-uniform inputs does not produce uniform outputs
On 9/30/19 2:20 PM, Alex Davidson wrote:
> I should have made it more explicit here that I'm assuming that the
> initial hash
> function evaluation is modelled as a random oracle.

The output of a random oracle (instantiated once globally) on
non-uniform inputs is not uniform, in the sense of all values being
equally likely.  For example, if "mypassword" is a thousand times as
likely as any other input, then H("mypassword") will be roughly a
thousand times as likely as any other output.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 2 Oct 2019 17:02:26 +0000

On 10/2/19, 12:50 PM, "Cfrg on behalf of Greg Hudson" <[email-masked] on behalf of [email-masked]> wrote:
    >> initial hash function evaluation is modelled as a random oracle.
    >

Which is no different from, e.g., a block cipher in ECB/codebook mode. Which often enough is modeled as Random Oracle, regardless.

---

From: John Mattsson <[email-masked]>
Date: Mon, 7 Oct 2019 15:12:35 +0000

Hi,

I think this is a useful and well-written draft, and I support adoption.

A minor editorial comments. I think the draft should be more aligned more with the terminology in RFC7748 and RFC 8032. The document talks about "Curve25519" and refers to RFC 7748, but RFC 7748 defines the Montgomery curve "curve25519" and the twisted Edwards curve "edwards25519". If I understand correctly, the draft requires an edwards25519 implementation.

Cheers,
John

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 7 Oct 2019 18:08:33 +0100

Dear CFRG Participants,

On 18/09/2019 17:44, Alexey Melnikov wrote:
> Dear CFRG participants,
>
> This email commences a 2-week call for adoption for 
> draft-hdevalence-cfrg-ristretto-01 that will end on October 2nd 2019:
>
>  https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/
>
> Please give your views on whether this document should be adopted as a 
> CFRG draft, and if so, whether you'd be willing to help work on 
> it/review it. Please reply to this email (or in exceptional 
> circumstances you can email CFRG chairs directly at 
> [email-masked]).

Based on the mailing list feedback chairs declare that this draft is 
successfully adopted by CFRG. Authors should submit a new version and 
reply to comments raised during the adoption call.

Thank you,

Alexey (for the chairs)

---

From: "Filippo Valsorda" <[email-masked]>
Date: Wed, 09 Oct 2019 17:25:09 -0400

Glad to hear the group decided to adopt the draft, thanks to everyone
who commented and offered feedback.

We are working on draft-irtf-cfrg-ristretto-00 to address the various
comments that came up during and before the adoption call.

I definitely agree that there should be a standard path from non-uniform
inputs to ristretto255 points, and after some experimentation I
am fairly convinced the best solution is for hash-to-curve to
define the input processing (as well as the domain separation)
homogeneously with the other target curves, and then use the
ristretto255 FROM_UNIFORM_BYTES API as the abstraction point. This way
hash-to-curve users will be presented a uniform API, and ristretto255
internal types won't leak into neither the hash-to-curve spec nor its
implementations.

After -00 is ready we'll also look into how much extra work it would be
to add Decaf to the spec. I agree that whether it's a good idea depends
on how much extra complexity it brings in.

2019-10-07 13:08 GMT-04:00 Alexey Melnikov <[email-masked]>:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 25 Oct 2019 11:25:46 -0700

> internal types won't leak into neither the hash-to-curve spec nor its

Hi Filippo,

I'm glad that Ristretto is moving forward, and I eagerly await its
widespread use :)

As we're prepping hash-to-curve-05, one of the changes was to ensure
that the hash function from arbitrary strings to the base field has
an indifferentiability proof and that the domain separation design
is conservative. In doing so, I've become (more) convinced that this
is something that is easy to get subtly wrong, and that we should do
as much as possible to encourage carefully vetted solutions.

With that as backdrop, I'm a bit nervous about the FROM_UNIFORM_BYTES
API. Specifically, I worry that this API will encourage implementors
to cook up ad-hoc methods of turning strings into "uniform" bytes.
As one (possibly simple-minded) example, I worry that even the name
of the API is misleading, because in almost all cases uniformity is
not really enough. Meanwhile, FROM_INDEPENDENT_UNIFORM_BYTES starts
sounding a little ridiculous, and isn't yet exhaustive... :)

Here's one possible course of action:

1. Remove the function that takes uniform bytes and replace it with
   one that takes an element of the base field. Let's call this the
   MAP function.

2. As you said in your email, recommend (or even require) the use of
   hash_to_base (Section 5 of hash-to-curve) to produce the input to
   the MAP function.

3. Define a new hash-to-curve suite based on MAP. I don't know whether
   this should live in hash-to-curve or Ristretto, but I tend to think
   the latter.

4. Define MAP in terms of the Elligator 2 map in hash-to-curve, with
   the goal of allowing code reuse and minimizing redundancy between
   the two documents. (I realize that this is a contentious request.
   I make it again because I'm still convinced this is both possible
   and a good idea. If you think it's not, can you please explain in
   detail why not? All the past explanations I've seen have been too
   vague to be convincing.)

Even if (4) really is impossible, (1)-(3) still look to me like they
would help avoid confusion and steer implementors towards safe choices.

Looking forward to working with you on this,

-=rsw

---

From: "Filippo Valsorda" <[email-masked]>
Date: Fri, 25 Oct 2019 20:14:44 +0100

> sounding a little ridiculous, and isn't yet exhaustive... :)

Hi Riad,

Thanks for getting in touch about the hash-to-curve integration.

As far as I understand, you have concerns about two parts that feel
independent to me:

(a) the conversion from uniform bytes to the field element—this is
defined in the draft, so if you think there is an issue with it, please
let us know so we can address it;

(b) the generation of uniform bytes by the application—of course we
want to make sure this is not hard to get right, so can you share what
kind of issues we should be thinking about, based on your work on
hash-to-curve? Would SHA-512($STRING) be sufficient? We were already
planning to recommend (RECOMMEND, if you feel it would be appropriate)
to use hash-to-curve for domain separation purposes, so there is a
standard and vetted way to do it.

Again, we care about maintaining the abstraction of ristretto255
as nothing else than an abstract prime-order group, and abstract
prime-order groups don't have a base field, that's an implementation
detail that should not leak through the API. Integrating hash-to-curve
on top of FROM_UNIFORM_BYTES also maintains some compatibility between
the existing deployments which already use FROM_UNIFORM_BYTES and the
RFC.

>    detail why not? All the past explanations I've seen have been too

Multiple people made different arguments about this, but mine is
simple: there should be hash-to-curve libraries, and there should be
ristretto255 libraries. The ristretto255 libraries MUST NOT expose the
underlying curve points because it's an abstraction breach, because
it's encouraging implementors to do unsafe operations, and because
it makes interoperability with ristretto255 implementations based on
an alternative curve impossible. If the ristretto255 libraries don't
expose those internals, though, there is no way for hash-to-curve
libraries to do (4) without being one and the same, and I don't see why
a hash-to-curve library should be forced to implement ristretto255 and
vice-versa.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 25 Oct 2019 13:19:27 -0700

Hi Filippo,

Thanks for the email. Responses inline.

> let us know so we can address it;

There aren't any technical issues that I can see---the bias seems fine,
etc. The issue is what I said in my prior email: having an interface
like this seems likely to encourage incorrect usage, because the
requirements for secure use are left as an exercise to the reader.

As a concrete worry, imagine that I naively sample 64 random bytes
from which I'll derive my secret key. I also need a group element, so
I pass those same 64 bytes to FROM_RANDOM_BYTES. Oops, now security
depends on an unstated assumption about the difficulty of inverting
the sum of two Elligator mappings, rather than on an explicit and
well-understood assumption like first-preimage resistance of SHA-2.

(Sure, this is plausibly hard to do, but that's besides the point.
My naivete combined with an underspecified interface has introduced
a subtle defect in existing security proofs. Indeed, this defect may
interact with other defects in my implementation. Complex systems
fail in complex ways.)

> standard and vetted way to do it.

In some applications, SHA-512(string) might be sufficient, but it
would not be a good recommendation because it's easy to imagine
applications for which it's certainly *not* sufficient.

The domain separation in hash-to-curve enters in the hash_to_base
function (Section 5 of hash-to-curve draft), whose signature is

    {0,1}* -> F

for F the base field of the target curve. This is not compatible with
the FROM_UNIFORM_BYTES interface. (In my mind, this is another reason
to abandon that interface.)

> detail that should not leak through the API.

That's fine, but in what I'm suggesting it wouldn't leak through the
API because there would be no exposed function going from the base
field to the abstract group.

The confusion here is my fault, because my prior email was unclear.
The MAP function I mentioned should *not* be considered part of
the external API. Rather, it's an internal function that's used,
together with hash_to_base, to produce the public API function (say)
FROM_STRING, which could be defined similarly to the hash_to_curve
function (Section 3 of hash-to-curve draft):

def FROM_STRING(str):
    t1 = hash_to_base(str, 0)   # returns element of F
    t2 = hash_to_base(str, 1)   # returns element of F
    p1 = MAP(t1)                # returns element of group
    p2 = MAP(t2)                # returns element of group
    return p1 + p2              # group addition law

(Note that the domain separation tag is an implicit parameter of
hash_to_base.)

It's obvious that mechanically the above works, since it is very
similar to what FROM_UNIFORM_BYTES is currently doing---and indeed,
in spite of the lack of a base field, somehow r0 and r1 in the current
FROM_UNIFORM_BYTES definition are exactly elements of the field GF(p),
and the MAP function goes from an element of F to a group element!
(So I'm not sure how to make sense of the objection that abstract
prime-order groups don't have a base field.)

> Integrating hash-to-curve on top of FROM_UNIFORM_BYTES also maintains
> some compatibility between the existing deployments which already
> use FROM_UNIFORM_BYTES and the RFC.

As I said above, right now there is no compatible interface between
hash-to-curve and FROM_UNIFORM_BYTES.

If somehow we completely fail to come to any understanding of how to
combine hash-to-curve with Ristretto, I'd recommend making the current
FROM_UNIFORM_BYTES function private and instead exposing a FROM_STRING
function of the following form:

def FROM_STRING(str):
    b = HMAC-SHA512(DST, str)       # DST is the domain separation tag
    return FROM_UNIFORM_BYTES(b)    # current FROM_UNIFORM_BYTES

Aside: to my knowledge there is generally no assumption in CFRG
working drafts that edits must not break existing deployments. It's
nice if breakage can be avoided, but it's not a good reason to keep
a bad interface.

> an alternative curve impossible.

Sorry, to clarify: I'm proposing that MAP is not an external interface,
so defining it in terms of the existing Elligator 2 description in
hash-to-curve would not have the effect of breaching any abstractions.

Anyway, the current version of MAP is certainly defined in terms of
Elligator 2 operating on concrete curve points. So I don't understand
how to differentiate between my proposal (bad?) and what's currently
there (good?).

Can you please be more specific about the issue here?

> If the ristretto255 libraries don't

I don't see how this is germane to the discussion. I am asking about
whether MAP can be defined in terms of the description of Elligator-2
given in hash-to-curve. I'm not (yet) thinking about implementations,
code sharing, etc. Let's discuss one thing at a time.

Regards,

-=rsw