[CFRG] draft-irtf-cfrg-vrf09 feedback

[Antonio Marcedone <[e-mail]>]

Hello CFRG,

Here is some additional feedback on draft-irtf-cfrg-vrf-09.

In general we think the draft is well-written and helpful to implement the
VRF functionality. We support its publication as an RFC, but have some
concrete suggestions that we feel would clarify the specification, increase
interoperability, and reduce the potential for bad parameter choices.

Technical comments:

- Lack of well-defined RSA-FDH ciphersuites: The specification (and the
references quoted) do not seem to recommend a specific hash function, or a
specific RSA modulus length. Therefore a compliant implementation might
accept weak keys (that are too short), or there might be confusion around
other parameters. We suggest adding a section specifying RSA ciphersuites,
similarly to how it is done for ECVRF. In particular, defining ciphersuites
with a fixed size for the RSA modulus and a specific hash function would
reduce ambiguity and help to quickly determine whether different
implementations of this standard can interoperate. To directly parallel
Section 5, we could add a section 4.4 called “RSA-FDH-VRF Ciphersuites”,
and add a reference to this section in the “Fixed options” of Section 4.

- ECVRF PK Validation: The PK validation procedure for ECVRF seems like a
likely thing for implementers to forget to do, especially given the way it
is described in the standard. Even if a library claimed to implement
ECVRF-P256-SHA256-TAI exactly according to the spec, it would be unclear if
the implementation performs this check or not, which may cause confusion
and security issues in cases where this check is important. We suggest
mandating that compliant implementations MUST perform this check in all
cases, as opposed to only when full uniqueness and full collision
resistance are deemed necessary. Another option might be to have
ciphersuites that turn this on explicitly, and others which don’t.
Adding an additional test vector including a bad public key that the
implementation should reject would ensure implementations correctly cover
this case.

Minor technical comments:

- The suggestion of increasing the security parameter for applications
concerned about tightness of cryptographic reduction cannot really apply to
ECVRF, as the curves are fixed by the spec. If you decide to accept our
previous suggestions and define parameters for the RSA based version, the
same would apply there too. In that case, maybe clarify that this is more
of a forward-looking suggestion for future versions of the spec?

- Section 4: Should the size of the modulus n (or a bound on it) be a
“Fixed option” like hLen?

- Domain separation and notation: Section 7.7 implies that constants like
one_string and two_string that are often used as inputs to the hash
functions are for domain separation. In the RSA case, domain separation is
trivial to check, as these different octets are at the beginning of inputs
to both MGF1 and proof_to_hash. The only thing we would recommend is
perhaps naming the constants in a way that makes this intent self-evident,
such as defining TAG_PROOFTOHASH=0x01 and TAG_MGF1=0x02.
On the other hand, in the ECVRF case things are a bit more complex, as
these octets appear at different positions in different hash functions
(sometimes they are in second position, sometimes in the last), and in some
cases aren’t even there (and we rely on the hash inputs being only known to
honest parties). We wonder if perhaps using a distinct octet (defined as a
constant with a descriptive name) as the first octet of the input to each
hash function would make both intent and reasoning easier.

- Section 5.4.1.1: Suggest mentioning that arbitrary_string_to_point is
allowed to return “INVALID” when it’s first defined, e.g., by inserting ‘or
“INVALID” ’ after “conversion of an arbitrary octet string to an EC point.”
On a first reading, the current definition seems to suggest that it already
maps every octet string to a valid EC point. The fact that there are both a
string_to_point and an arbitrary_string_to_point functions that seem to
serve similar purposes is a bit confusing: as others have noted, the name
doesn’t convey the difference.

- Section 5.4.1.1, step 6: The loop is slightly suspicious in that it seems
potentially unbounded; ctr looks like it can just keep going past a single
octet, causing int_to_string to fail internally in a way that is not
obviously handled. Suggest one sentence of clarification such as “The loop
in step 6 errors if ctr reaches 256, but for all ciphersuites in Section
5.5, this is overwhelmingly unlikely.”, which may be helpful for
implementers.

Minor editorial comments:

- Abstract: The text talks about “several VRF constructions”. But then “One
VRF uses RSA and the other VRF uses...”. It could say “Some VRFs are based
on RSA and others on Elliptic Curves (EC).”

- Implicit definition of the Key Generation algorithm. Section 2 explicitly
defines a syntax for the VRF_hash, VRF_prove, VRF_proof_to_hash, …, but
only implicitly defines the need for a key generation algorithm (there is
no VRF_keygen or similar). We think that explicitly mentioning this
algorithm (with its inputs and outputs both in the EC case and the RSA
case) would improve the clarity of the document, even if its actual
implementation is deferred to some other specification.

- Section 3.4: Suggest elaborating slightly on what “certain VRF
applications” are, in addition to the provided references. A concrete
proposal: “(such as preventing bias when selecting participants in some
consensus protocols as in [GHMVZ17] and [DGKR18])”.

- Section 4, under Primitives: Add a short parenthetical sentence about
what MGF1 does to match the other primitives above it, for example: “(given
a seed, which is an octet string, and a length, deterministically produce a
pseudorandom octet string of the specified length)”

- Section 4.1: The RSAFDHVRF_prove algorithm explicitly uses the RSA
modulus n and its length k. Although these can be recomputed/extracted from
K as in RFC8017, these are not formally inputs to the algorithm and so this
makes the description hard to follow. Maybe we could add a step to
explicitly extract n and k from K (as in Step 1 of ECVRF_prove), or add n
as an explicit input.

- The concatenation operator || is listed as notation in section 4 and as a
primitive in section 5. In general the two sections are not organized
consistently in terms of notation. We realize that this is to use a similar
notation to other unrelated RFCs, but contents in the two sections do not
flow organically.

- The & operator in step 5 of the algorithm to validate keys in ed25519
(Section 5.6.1) is not defined, as well as the notation string[int] to
indicate individual octets in a string. Given that * and || are defined, we
suggest defining those too.

- Section 3.4: The text says “Additionally, the ECVRF is believed to also
satisfy this property ...” with respect to the random-oracle-like
unpredictability property. The language doesn’t make it clear if this is
just a conjecture or if a proof of this (in some formal model) exists in
the literature. A more concrete reference would help.

- Section 5.4.2.2 implicitly assumes that Hash has at least a 64 bytes
output. Indeed, in RFC8032 Hash is fixed to be SHA512. If the intent is to
use the same steps as the Signature algorithm from RFC8032, perhaps it
would be worth explicitly fixing Hash here as well.

Typos:
- Section 5.4.1.1: Right before its description,
ECVRF_hash_to_try_and_increment -> ECVRF_hash_to_curve_try_and_increment
- Sec 7.7: “inputs all the hash functions used” -> “inputs to all the hash
functions used“

Note that we did not check the test vectors.

Sincerely yours in cryptography,
Antonio Marcedone and Brian Chen
Zoom Video Communications
Note: these are our own views and do not reflect those of our employer

[image: Zoom Logo for Email Signature.png] <https://zoom.us/>

*Antonio Marcedone*

Lead, Cryptography Engineering

Zoom Video Communications
[image: FB logo.png] <https://www.facebook.com/zoomvideocommunications> [image:
Twitter Logo.png] <https://twitter.com/zoom> [image: LinkedIn Logo.png]
<https://www.linkedin.com/company/zoom-video-communications-inc-> [image:
Instagram Logo.png] <https://www.instagram.com/zoom/> Refer a Friend
<https://zoom.us/myreferral>
<https://partnerbasecamp.zoom.us/events>