[CFRG] Re: [Technical Errata Reported] RFC9497 (7925)

[Stefan Santesson <[e-mail]>]

Thanks Jack for taking the time to explain.

I see now where I was thrown of the waggon. Yes, the collection of valid 
scalars is also a field GF(r).

Many descriptions of Elliptic Curve do not talk about this as a separate 
field, so when the standard talked about a field of characteristic p and 
order q = p^m, I falsely assumed that the base field was intended.

But as you point out. The text is there in section 5.


Perhaps it is just me, but I think this is an easy mistake to be made.

I no longer think that this is an error in the standard (I agree with 
your explanation). But I still think the proposed text would be better 
and more clear. It is more in line with how this is described for other 
curves, and it totally avoids any possible misunderstandings. Using 
expand_message_xmd mod group order does the job with identical result 
also for P-256. Invoking hash_to_filed is redundant.

I don't know if an editorial clarification would help. I leave that up 
to you.

/Stefan



On 2024-05-08 16:19, Jack Grigg wrote:
> Hi Stefan,
>
> On Wed, May 8, 2024 at 6:10 AM Stefan Santesson <[e-mail]> 
> wrote:
>
>     Your answer does not appear to match the literature or my
>     implementation experience.
>
>     The field order for P-256 is the field over which the curve is
>     defined and is 2^256 - 2^224 + 2^192 + 2^96 - 1, or in HEX
>     (0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff)
>     The group order (n) is the number of points on the curve and for
>     P-256 this is equal to
>     0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551.
>
> Indeed; for any elliptic curve, there are two fields:
> - The "base field", over which the curve is defined, which is used for 
> point coordinates. This is an implementation detail of elliptic curves.
> - The "scalar field", which is defined by the group order, and is an 
> inherent property of any group.
>
> (The fact that elliptic curves have two fields, and the ensuing 
> confusion this causes when using elliptic curves for their group 
> properties, is one of many reasons that I and my co-authors were very 
> specific about our wording describing ristretto255 and decaf448 in RFC 
> 9496; while it is specified using elliptic curve points as 
> representatives, ristretto255 elements themselves are not elliptic 
> curve points, and thus only have _one_ associated field - the scalar 
> field.)
>
>     When you use hash_to_field in an implementation that match the
>     test vectors of RFC 9380, then it will be reduced mod p (Field order).
>
> hash_to_field is not defined specifically over the base field of an 
> elliptic curve; it is defined over an arbitrary field. The algorithm 
> works with either the base field or scalar field of P-256.
>
> Section 5 of RFC 9380 makes this explicitly clear:
>
> > The hash_to_field function is also suitable for securely hashing to 
> scalars. For example, when hashing to the scalar field for an elliptic 
> curve (sub)group with prime order r, it suffices to instantiate 
> hash_to_field with target field GF(r).
>
> This is precisely what RFC 9497 is doing.
>
> The P-256 test vectors in Appendix J.1 of RFC 9380 are for the 
> hash_to_curve interface (as defined for P-256 in Section 8.2). 
> hash_to_field is used as an internal implementation detail of 
> hash_to_curve (in Section 3) with F implicitly set to the base field 
> of the elliptic curve (due to the output of hash_to_field being used 
> as the input of map_to_curve, which takes an element of the finite 
> field F over which E is defined). Thus while it may be the case that 
> some implementations have specialized hash_to_field to only work with 
> the P-256 base field, that is a limitation of the implementations, and 
> not of hash_to_field.
>
> That being said, given the confusion that the current wording of RFC 
> 9497 causes, an errata that clarifies the instantiation of 
> hash_to_field (and specifically distinguishes it from the inherent 
> specialization in Section 3 of RFC 9380) may make sense.
>
> Cheers,
> Jack
>
>
>     If you use that you will not match the test vectors of OPRF.
>
>     To match the test vectors of OPRF, you have to stop using
>     hath_to_field and just use expand_message_xmd and reduce the
>     result mod group order n.
>
>
>     We were 2 implementers implementing this (me in Java and the other
>     in Python). We both made the same mistake following the standard
>     and ended up not complying with the test vectors of OPRF.
>
>     It was first when we read the definition of HashToScalar for other
>     curves, that we saw the difference and figured out how to
>     implement this to match the test vectors. But it took some time
>     and effort.
>
>     /Stefan
>
>
>     On 2024-05-07 17:56, Jack Grigg wrote:
>>     Hi all,
>>
>>     On Tue, May 7, 2024 at 2:34 PM RFC Errata System
>>     <[e-mail]> wrote:
>>
>>         The following errata report has been submitted for RFC9497,
>>         "Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order
>>         Groups".
>>
>>         --------------------------------------
>>         You may review the report below and at:
>>         https://www.rfc-editor.org/errata/eid7925
>>
>>         --------------------------------------
>>         Type: Technical
>>         Reported by: Stefan Santesson <[e-mail]>
>>
>>         Section: 4.3
>>
>>         Original Text
>>         -------------
>>         HashToScalar():  Use hash_to_field from [RFC9380] using L = 48,
>>                  expand_message_xmd with SHA-256, DST =
>>         "HashToScalar-" ||
>>                  contextString, and a prime modulus equal to
>>         Group.Order().
>>
>>         Corrected Text
>>         --------------
>>         HashToScalar():  Compute uniform_bytes using expand_message =
>>                  expand_message_xmd, DST = "HashToScalar-" ||
>>         contextString, and
>>                  an output length of 48 bytes, interpret
>>         uniform_bytes as a
>>                  384-bit integer in little-endian order, and reduce
>>         the integer
>>                  modulo Group.Order().
>>
>>         Notes
>>         -----
>>         It is incorrect to refer to the hash_to_filed operation of
>>         RFC 9380 because the implementation of hash_to_field, as
>>         described in section 5.2 of RFC 9380 reduces the result
>>         integer mod Field order (not Group order).
>>
>>
>>     This is a misreading of both RFC 9380 and RFC 9497.
>>
>>     RFC 9380 Section 5.2 defines the hash_to_field parameters. These
>>     parameters in particular are relevant:
>>
>>     > - F, a finite field of characteristic p and order q = p^m.
>>     > - p, the characteristic of F (see immediately above).
>>     > - m, the extension degree of F, m >= 1 (see immediately above).
>>
>>     I'll use F.p, F.q, and F.m to reference these below.
>>
>>     RFC 9497 Section 2.1 defines Group.Order() (somewhat
>>     tautologically) as the order of the group (p). It then defines
>>     scalars thusly:
>>
>>     > Scalar multiplication by r is equivalent to the repeated
>>     application of the group operation on an element A with itself r
>>     - 1 times; [..] The set of scalars corresponds to GF(p), a prime
>>     field of order p.
>>
>>     It is therefore correct to refer to hash_to_field in RFC 9497 in
>>     the context of producing a scalar of the Group. The Field order
>>     F.q of that scalar field is precisely Group.Order() by
>>     definition, and because it is also prime by definition (and thus
>>     has no factors), this forces F.m = 1 and thus F.p = F.q.
>>
>>
>>          7.     e_j = OS2IP(tv) mod p
>>
>>         Where p is the characteristic of field F.
>>
>>
>>     Per above, F.p here is precisely Group.Order().
>>
>>     Cheers,
>>     Jack
>>
>>
>>         The current text imply that the existing hash_to_field
>>         implementation for P-256 can be used. But using this will
>>         cause a false result due to the mod field order operation.
>>
>>         The a better, and accurate way to describe this is by using
>>         the same explanation as for other curve types and specify the
>>         use of expand_message_xmd directly modulus Group.Order().
>>
>>         Instructions:
>>         -------------
>>         This erratum is currently posted as "Reported". (If it is
>>         spam, it
>>         will be removed shortly by the RFC Production Center.) Please
>>         use "Reply All" to discuss whether it should be verified or
>>         rejected. When a decision is reached, the verifying party
>>         will log in to change the status and edit the report, if
>>         necessary.
>>
>>         --------------------------------------
>>         RFC9497 (draft-irtf-cfrg-voprf-21)
>>         --------------------------------------
>>         Title               : Oblivious Pseudorandom Functions
>>         (OPRFs) Using Prime-Order Groups
>>         Publication Date    : December 2023
>>         Author(s)           : A. Davidson, A. Faz-Hernandez, N.
>>         Sullivan, C. A. Wood
>>         Category            : INFORMATIONAL
>>         Source              : Crypto Forum Research Group
>>         Stream              : IRTF
>>         Verifying Party     : IRSG
>>
>>         _______________________________________________
>>         CFRG mailing list -- [e-mail]
>>         To unsubscribe send an email to [e-mail]
>>
>>
>>     _______________________________________________
>>     CFRG mailing list [e-mail]
>>     To unsubscribe send an email [e-mail]
>