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

["Riad S. Wahby" <[e-mail]>]

Hi Filippo,

Thanks for the email. Responses inline.

Filippo Valsorda <[e-mail]> wrote:
> 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;

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.)

> (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.

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.)

> 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.

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.

> 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.

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
> 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.

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