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

[Jack Grigg <[e-mail]>]

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 to [e-mail]
>
>