Subject: [Crypto-panel] Request for review: "The ristretto255 and decaf448 Groups"

From: Nick Sullivan <[email-masked]>
Date: Fri, 6 Aug 2021 18:32:01 -0400

Dear Crypto Panel Experts,

We've obtained a request for review of version -01 of the "The ristretto255
and decaf448 Groups" draft, draft-irtf-cfrg-ristretto255-decaf448-01 (
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448-01
).

The chairs would like to ask the Crypto Panel to provide a review of this
document. This document has received very little discussion on list, even
during the adoption process, so a thorough review is in order.

Any volunteers?

Nick (on behalf of the CFRG Chairs)

---

From: Russ Housley <[email-masked]>
Date: Sat, 7 Aug 2021 12:23:44 -0400

Hi Nick.

I am not the best person for this one, so I am taking a step backward this time around.

Russ

> On Aug 6, 2021, at 6:32 PM, Nick Sullivan <nick=[email-masked]> wrote:
> 
> We've obtained a request for review of version -01 of the "The ristretto255 and decaf448 Groups" draft, draft-irtf-cfrg-ristretto255-decaf448-01 (https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448-01 <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448-01>).
> 
> The chairs would like to ask the Crypto Panel to provide a review of this document. This document has received very little discussion on list, even during the adoption process, so a thorough review is in order.
> 
> Any volunteers?
>

---

From: Thomas Pornin <[email-masked]>
Date: Sat, 7 Aug 2021 18:31:17 +0000

I can do that.

Thomas

From: Crypto-panel <[email-masked]> on behalf of Nick Sullivan <nick=[email-masked]>
Date: Friday, August 6, 2021 at 18:32
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: EXTERNAL: [Crypto-panel] Request for review: "The ristretto255 and decaf448 Groups"

You don't often get email from nick=[email-masked]. Learn why this is important<http://aka.ms/LearnAboutSenderIdentification>
Dear Crypto Panel Experts,

We've obtained a request for review of version -01 of the "The ristretto255 and decaf448 Groups" draft, draft-irtf-cfrg-ristretto255-decaf448-01 (https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448-01<https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-irtf-cfrg-ristretto255-decaf448-01&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C413991b1a03f4b684c6508d9592a1317%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637638859558238023%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=3jq64nUflDgMUHYYIQScMsoS9h9df2nJyWuEad0EuR0%3D&reserved=0>).

Any volunteers?

---

From: Nick Sullivan <[email-masked]>
Date: Mon, 16 Aug 2021 18:13:11 -0400

Thank you, Thomas!

On Sat, Aug 7, 2021 at 2:31 PM Thomas Pornin <thomas.pornin=
[email-masked]> wrote:

> I can do that.
>
>
>
> Thomas
>
>
>
> *From: *Crypto-panel <[email-masked]> on behalf of Nick
> Sullivan <nick=[email-masked]>
> *Date: *Friday, August 6, 2021 at 18:32
> *To: *"[email-masked]" <[email-masked]>
> *Cc: *"[email-masked]" <[email-masked]>
> *Subject: *EXTERNAL: [Crypto-panel] Request for review: "The ristretto255
> and decaf448 Groups"
>
>
>
> You don't often get email from nick=[email-masked]. Learn
> why this is important <http://aka.ms/LearnAboutSenderIdentification>
>
> We've obtained a request for review of version -01 of the "The
> ristretto255 and decaf448 Groups" draft,
> draft-irtf-cfrg-ristretto255-decaf448-01 (
> <https://gbr01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-irtf-cfrg-ristretto255-decaf448-01&data=04%7C01%7Cthomas.pornin%40nccgroup.com%7C413991b1a03f4b684c6508d9592a1317%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637638859558238023%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=3jq64nUflDgMUHYYIQScMsoS9h9df2nJyWuEad0EuR0%3D&reserved=0>
> ).
>

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 20 Aug 2021 23:48:00 +0000

Here is my review of the draft.
It would make sense to let the draft authors see the review; will any of you forward it to them?

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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.

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

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

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.

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

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.

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

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

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.

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

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.

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

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

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

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

(Note: I am not verifying the map formulas of section 5.3.4.)

page 17: "byte strings" -> "bytestrings"

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

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

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.

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.

(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

Any volunteers?