Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions

Two applications:
-NSEC5 uses VRFs to use online signing for zonewalking prevention and
offline signing for authenticity.
- Cloudflare uses OPRFs, a slightly different construction, to improve the
experience of Tor users

On Fri, Jul 21, 2017 at 9:32 AM, Dan Brown <danibrown@blackberry.com> wrote:

> Answering myself below: VRFs have been around since 1999, so are not so
> new.  ‎Still don't like the name, and still have trouble seeing the value.
>
> *From: *Dan Brown
> *Sent: *Tuesday, July 18, 2017 2:29 PM
> *To: *Sharon Goldberg; cfrg@irtf.org
> *Cc: *jan@ns1.com; Leonid Reyzin; Dimitrios Papadopoulos
> *Subject: *Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
>
> Hi Sharon and CFRG,
>
>
>
> On VRFs, my uncertain comments to consider at your leisure:
>
>
>
> Is it fair to say VRFs are relatively new?  If so, then maybe a little
> more caution is needed about their use.  It seems a tad hasty that it is
> being used already.
>
>
>
> To me, it seems that VRFs are basically signatures, with an extra
> feature.  My concern is that this extra feature might get overused, before
> it is thoroughly reviewed.
>
>
>
> It is unsurprising to me that random oracle model proof can prove the
> output of a hash to be random.  My intuitive concern is that at least
> informally, this is kind of circular.  Hashes often have some
> non-random-ish properties that might affect the extra security (over
> signatures) that VRFs are aiming for.  I guess I would much prefer a proof
> saying if the hash has (well-studied) properties XYZ, then your
> construction are VRFs.  (Maybe you have this already?  If so, then tell me
> so.)
>
>
>
> Since, VRFs require sending the “proofs” on the wire, I find it hard to
> see how it could be used to prevent dictionary attacks.  I assume that you
> are saying the proofs must be encrypted when one needs to avoid dictionary
> models?  I suppose all the details are there in I-D and papers, but for
> now, I am confused about the threat model (which parties have keys, etc.,
> if they require a secure channel and mutual trust, why just use plain old
> hash,…). To resist dictionary attacks, were already have PAKEs and
> PBHashing.  Now this?
>
>
>
> Finally, on a bikeshed-coloring note, I object to the name “verifiable
> random function”, on several grounds.
>
>
>
>    1. It is not a function.  It is at least four functions, keygen, sign,
>    verify, and hashify.
>    2. If you make it into a keyed function F_sk(m), as in
>    prooftohash(sign_sk(m)), it is not verifiable.
>    3. Verification requires the intermediate proof, which is certainly
>    not even pseudorandom (it is easy to distinguish valid signatures from
>    random).
>    4. It is pseudorandom, not random.  (The keys are random, but many
>    crypto has keys, without having “random” in its name: encryption, MAC,
>    signatures, key exchange, …, they also don’t verifiable or random in their
>    names either.)
>    5. The similar phrase “verifiably random”, albeit as a misnomer, has
>    past precedents, see NIST P-256 and Brainpool, etc.  When I see VRF, I
>    think a function, that aims to VR in that sense, and great, now we can
>    improve on Brainpool, etc.
>    6. “Random function” should be reserved for the ideal random mapping
>    concept, for example, as studied by Flajolet-Odlyzko (ok they only studied
>    the case of equal size domain and range).  The random oracle model, is the
>    idea of approximating this ideal, etc.  An actual approximation should not
>    be name as the ideal (sorry, I’m kind of repeating my point 4).
>
>
>
> Please forgive the fact that my comments above are not very constructive
> (or if the tone is wrong).  This is a new topic for me, so I am reluctant
> too many suggestions.  Nonetheless, I suggest (0) waiting a little, (1) a
> non-random-oracle security proof (if you don’t have it yet), (2) re-naming
> the scheme to something like re-hashable (or digestible) signatures (and
> re-name the various parts, i.e. proof -> signature, etc.).
>
>
>
> Best regards,
>
>
>
> Dan
>
>
>
>
>
> *From:* Cfrg [mailto:cfrg-bounces@irtf.org] *On Behalf Of *Sharon Goldberg
> *Sent:* Wednesday, July 12, 2017 5:42 AM
> *To:* cfrg@irtf.org
> *Cc:* jan@ns1.com; Dimitrios Papadopoulos <dipapado@umd.edu>; Leonid
> Reyzin <reyzin@cs.bu.edu>
> *Subject:* [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
>
>
>
> Dear CFRG,
>
> I'm presenting at next week's meeting on Verifiable Random Functions. A
> VRF is the public-key version of keyed cryptographic hash. Only the holder
> of the VRF secret key can compute the hash, but anyone with the public key
> can verify it.  VRFs can be used to prevent dictionary attacks on
> hash-based data structures, and have applications to key transparency
> (CONIKS), DNSSEC (NSEC5), and cryptocurrencies (Algorand).
>
> In advance of the meeting, please see:
>
> 1) Our substantially updated -01 draft:
> https://datatracker.ietf.org/doc/draft-goldbe-vrf/
>
> 2) Our project page, with links to various VRF implementations:
> https://www.cs.bu.edu/~goldbe/projects/vrf
>
> Comments welcome.  Thanks,
>
> Sharon
>
> --
> Sharon Goldberg
> Computer Science, Boston University
> http://www.cs.bu.edu/~goldbe
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.