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

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 2 Aug 2018 18:21:42 +0300

Dear Sharon and Leonid,

Some thoughts and considerations on these issues.

1) All your arguments make sense, hence it seems a good idea to keep both
“hash to curve" algorithms with very clear explanations of their advantages
and disadvantages – basing on which most appropriate ciphersuite can be
chosen.

2) Taking a certain part of one algorithm (nonce generation from RFC 8032
EdDSA) and putting into another algorithm does not seem to be a good
practice. Such an approach requires a separate careful security analysis of
the obtained construction. Moreover, the usage of SHA-512 for curve 25519
in the context of VRF seems to be overabundant since almost all outputs are
to be truncated to 32 octets.

Maybe it won’t be a bad idea to get rid of SHA-512 at all and to replace it
by SHA-256. In the places, where more than 32 octets output is needed, an
appropriate PRG function should be used (for generation of keys (x,z) and a
nonce k, for "elligator2 hash to curve" function). Moreover, for the
"elligator2 hash to curve" function the SHA-256 can be used and the x_0
value can be set to constant (the same for the "try and increment"
function).

3) HMAC_DRBG seems to be better since it has the security proof and using
SHA256 10 times (particularly with hardware support) is negligible for
overall performance.

A) The additive notation (+,x*H) (typical for EC) seems to be better.

B) Since the draft does not restrict the usage scenarios, in our opinion,
the contexts should be added as option.

C) We believe that common “leftmost” transformation is better to be used
since it seems to be more suitable for implementation.

D) Having in mind the huge background on the cross-ciphersuite and
reflection attacks on different protocols, we suppose the hash domain
separation couldn't hurt. Moreover, it is a cheap way to make practice
closer to the theoretical assumptions where the used functions should be
separate random oracles.

Best regards,
Stanislav Smyshlyaev and Liliya Akhmetzyanova

2018-07-18 19:59 GMT+03:00 Tony Arcieri <[email-masked]>:

> On Wed, Jul 18, 2018 at 7:39 AM Sharon Goldberg <[email-masked]> wrote:
>
>> 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.
>>
>
> 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
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Sharon Goldberg <[email-masked]>
Date: Wed, 15 Aug 2018 15:16:31 -0400

Hi CFRG:

I'm writing to again request everyone to send us feedback on
draft-irtf-cfrg-vrf.  We plan to do a revision at the end of this month, so
we'd appreciate having the CFRF's feedback before August 25, so we can add
it to the draft.

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

Thanks Tony and Sanislav and Liliya for the feedback sent thus far!  We
will send substantive responses to these in a few weeks. In the meantime,
please send us other comments, especially about the questions in the slides
and below.

Thanks!
Sharon

On Wed, Jul 18, 2018 at 10:38 AM, Sharon Goldberg <[email-masked]> wrote:

> 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-10
> 2-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 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
>

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

---

From: Marek Jankowski <[email-masked]>
Date: Thu, 16 Aug 2018 18:20:10 -0700

Hello Sharon and Leo,
Thank you for your detailed response to my review. As for your request for
feedback, the domain separation you have suggested looks good. With regard
to your question about notation, I think that it is more common to denote
the group operation in an elliptic curve via addition. I do not have very
strong opinions about the remaining questions.

I have several additional minor comments:

Section 3.1 - in page 4, "uniquness" (in the expression "trusted
uniquness") should be correted to "uniqueness".

Section 5 - Adopting a notational convention to distinguish between
variables denoting points on an elliptic curve and other variables could be
a good idea, e.g. by using capital or Greek letters to exclusively denote
such variables. Perhaps it would be beneficial to do the same for
distinguishing other kinds of variables, such as strings vs. integers.

Section 5.4.1.2 - in page 15, "Steps 7 and 8" should be replaced by "Steps
8 and 9".

In general - in order to guarantee strong security properties, you provide
the function ECVRF_validate_key, which verifies that the public key is
non-zero in the  component of the elliptic curve group. However, in order
for the discrete logarithm problem in the elliptic curve to be hard, we
want all points we refer to to belong to the order q subgroup of the
elliptic curve, since otherwise information about the logarithm of a point
could be extracted by computing it in the cofactor component of the
elliptic curve group. It appears that at no point in the protocol is it
verified that the points are actually inside the order q subgroup. Can it
be that the prover or verifier (or both) need to verify that the points
they are dealing with are indeed of order q?

Thanks,
Marek

On Wed, Aug 15, 2018 at 12:17 PM Sharon Goldberg <[email-masked]> wrote:

> SLIDES:
> https://datatracker.ietf.org/meeting/102/materials/slides-102-cfrg-verifiable-random-functions-00
>
>> 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
>>
>> 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?
>>