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

[Alex Davidson <[e-mail]>]

Hi Jack,

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

On Thu, Jul 25, 2019 at 1:00 AM Jack Grigg <[e-mail]> wrote:

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

Agreed, these should be cleaned up.


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

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.


>
> ---
>
> 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?
>

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?


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

+1


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

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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>