Subject: [CFRG] I-D Action: draft-irtf-cfrg-ristretto255-decaf448-03.txt

From: [email-masked]
Date: Fri, 25 Feb 2022 04:58:15 -0800

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : The ristretto255 and decaf448 Groups
        Authors         : Henry de Valence
                          Jack Grigg
                          Mike Hamburg
                          Isis Lovecruft
                          George Tankersley
                          Filippo Valsorda
	Filename        : draft-irtf-cfrg-ristretto255-decaf448-03.txt
	Pages           : 27
	Date            : 2022-02-25

Abstract:
   This memo specifies two prime-order groups, ristretto255 and
   decaf448, suitable for safely implementing higher-level and complex
   cryptographic protocols.  The ristretto255 group can be implemented
   using Curve25519, allowing existing Curve25519 implementations to be
   reused and extended to provide a prime-order group.  Likewise, the
   decaf448 group can be implemented using edwards448.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-ristretto255-decaf448/

There is also an HTML version available at:
https://www.ietf.org/archive/id/draft-irtf-cfrg-ristretto255-decaf448-03.html

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-ristretto255-decaf448-03

Internet-Drafts are also available by rsync at rsync.ietf.org::internet-drafts

---

From: "Filippo Valsorda" <[email-masked]>
Date: Fri, 25 Feb 2022 14:49:35 +0100

-02 and -03 address the Crypto Panel review by Thomas Pornin. Notes inline below.
https://mailarchive.ietf.org/arch/msg/crypto-panel/isgCxg9ddxoPkNnOdGbwK2Z2_Cw/ <https://mailarchive.ietf.org/arch/msg/crypto-panel/isgCxg9ddxoPkNnOdGbwK2Z2_Cw/#>

Latest HTML and diff from the reviewed version.
https://www.ietf.org/archive/id/draft-irtf-cfrg-ristretto255-decaf448-03.html
https://tools.ietf.org/rfcdiff?url1=draft-irtf-cfrg-ristretto255-decaf448-01&url2=draft-irtf-cfrg-ristretto255-decaf448-03

Some discussion on the changes.
https://github.com/cfrg/draft-irtf-cfrg-ristretto255/pull/9
https://github.com/cfrg/draft-irtf-cfrg-ristretto255/pull/11

> The ristretto255 and decaf448 Groups
> draft-irtf-cfrg-ristretto255-decaf448-01
> 
> Overall I find this draft to be well-written and reasonable; my comments below are mostly cosmetic in nature.
> 
> page 3: "fastest known formulas curve operations" -> I could dispute
> that, at least for point doubling. I suggest: "[...] and formulas among
> the fastest known for curve operations".

Done.

> page 4: "https://ristretto.group (https://ristretto.group)" -> I would
> expect this reference to be, indeed, a reference to an entry in section 11
> ("Informative References"), where the URL would be, instead of having
> the URL directly inlined (twice!) in the text. (If you don't use a
> reference, the RFC editor will probably be very cross.)

Done.

> page 4: about curve names: it might be worth including somewhere that
> what is described as "Curve25519" here is what is called "edwards25519"
> in RFC 7748 (which uses "Curve25519" to designate the Montgomery curve).

Done.

> page 4: "the Curve25519 prime 2^255 - 19 or the edwards448 prime" -> for
> symmetry of expression, if you include the value of the Curve25519 prime
> (2^255 - 19), then you should also include the value of the edwards448
> prime (2^448 - 2^224 - 1).

Done.

> page 4: "array[A:B]" -> maybe also specify that array indices start at 0?

Done.

> page 5: the American spelling of "behavior" is used (and also on page 17),
> whereas the British spelling ("behaviour") was used on page 3.

Done.

> page 5: "bytestring" -> this term is not defined in the draft; it's not
> defined either in RFC 7748 or 8032. This is not an utterly obscure term,
> but it is still a neologism (plain English would use "byte string" in
> two words); moreover, communication protocol standards tend to prefer
> the use of "octet" rather than "byte", the latter being historically
> imprecise. I suggest adding a definition in section 2, e.g. something
> like: "In this document, a byte is an 8-bit entity (also known as
> "octet") and a bytestring is an ordered sequence of bytes."

Defined "byte string" and "N-byte string" in Section 2, and used throughout.

> page 6: "using Curve25519 points as internal representations" -> I think
> it should be "representation" here.

I think the number of "representations" is supposed to match the number of "points"?

> page 6: "encoding" is a sequence of octets (a "bytestring") but here
> we see a sequence of eight 8-digit hexadecimal integers. This notation
> is slightly ambiguous because it does not say whether each 8-digit
> integer should be converted into bytes using little-endian or big-endian
> convention. Both conventions exist! (unfortunately)
> 
> RFC 7748 uses a single sequence of 64 characters (in its test vectors),
> with no internal spaces, which might be considered more reliably
> defined.

Defined the hex encoding with spaces in Section 2.

> page 7: non-zero quadratic residues have two distinct square roots, exactly
> one of them being non-negative (in the sense defined in section 2.1). The
> constants SQRT_M1 = sqrt(-1) and INVSQRT_A_MINUS_D = 1/sqrt(A-D) both
> use the non-negative square root, but SQRT_AD_MINUS_ONE = sqrt(A*D - 1)
> uses the negative square root. Is there a specific reason for this choice?
> (If a rationale is added, it would be nice to say that A = -1; this allows
> verification of the values.)
> (Also, it would be nice to add somewhere that the formulas leverage
> the fact that A = -1 in several places and cannot be applied "as is"
> on other Edwards curves where A != -1.)

SQRT_AD_MINUS_ONE was generated with Sage which selects the value with the least absolute residue by default. That would be the non-negative one by the Ed448-style definition of negativity, but it's the negative one by the Ed25519-style definition. Consistency would be preferable, but changing the value (and the one-way map formula) now would lead to confusion when comparing the spec and existing implementations, which doesn't feel worth it.

The rationale feels out of scope for a document aimed at implementers. It was a good discussion to have to make sure we are putting the right number into the spec, but this kind of concerns is a better fit for the paper and website referenced from the spec, along with all the formulas justifications.

> page 8: "All elements are encoded as a 32-byte string" -> "All elements
> [...] as 32-byte strings" (or, preferably: "as bytestrings of length
> exactly 32 bytes each")

Ah, missed this until now. Fixed on main. <https://github.com/cfrg/draft-irtf-cfrg-ristretto255/commit/a7432e06a45f6797af39f5dd7d0464aba7e6a12e>

> page 9: 'the internal representation "(x, y, 1, t)"' -> up until that
> point, there was not a word about representation of group elements,
> except to say that there can be several, and that API consumers are
> utterly prohibited from looking at them, ever. There should be a
> paragraph somewhere (e.g. near the start of section 4) that says: "in this
> document, the internal representation of a ristretto255 element is the
> representation of a Curve25519 point in homogeneous coordinates (x, y,
> z, t) as specified in section 5.1.4 of RFC 8032".

Section 2 defines the coordinates format, updated with a reference to Section 5.1.4 of RFC 8032. The first paragraph of Section 4 and Section 5 defines the curve on which internal representations lie.

"This document describes how to implement the ristretto255/decaf448 prime-order group using Curve25519/edwards448 points as internal representations."

> page 10: is there a traditional reason why the denominator is called
> "enchanted"? This is maths, not magic (despite superficial similarities,
> these are distinct activities).

Henry explains: "The naming is related to Mike's ingenious trick <https://ristretto.group/details/encoding_in_extended.html#batching-the-inversion-and-inverse-square-root> for computing the encoding in the cofactor-8 case with only a single inverse square root. Clever use of the curve equation gives a number that relates two of the quantities, called `magic` in Mike's script. I named the variable `enchanted_denominator` to reflect the fact that it had magic multiplied in."

The authors are fairly unanimous in being fond of the naming.

> page 10: "x = CT_SELECT(iy0 IF rotate ELSE x0)" -> maybe add a comment
> there to highlight that the use of "iy0" here (and not "ix0") is
> intentional and not a typo (and similarly for the next formula).

Done.

> page 11: In the interest of clarity, it may be worth pointing out that
> the "one-way map" is not, by itself, one-way: given an output
> ristretto255 element, it's not too hard to find an input 64-byte string
> b that yields that element (you try random values b[0:32] and, for each,
> you apply the reverse Elligator2 on P2; it will work with sufficiently
> high probability that the process will complete quickly). What makes the
> map one-way is the combination of the process of section 4.3.4 with a
> suitable hash construction; the one-wayness is really that of the hash.
> The role of the mapping of section 4.3.4 is to turn the one-way hash
> output b into a close-to-uniformly distributed group element in such a
> way that nobody can work out the discrete logarithm of the output
> relatively to the conventional generator.

Done.

> page 11: "The one-way map operates an uniformly [...]"
> -> "[...] operates on [...]"

Done.

> page 11: "on a 32-bytes string" -> "on a 32-byte string"
> (or: "a string of 32 bytes")

Done, and then changed on main to be "on 32-byte strings" for consistency with the element encoding sections.

> page 11: "Interpret the least significant 255 bits of the string as an
> integer r in little-endian representation" -> to be clear about that,
> the _256_ bits are interpreted in little-endian representation, which
> defines which ones of these bits are the "least significant 255 bits",
> and only then is the top bit ignored. And, to be _really_ clear, the
> string does not contain bits but bytes, and the transform here is not
> fully specified if you do not say how the bits of a byte are to be
> extracted. And you probably do not want to go there, because then you
> will have to say things like "we use little-endian convention at the
> byte level, but big-endian convention for bits within a byte", and a lot
> of confusion lies down that path. Previously in the document, the input
> _bytes_ were simply interpreted in "little-endian convention" and that
> was not ambiguous as long as we simply used bytes, i.e. each byte having
> a value in the 0..255 range, and we never even tried to look at
> individual _bits_.
> I thus suggest writing step 1 of the MAP function as:
> 
>    1. Interpret the input bytestring as in integer in little-endian
>       convention, then reduce it modulo 2^255 (this is equivalent to
>       "masking out the most significant bit" as in [RFC7748],
>       section 5). The resulting integer, which is lower than 2^255,
>       is then further reduced modulo p, yielding a field element t.

Agreed that "the least significant 255 bits of the string" is under-specified. On the other hand, we want to point implementers to the simple way to perform this operation. Changed to "mask the most significant bit in the final byte of the string" which matches the RFC 7748 language (which does not feel the need to specify the use of big-endian for bytes), and added a sub-element noting that the operation is equivalent to reduction modulo 2^255 to avoid any ambiguity.

> page 12: section 4.4 uses "byte string" while the document previously
> used "bytestring".

Now using "byte string" throughout. See above.

> page 12: the provisions on canonical encodings of scalars use "SHOULD";
> maybe that should be "MUST", for the same reasons that make canonical
> encodings of group elements desirable? Otherwise, you end up with
> things like malleable signatures, and Bitcoin is sad.

They are SHOULD to allow reuse of existing implementations. Added a rationale and reiterated that omitting the checks is NOT RECOMMENDED.

> page 12: "Given a uniformly distributed 64-byte string b [...]" -> It
> might be worth saying what is the point of this paragraph. For any
> integer l, one can obtain a value modulo l by taking an integer and
> reducing it modulo l. What you want to express here is that IF the
> source 64-byte string is uniformly distributed, THEN the result of
> the reduction will be very close to uniformly distributed among
> integers modulo l.
> (Arguably, since l is very close to 2^252, taking an input 32-byte
> string b would already yield a sufficiently uniform output for
> cryptographic purposes. Using a full 64-byte input is overkill, but does
> not harm much beyond the extra cost of reduction.)

Precised that the purpose is to "obtain a *uniformly distributed* scalar".

> page 12: "This documents" -> "This document"

Done.

> page 12: as on page 9, there should be a definition of the internal
> representation of curve points. This is made slightly more complicated
> because RFC 8032, for edwards448, uses projective coordinates (in
> section 5.2.4) and not homogeneous coordinates, so you cannot simply
> add a reference to that RFC.

See above, defined in Section 2 and at the top of Section 5.

> page 13: same remark as page 6 on expression of bytestrings as 8-digit
> hexadecimal numbers.

See above.

> page 14: "similar to Section 5.1.3 of [RFC8032]" -> This is the wrong
> section. 5.1.3 is for Curve25519; you want to reference section 5.2.3,
> which is about edwards448.
> Also, the formula in section 5.2.3 of RFC 8032 is different; the one
> in your draft is simpler, and also correct. I don't know why RFC 8032
> used a more complicated formula.

Done.

> page 14: "encoded as a 56-byte string" -> "[...] as 56-byte strings"

Done in main. See above.

> (Note: I am not verifying the encoding formulas of section 5.3.2.)
> 
> page 15: "encoding of s, reduced modulo p" -> since s is a field
> element, it is inherently "reduced modulo p". Maybe write this as:
> "encoding of the unique integer representation of s as an integer in the
> 0 to p-1 range".

Agreed that this is redundant, as a field element is defined in Section 2 as "values modulo p". Trimmed to just "encoding of s" for brevity.

> page 16: "operates an uniformly" -> "operates on uniformly"

Done.

> page 16: same remark as page 11 about one-wayness.

Done. See above.

> (Note: I am not verifying the map formulas of section 5.3.4.)
> 
> page 17: "byte strings" -> "bytestrings"

Now using "byte string" throughout. See above.

> page 17: "SHOULD" on encoding of scalars: same remark as on page 12.

See above.

> page 17: reducing an integer modulo l: as on page 12, there should be a
> word about what is the point here. Also, one may note that a 512-bit
> integer is not very much larger than the 446-bit subgroup order; but it
> is still fine here because l is very close to a power of 2. This might
> be worth a comment (otherwise, one might imagine that the paragraph was
> copy&pasted from the one in section 4.4, and that the "64" is a typo).

Like above, precised that the purpose is to "obtain a *uniformly distributed* scalar". The bias analysis and rationale for the size was deemed out of scope for an implementer oriented document.

> page 17: "they MUST NOT construct group elements except via decoding and
> the one-way map" -> Actually, group operations such as adding two
> elements together are also allowed ways to construct group elements.

Done.

> page 18: section 8 explains that decoding always returns either a valid
> representation, or an error. However, some implementations may return an
> error _and_ an invalid representation; this would be typical of C
> implementations where the output point is written into a
> caller-allocated structure, and the error code is the return value of
> the function. In that case, a depressingly common implementation failure
> is to ignore the error code and keep on with the invalid representation.
> This might be worth an explicit warning sentence in section 8.

I tried to formulate the warning, but kept failing because it felt jarring and contradictory to say "this API MUST return either X or Y" and then follow up with "if you get both X and Y, here's the precedence rule". Moreover, it boiled down to "tell your applications not to ignore the error or defeat the API!" which is not even under the draft implementer's control. I don't disagree that this might be depressingly common, but I think it's a general C shortcomings like the lack of memory safety which is out of scope for this document.

> (Note: ideally I should implement everything to verify the test vectors,
> but there already are existing ristretto255 and decaf448 implementations
> around so I assume this has already been done. I verified most formulas,
> except those of sections 5.3.2 and 5.3.4, by comparing with the published
> formulas on https://ristretto.group/ and the Decaf paper.)
> 
> Thomas

As a final note, thank you for the thorough and helpful review!

Cheers,
Filippo

2022-02-25 13:58 GMT+01:00 [email-masked]:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>