[Cfrg] Reviewing draft-irtf-cfrg-voprf-01

[Jack Grigg <[e-mail]>]

 Hi all,

I've been looking at the VOPRF draft as part of my work on ristretto255,
and have some comments which I hope will be of use to the CFRG.

---

Section 4:
> Let GG be an additive group of prime-order p, let GF(p) be the Galois
field defined by the integers modulo p.

Section 4.2:
> As we remarked above, GG is a subgroup with associated prime-order p.

These sections are inconsistent in defining GG as a group vs a subgroup
(section 4.2 is the first mention of the latter).

> In the multiplicative setting we can choose GG to be a prime-order
> subgroup of a finite field FF_p. For example, let p be some large
> prime (e.g. > 2048 bits) where p = 2q+1 for some other prime q.

This is confusing regarding naming of the primes. GG is defined to have
order p; in this example, GG now has order q, while the base field has
order p.

> There are also other settings where GG is a prime-order subgroup
> of an elliptic curve over a base field of non-prime order, these
> include the work of Ristretto [RISTRETTO] and Decaf [DECAF].

Ristretto and Decaf are abstractions that define a prime-order group of
elements, not a prime-order subgroup of points on a specific elliptic curve.

If the intention is to solely refer to Ristretto and Decaf in this
paragraph, I suggest rewording this (lifting wording from the ristretto255
introduction) as:

> There are also other settings where GG is a prime-order group
> constructed from non-prime-order elliptic curves, using techniques
> such as Ristretto [RISTRETTO] and Decaf [DECAF].

If the intention is to also include elliptic curves with prime-order
subgroups and cofactors, I suggest rewording this as:

> There are also other settings where GG is a prime-order subgroup
> of an elliptic curve over a base field of non-prime order (such as
> edwards25519 [RFC7748]), or where GG is a prime-order group
> constructed from non-prime-order elliptic curves (using techniques
> such as Ristretto [RISTRETTO] and Decaf [DECAF]).

It would be generally useful to refactor section 4.2 to be clear that GG is
assumed to be a group of prime-order p, and then be explicit about when (in
examples or otherwise) this group is a subgroup of a larger group with
prime or non-prime order.

---

Section 4.3:
> 1. P samples a uniformly random key k <- {0,1}^l for sufficient
>    length l, and interprets it as an integer.

Section 4.3.1:
> l: Some suitable choice of key-length (e.g. as described in [NIST]).

This definition feels less clear than something like "P samples a key
uniformly from GF(p)". Particularly given the NIST reference, it appears to
imply that greater security can be obtained by choosing a longer key, while
in practice the security is bounded by the size of the group GG. I suggest
making the modular reduction (applied to the key) explicit in OPRF_Setup,
instead of being tucked away in bin2scalar. Perhaps "and interprets it as
an integer modulo p" would suffice?

---

Section 5.1:
> H_3: A hash function from GG to {0,1}^L, modelled as a random oracle.

Judging from the later definition of H_4, and looking at how H_3 is used, I
suspect this is intended to be:

> H_3: A hash function from GG^6 to {0,1}^L, modelled as a random oracle.

---

Section 7.2 defines an instantiation of VOPRF using ristretto255 as follows:

> 7.2. ECVOPRF-RISTRETTO-HKDF-SHA512-Elligator2:
>    o GG: Ristretto [RISTRETTO]
>    o H_1: H2C-Curve25519-SHA512-Elligator2-Clear
[I-D.irtf-cfrg-hash-to-curve]
>       * label: voprf_h2c
>    o H_2: SHA512
>    o H_3: SHA512
>    o H_4: SHA512
>    o H_5: HKDF-Expand-SHA512
> In the case of Ristretto, internal point representations are represented
by
> Ed25519 [RFC7748] points. As a result, we can use the same hash-to-curve
> encoding as we would use for Ed25519 [I-D.irtf-cfrg-hash-to-curve].

This directly conflicts with the VOPRF draft's normative reference to the
ristretto255 draft, which states:

> Implementations MUST NOT perform any other operation on internal
> representations and MUST NOT construct group elements except via
> "DECODE" and "FROM_UNIFORM_BYTES".

Such an instantiation would breach the Ristretto abstraction, and in
practice would not be compatible with ristretto255 implementations that use
an alternative isomorphic curve instead of edwards25519.

EDIT: While I was typing these comments up, a new revision of the VOPRF
draft was published that alters section 7.2 to:

> 7.2. ECVOPRF-ed25519-HKDF-SHA256-Elligator2:
>    o GG: Ristretto255
>    o H_1: edwards25519-SHA256-EDELL2-RO
>       * label: voprf_h2c
>    o H_2: SHA256
>    o H_3: SHA256
>    o H_4: SHA256
>    o H_5: HKDF-Expand-SHA256

This retains the above problem, and it is now unclear from the name whether
this is an instantiation on ristretto255 or edwards25519. The two are of
course incompatible (the encoding of ristretto255 elements is not
equivalent to the encoding used for edwards25519 points).

I suggest using the following instantiation and text for a
ristretto255-based ECVOPRF:

> ECVOPRF-ristretto255-HKDF-SHA256:
>    o GG: ristretto255
>    o H_1: ristretto255.FROM_UNIFORM_BYTES(SHA512)
>    o H_2: SHA256
>    o H_3: SHA256
>    o H_4: SHA256
>    o H_5: HKDF-Expand-SHA256
>
> The Ristretto API provides a FROM_UNIFORM_BYTES function
> for mapping a 64-byte input to a ristretto255 element, suitable for
> hash-to-group operations. To satisfy the arbitrary input requirement
> of H_1, we hash the arbitrary input x with SHA512 to obtain 64 bytes,
> then use this as the input to FROM_UNIFORM_BYTES.

---

I'm happy to contribute a patch addressing these points.

Cheers,
Jack