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

From: Leonid Reyzin <[email-masked]>
Date: Mon, 1 Nov 2021 16:55:31 -0400

Thank you, Chris, Jiayu, Inigo, and Riad! I support making this small
change.

On Fri, Oct 29, 2021 at 8:11 PM Christopher Peikert <christopher.peikert=
[email-masked]> wrote:

> [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)
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Christopher Peikert <[email-masked]>
Date: Mon, 1 Nov 2021 17:39:40 -0400

Leo, thank you for the support. I should also have mentioned that I support
publication of the document as an RFC, especially with this small change
(and even without it, if need be).

Chris

On Mon, Nov 1, 2021 at 4:56 PM Leonid Reyzin <[email-masked]> wrote:

>> in a paper that is still under construction, but we have fully written
>> and very