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

From: Jack Grigg <[email-masked]>
Date: Thu, 25 Jul 2019 00:59:37 +0100

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

---

From: Alex Davidson <[email-masked]>
Date: Fri, 26 Jul 2019 10:22:17 +0100

Hi Jack,

Thanks for your comments and for taking the time to read the latest version
of the draft; reply inlined.

> order p; in this example, GG now has order q, while the base field has

Agreed, these should be cleaned up.

> 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

I think the latter description is probably the most informative. I agree
that assuming that GG is of prime order p throughout is the best course of
action. The intention of the draft is to be as generic as possible (i.e. to
be agnostic to the instantiation of the prime-order group). We should only
really demand specificity when instantiating the construction in the
elliptic curve setting, and I think that the changes you have proposed here
help to achieve that.

> an integer modulo p" would suffice?

Agreed, I think replacing the first with "P samples a key uniformly from
GF(p)" is probably the easiest way, and then just remove the notion of
sampling k as a binary string altogether?

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

+1

> 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

Judging by the conversation in the thread on draft-irtf-cfrg-hash-to-curve,
I'm reticent to address this until some consensus has been achieved on how
encoding bytes as points in Ristretto is achieved. In particular, I
personally think it would be preferable if the Ristretto API included some
function that allowed mapping any (potentially non-uniformly distributed)
bytes to the curve. This would eliminate having to define an extra
unspecified hash function evaluation at the OPRF level.

In general, the OPRF construction is defined for all valid inputs; the only
security that we require is that the h2c mapping is one-way. If we define
H_1 in this way, then it would appear that we have to consider a different
security analysis for every instantiation of
ristretto255.FROM_UNIFORM_BYTES(H(x)) where H is whatever hash function
that you want to choose. If there was a way of mapping bytes of any
distribution to Ristretto, then we can analyse the security of H_1
independently of the OPRF construction.

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

Please do contribute a patch for the changes that you have proposed, I will
be happy to review it.

Thanks,
Alex

> Cheers,
> Jack
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>