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

[Henry de Valence <[e-mail]>]

(resending under IETF alias address)

Hi all,

Thanks for the detailed comments, Riad.  I'm not currently subscribed
to this list so I hope I will be forgiven if I missed any comments
which were not addressed to me, as well as for responding to points
made in various emails all at once instead of individually.

First, here are some comments on points made in the preceding
discussion, followed by comments on Riad's proposal.

I will annotate some possible clarifications with capital letters (A),
(B), (C), etc., and compile them into a list at the end.

Riad S. Wahby <[e-mail]> wrote:
> First, the text of section 1 makes repeated reference to Edwards
> curves, but the document deals with a Montgomery curve (and, per the
> above, explicitly *does not* deal with an Edwards curve)---and the
> word Montgomery *never appears in the document*! Of the curves are
> equivalent, but the document should be intelligible even to readers
> who don't instantly recall this fact. I'm happy to suggest specific
> (likely minor) edits to the intro to help clarify this point.

The text of section 1 makes reference to Curve25519, meaning the
abstract elliptic curve, following the naming scheme posted to this
list by its designer five years ago [1], and referenced on the second
line of its Wikipedia page [2].  That email suggests using
"Curve25519" to refer to the underlying elliptic curve, "X25519" and
"Ed25519" to refer to particular DH and signature schemes using that
curve, and names for various coordinate systems found in the
academic literature.  Our draft follows this terminology.

The reason the word Montgomery never appears in the document is that
the document explicitly deals with Edwards coordinates for Curve25519,
as described in Section 2, "Notation and Conventions
Used In This Document":

> Elliptic curve points in this document are represented in extended
> coordinates in the (x, y, z, t) format [Twisted].

where [Twisted] is a reference to the HWCD08 "Twisted Edwards Curves
Revisited" paper which defined them.

We could (and probably should) add an explicit note to this section
that "Curve25519" refers to the abstract elliptic curve (A), if that
would help clear up confusion.  However, the source of that confusion
is ultimately the decision to use the same name for an X-coordinate DH
system and its underlying (abstract) elliptic curve, and then to amend
terminology a decade later, and resolving it completely is out of
scope for our draft.

Riad S. Wahby <[e-mail]> wrote:
> The problem is, the document as currently written does not tell me
> how to implement the (+) operator on the third line above. It implies
> that such an operator exists (in Section 3.3), but as far as I can
> tell it does not tell me what it is.

The document does not define elliptic curve addition, because, as
described at the beginning of Section 3, "This document describes how
to implement the ristretto255 group using Curve25519 points as an
internal representation".

The document does describe how to implement the (+) operator, in
Section 3.3, which reads in its entirety: "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."

> Is it edwards25519 point addition?

Yes, as described in Section 3.3, quoted above.

> If so, then I just don't see how it can be true that the "internal
> representation" in Section 3 is not an edwards25519 point.

Yes, the internal representation is a Curve25519 point.  However, what
Jack said is "any mapping from ristretto255 elements", and a
ristretto255 group element is not the same as its internal
representation, as Watson alluded to.

The draft notes in Section 2 that "Each group element can have
multiple equivalent internal representations", and also in Section 4
that "ristretto255 elements are represented by curve points, but they
are not curve points ... the type ... SHOULD be opaque."

We can of course add an more explicit note in Section 2 that
ristretto255 group elements are not the same type as their internal
representations (B) if this was unclear.

Riad S. Wahby <[e-mail]> wrote:
> Here's my current best guess: ENCODE and DECODE convert ristretto255
> points into some internal representation.
>
> For the algorithms in
> Section 3, that internal representation is edwards25519, except that
> equality testing is different (specifically, it must use EQUALS) and
> maybe some other things are different (but I don't know what).
>
> Operations are the same as for edwards25519, but the only ones that
> are allowed are addition, inversion, and multiplication.
>
> Implementors can maybe use a different internal representation. There
> is no obvious way to do this given the information in the document.

I don't think any guessing is required here, because all of these
points are described fairly explicitly in the draft already.

The ENCODE and DECODE functions are described on page 2 of the draft:

> *  "ENCODE", an encoding function from internal representations to
>    bytestrings so that all equivalent representations on the same
>    ristretto255 element are encoded as identical bytestrings;
>
> *  "DECODE", a decoding function from bytestrings to internal
>    representations with built-in validation, so that only the
>    canonical encodings of valid ristretto255 elements are accepted;

The provided (and allowed) operations are described on the following
paragraph, and again in Section 3.3.

And indeed, there is no obvious way to use a different curve given the
information in the draft, which is also described on page 2:

> It is also possible and allowed to implement ristretto255 using a
> different elliptic curve internally, but that construction is
> out-of-scope for this document.

Riad S. Wahby <[e-mail]> wrote:
> In particular, there is no group isomorphic to Curve25519 with order l,
> because Curve25519 has order 8 * l.

The requirement is that the "isomorphic group" provided by an
implementation is isomorphic to the ristretto255 group, not to
Curve25519, so this is not an obstruction.  (The referent of "they" is
"implementations", but we can make the sentence more explicit that the
isomorphism is to the ristretto255 group (C) since it seems to have
been unclear).

And of course, ristretto255 is not isomorphic to Curve25519, for the
reason you mention.

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

I think this is made clear throughout the draft for all the reasons
mentioned above (modulo adding an explicit note (A) that Curve25519
refers to the abstract elliptic curve).

Riad S. Wahby <[e-mail]> wrote:
> Sorry, I don't understand this. edwards25519 points *are* valid
> internal representations.

No, not all Curve25519 points are valid internal representations.
Valid internal representations are representations constructed via the
DECODE and FROM_UNIFORM_BYTES functions, as mentioned in paragraph 3
of Section 4 ("implementations ... MUST NOT construct group elements
except via...") and described in detail in Section 6:

> There is no function to test whether an elliptic curve point is a
> valid internal representation of a group element.  The decoding
> function always returns a valid internal representation, or an error,
> and allowed operations on valid internal representations return valid
> internal representations.  In this way, an implementation can
> maintain the invariant that an internal representation is always
> valid, so that checking is never necessary, and invalid states are
> unrepresentable.

The draft does not go into detail about criteria for validity because
it is written for implementors, and the functions-to-be-implemented
are carefully constructed so that invalid representations are
unrepresentable, so implementors don't need to worry about it.

Regarding the proposal, I have the following comments:

> 0. Define the term "internal representation" up front. Make clear
>    that it's a restricted version of an elliptic curve point that
>    is defined over some underlying curve, and that all operations on
>    intenal representations not explicitly allowed by the text of the
>    document are prohibited.

This is already defined up front in Section 2, "Notation and
Conventions Used In This Document".

> 1. Make the Section 3 implementations of ENCODE, DECODE, EQUALS, and
>    FROM_UNIFORM_BYTES normative, and clarify that the inputs to ENCODE
>    and EQUALS and the outputs of DECODE and FROM_UNIFORM_BYTES are
>    edwards25519 points that are "internal representations."

I don't understand how these implementations can be normative (an
implementation MUST implement them) without making a normative choice
of curve to use internally (which prevents an implementor from
changing the curve, as is currently explicitly allowed and which you
suggest in (3) below).

The *behaviour* of the encoding and decoding is already normative
(cf. the beginning of Section 3), and the provided test vectors ensure
consistency between the encoding and the group operation.

> 1.1. Clarify in the above that inputs to ENCODE and EQUALS MUST be
> internal representations; any other inputs are prohibited.  Also
> clarify that the only way to get an internal representation is from
> DECODE, FROM_UNIFORM_BYTES, or from a permitted operation applied to
> an existing internal representation.

We can repeat the definitions of ENCODE and EQUALS from Section 1 in
Section 3, and repeat the requirements from Section 4 and Section 6 in
Section 1 to make this even more clear, but I think these requirements
are already described fairly explicitly.

> 2. As now, forbid implementors from exposing any point that is an
>    internal representation.

Yes, I agree that this should remain in the draft.

> 3. Explicitly allow mapping any internal representation to any curve
>    isomorphic to edwards25519, and state that the output of any such
>    mapping remains an internal representation and thus subject to
>    all of these requirements.

The header of Section 3 already allows an implementor to use any curve
model they want internally, as long as it provides an isomorphic group
with the same byte encoding.

>    (List the edwards25519/curve25519 isomorphism as an example,
>    and direct the reader to the birational map in RFC7748.)

I would rather direct the reader (and list it as an informative
reference (D)) to the Ristretto notes linked in the document, which
explain in detail which other curves can be used internally and the
particular role that the birational map plays in the Ristretto
construction (see comments on 5 & 6 below).

>    I'd also get rid of the text in the Section 3 header that talks
>    about groups of order l, since edwards25519 is not such a group
>    and thus no group isomorphic to it is either.

The Section 3 header talks about groups of order l because
ristretto255 is such a group, and a compatible implementation provides
a group isomorphic to the one described in the document.

> 4. Explicitly allow addition, subtraction / inversion, and
>    multiplication on any point that is an internal representation.
>    These operations MUST be isomorphic to addition, subtraction /
>    inversion, and multiplication on edwards25519.

These operations are already explicitly allowed, and the group
operations are already required to match the ones specified in the
test vectors.  As noted in Appendix A.1, these test vectors encode
elements with a defined relation to each other in terms of the group
operation, so they test the definition of the group operation as well
as the definition of the encoding.

Since ristretto255 is not isomorphic to Curve25519 for the reason you
mentioned above -- they're different groups, one of which MAY be
implemented using the other -- I don't think it makes sense to define
anything in terms of isomorphism to Curve25519.

> 5. Explicitly state that any internal representation that is the
>    result of a sequence of mapping operations MUST be converted back
>    to edwards25519 internal representation via the inverse sequence
>    of mappings before applying the ENCODE or EQUALS function.

> 6. Explain that implementors MAY compose (e.g.)  DECODE/mapping,
>    FROM_UNIFORM_BYTES/mapping, reverse-mapping/ENCODE,
>    reverse-mapping/EQUALS, and similar into monolithic functions.
>    In other words, the idea isn't to dictate the structure of the code,
>    only the underlying algebraic properties.

I think these are already covered by the fact that their
implementations are not normative (cf. your suggestion 1), and the
Section 3 header.  Implementations using different curves internally
will presumably have different implementations of encoding and
decoding.

As explained in the Decaf paper, as well as the
https://ristretto.group website referenced in Section 1, Decaf and
Ristretto initially construct an encoding on a Jacobi quartic, then
transport that encoding along a 2-isogeny to one of a number of
possible curves which are used internally to actually perform group
operations.

Of course, this complexity only plays a role in the abstract
construction, *not* in the concrete implementation: these maps compose
into the simple formulas in the document, each of which fit into half
a page of ASCII spec.

An implementation which wanted to use a different elliptic curve
internally (say, the 4-isogenous "small-d, Ed448-style" Edwards curve
described on the Ristretto website and below) would have different
encoding and decoding formulas, because those formulas are obtained by
transporting the Jacobi quartic encoding along a different 2-isogeny.

In fact, the birational map you mentioned in suggestion 3 is already
used to construct the encoding given in the draft, by transporting the
Jacobi quartic encoding along a 2-isogeny to the Montgomery form of
Curve25519 and then along the birational map to the Edwards form, as
explained on the Ristretto website.

This construction places the Edwards form of Curve25519 (a "large-d,
Montgomery-style" Edwards curve) in the correct spot on the isogeny
graph, so that the Jacobi-Edwards 2-isogeny lands on a "small-d,
Ed448-style" Edwards curve, allowing an implementation of ristretto255
to use this curve, which is 4-isogenous to Curve25519 but has a
smaller (17-bit) Edwards d parameter, while retaining wire-compatible
(even for hash-to-group, as described below!) with implementations
which use Curve25519.

However, as described in Section 1, these details are out-of-scope:
"It is also possible and allowed to implement ristretto255 using a
different elliptic curve internally, but that construction is
out-of-scope for this document."

Instead, the draft, as written, has two goals:

1. To provide test vectors for the ristretto255 encoding, decoding,
group-operations, and from-uniform-bytes functions (Appendix A), which
provide sufficient rigidity that passing them enforces compatibility
between implementations, regardless of which curve is used internally;

2. To provide concrete formulas aimed at allowing implementors to add
support for ristretto255 to an existing Ed25519 implementation.  I
think that the speed with which a conformant ristretto255
implementation was added to libsodium following publication of the
draft is illustrative of its success with respect to this goal.

> 7. Make FROM_UNIFORM_BYTES incorporate edwards25519-SHA256-EDELL2-RO
>    by reference, and specify a DST (domain separation tag, see Section
>    5.1 and 5.3 of hash-to-curve), e.g., "Ristretto255-Hash".
>
> 7.1. Also, rename FROM_UNIFORM_BYTES to either FROM_BYTES or FROM_STRING,
> and remove the length and distribution requirements on the input.
> The hash-to-curve document handles the uniformity internally while
> ensuring that conforming usage meets relevant security requirements.
> There's no reason to make higher-level protocols reinvent the wheel.

I don't think this suggestion is a good idea, for a number of reasons:

1. edwards25519-SHA256-EDELL2-RO is not compatible with ristretto255, as
it does not produce valid internal representatives;

2. even if it did, ristretto255 implementations are not required to
use Curve25519 internally, so the hash-to-group method cannot be
defined in terms of Curve25519;

3. ristretto255 already provides a hash-to-group method, which is defined
so that implementations remain wire-compatible even when changing the
curve used internally, as noted in the Ristretto website and the Decaf
paper;

4. requiring use of a specific hash function is a layering violation,
as the definition of an elliptic curve should not depend on use of a
particular symmetric primitive.

The FROM_UNIFORM_BYTES function provides a generic hook which handles
all of the details specific to the ristretto255 group, whose input
uniformity requirement retains composability with various symmetric
constructions.  This isn't requiring higher-level protocols to
reinvent the wheel, but retaining compatibility with them.

For instance, why should a higher-level protocol that everywhere else
uses domain-separated SHA3 be forced to use SHA2 for hash-to-group?

Or, consider a protocol that uses a duplex construction to ensure that
hash output is not just bound to a single domain separator, but to an
entire message transcript with arbitrary application domain separation
messages (e.g., https://merlin.cool).  Why should it be forced to
launder its domain-separated hash output through a second HKDF
construction?

Of course, it would be most preferable to achieve compatibility
between the ristretto255 draft and the hash-to-curve draft.  But since
the hash-to-curve draft describes hash-to-curve methods for various
elliptic curve groups (P-256, secp256k1, Curve25519, etc), while this
draft is tightly focused on describing a specific group, it seems like
the cleaner layering would be for the hash-to-curve draft to
incorporate this draft by reference, and use this draft's
FROM_UNIFORM_BYTES function to define a

ristretto255-SHA256-RISTRETTO-RO

or similar (I'm not 100% confident in my understanding of your naming
scheme).

In this way, the hash-to-curve draft defines hash-to-curve methods for
various elliptic-curve-based groups (P-256, secp256k1, Curve25519, and
ristretto255), while the ristretto255 draft remains focused on
definining a single group and retains compatibility with other
symmetric constructions (e.g., sponge constructions).

Cheers,
Henry de Valence

(A): Clarify that "Curve25519" refers to the abstract elliptic curve,
as described in the references below.

(B): Copy the note that ristretto255 elements and their internal
representations are distinct types from Section 4 to Section 2.

(C): Clarify that the isomorphism is an isomorphism to the
ristretto255 group.

(D): Add the Ristretto website as an informative reference, not just
an in-body link.

[1]: https://mailarchive.ietf.org/arch/msg/cfrg/-9LEdnzVrE5RORux3Oo_oDDRksU
[2]: https://en.wikipedia.org/wiki/Curve25519