Subject: [CFRG] comment on draft-irtf-cfrg-vrf: suggested non-malleability fix

From: Christopher Peikert <[email-masked]>
Date: Fri, 29 Oct 2021 20:10:52 -0400

[trying again, since the first attempt was apparently rejected...]

Hello VRF maintainers and CFRG readers,

I'm writing to suggest a very small and backwards-compatible change to
ECVRF,
with the goal of making this construction slightly more resistant to
misuse, and
consistent with other EC constructions.

(See the following pull request for the full change:
https://github.com/cfrg/draft-irtf-cfrg-vrf/pull/1 )

An ECVRF proof comprises (Gamma, c, s), where s is a nonnegative integer
modulo q. In the current version of ECVRF_decode_proof, the range of s
is not checked, meaning that (for most curves) one can maul a valid proof
(Gamma, c, s) to a "different" valid proof (Gamma, c, s + q).

(Note that mauling a proof in this way does not violate any of the security
properties discussed in the draft. It is not an attack on ECVRF, but it
could
cause security problems in a system that uses ECVRF in a way that
incorrectly
assumes non-malleability. And experience shows that assumptions like this
are not nearly as uncommon as we might hope...)

Fortunately, there is a cheap and simple fix that is in line with other EC
constructions: ECVRF_decode_proof should just reject any proof where the
decoded s >= q.

Using this change to enforce canonical representations of proofs, Jiayu Xu
and I have shown that ECVRF proofs are non-malleable (under the same
or weaker assumptions adopted for analyzing ECVRF's other properties):
informally, it is infeasible for an attacker to produce any valid proof
that it did
not obtain from the legitimate prover.

(The formal definition and proof of this NM property and others are
contained
in a paper that is still under construction, but we have fully written and
very
carefully checked the proof of non-malleability, and have high confidence
in it.
It is a relatively standard analysis using the forking lemma, as with
Schnorr-style
signatures.)

I realize it's late for spec changes, but please note that this change is
backwards compatible with every implementation having a conforming
ECVRF_prove implementation (because ECVRF_prove reduces s mod q).
Moreover, the effect on performance ought to be negligible.

Thanks to Inigo Querejeta Azurmendi for bringing this issue to our
attention, and
Riad Wahby for helpful discussions and preparing the PR.

Sincerely yours in cryptography,
Chris Peikert
(for myself and Jiayu Xu)