Subject: [Cfrg] seeking feedback on draft-irtf-cfrg-vrf

From: Sharon Goldberg <[email-masked]>
Date: Wed, 18 Jul 2018 10:38:40 -0400

Dear CFRG,

Recapping our presentation on VRF (Verifiable Random Functions) yesterday,
we are seeking the following feedback.

SLIDES:
https://datatracker.ietf.org/meeting/102/materials/slides-102-cfrg-verifiable-random-functions-00

DRAFT: https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02

1) We currently have the following options for ECVRF in the draft:
  -- one ciphersuite with curve P256 ("try-and-increment hash to curve")
  -- and two ciphersuites with curve 25519 ("try and increment hash to
curve" and "elligator2 hash to curve").

Should we keep or remove "try and increment" for curve 25519 since we have
"elligator2"?

Why keep "try and increment"? (a) Elligator2 is not widely available and
requires arithmetic that may not be implemented in the underlying libraries
(such as exponentiation in the base field); (b) it is nontrivial to
implement in a timing-channel-resistant way.

Why get rid of "try and increment"? (a) Too many options cause
incompatibilities. (b) "try and increment" leaks a small amount of
information about the input through a timing side channel (but the input is
often not secret, anyway).

2) Our deterministic pseudorandom nonce generation for curve 25519 is
similar to RFC 8032 EdDSA, but using the curve point h (result of
hash-to-curve of the message) instead of the message itself, because the
curve point is our "prehashed messaged" everywhere in the scheme. Please
review and comment on this design.

3) Our deterministic pseudorandom nonce generation for curve P256 is the
same as RFC 6979 (deterministic ECDSA). It is a bit complicated (using
SHA256 10 times via HMAC_DRBG). Alternative designs are possible, such as
using SHA-512 just once, similar to RFC 8032 (but SHA-512 is not required
elsewhere in this ciphersuite, so that would add a primitive into the
codebase), or brand new ones using less hashing.

Why keep current complicated design? RFC 6979 is already implemented in
some libraries.

Why get rid of complicated design? Getting it implemented into a new
library is a pain. Also RFC 6979 has a small timing side-channel, but not
big enough to be a real security issue.

Four additional minor questions:

A) For clarity, how we should denote the operation of the EC group, with *
or with +? Consequently, If h is an EC point and x is a scalar, should we
use  h^x  or xh?

B) We do not support "contexts" like RFC 8032 EdDSA. Should we?

C) If we have a hash of 512 bits (64 octets) and we need to use only 256
bits (32 octets), which bits should we take (first/last) and what is the
clearest language to use to make sure that implementors are consistent?

D) Any objections to our approach to hash domain separation (using
ciphersuite plus a 1-octet identifier)? If not, we'll do the same for the
RSA VRF.

Thanks,
Sharon Goldberg + Leonid Reyzin

-- 
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 18 Jul 2018 09:59:09 -0700

> implement in a timing-channel-resistant way.

Apologies in advance for this all being somewhat of a sidebar to this draft:

I think it's worth noting that Elligator2 can be implemented in a
timing-safe manner using Ristretto[1], an application of the Decaf[2]
approach to cofactor elimination to the "edwards25519" elliptic curve.
Section 6 of the Decaf paper describes implementing Elligator2 in terms of
the Jacobi quartic.

A Rust implementation of this approach for Ristretto groups is available in
the curve25519-dalek library and to me at least (granted I use Rust on a
daily basis) helps illustrate how simple it can be:

https://github.com/dalek-cryptography/curve25519-dalek/blob/9a89a217f8792b93fde8cd36e7c4d3798c65be82/src/ristretto.rs#L518

In regard to this draft, perhaps it's worth considering going with
Elligator2 for "edwards25519"-based protocols in hopes of producing
"Ristretto editions" of these same protocols which respecify them in terms
of Ristretto groups.

Going back to your points about "not widely available and requires
arithmetic that may not be implemented in the underlying libraries",
clearly that applies to Ristretto as well. So far there are only a handful
of implementations.

That said, I think there's probably a broader discussion to be had about
whether it would make more sense to implement many protocols, including
VRFs, in terms of Ristretto rather than "edwards25519" groups.

[1]: https://ristretto.group/
[2]: https://www.shiftleft.org/papers/decaf/decaf.pdf