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

[Sharon Goldberg <[e-mail]>]

Hi Dan,

Thank you for your comments. Indeed, VRFs have been around since 1999. They
are really "verifiable PRFs" but the name is by now standard in the crypto
literature, and changing it will cause more confusion than keeping it.

In terms of the VRF's security properties, there are three:  uniqueness,
collision resistance, and pseudorandomness. These are defined in our draft (
https://tools.ietf.org/html/draft-goldbe-vrf-01#section-3).

How VRFs prevent dictionary attacks: a public hash is subject to a
dictionary attack because, given the output, an adversary can evaluate the
hash on different inputs and see what hits the outputs. In a VRF, the
adversary can't evaluate the hash on different inputs.

You say it's not surprising that "random oracle model proof can prove the
output of a hash to be random". But actually, the output of a hash is NOT
random if the input and the hash function are known. This is because the
output of a hash is deterministic (every input maps to a unique output).
That's exactly what enables dictionary attacks. This is in contrast to a
VRF, where the output is (pseudo)random even given knowledge of the input.
Only once the VRF proof is given, does the VRF output stop looking random.
Note that random oracles are not essential for VRFs, and non-random-oracles
constructions exist (but are less efficient than what we propose to
standardize).

As far as use cases, here are a few:

In the NSEC5 use case for DNSSEC, you have sensitive data (domain names)
and you sign consecutive pairs of hashes of domain names in order to be
able to prove absence of a name. If you just use standard hashing, whenever
signed hash values are disclosed, your sensitive data is subject to
dictionary attacks. VRFs solve that problem, and sensitive names don't have
to be disclosed at all. More details are in https://eprint.iacr.org/201
7/099.pdf

In CONIKS (also Google Key Transparency, Signal secure messaging, Yahoo!
Coname) you also have some sensitive data (user names) that are put into a
Merkle-like authenticated data structure. If you just use standard hashing,
whenever hash values are disclosed, sensitive data is subject to dictionary
attacks. If you use VRFs, sensitive data again can be disclosed only on an
as-needed basis. More details are in  https://eprint.iacr.org/2014/1004.pdf.

In a cryptocurrency use case, you wish perform a coin flip that is
deterministic and provably correct, but cannot be done by just anyone.
More details are in https://people.csail.mit.ed
u/nickolai/papers/gilad-algorand-eprint.pdf and possibly other
cryptocurrency papers.

Bryan Ford mentioned an additional usecase at the mic on Tuesday:
distributed password protection protocols

Many of these use case are already putting VRFs into production use (esp.
the CONIKS one).  You can see a list of the various implementations we have
found in the "implementation status" section of our draft.  One of the
reasons we think this spec is so important is that we found flaws in
several of the implementations that can be used to trivially break
uniqueness.  (See eg: https://github.com/google/keytransparency/issues/567)

Thanks,
Sharon

On Fri, Jul 21, 2017 at 7:32 PM, Dan Brown <[e-mail]> 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; [e-mail]
> *Cc: *[e-mail]; 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:[e-mail]] *On Behalf Of *Sharon Goldberg
> *Sent:* Wednesday, July 12, 2017 5:42 AM
> *To:* [e-mail]
> *Cc:* [e-mail]; Dimitrios Papadopoulos <[e-mail]>; Leonid
> Reyzin <[e-mail]>
> *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
>



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