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

From: Sharon Goldberg <[email-masked]>
Date: Wed, 12 Jul 2017 12:41:58 +0300

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

---

From: Dan Brown <[email-masked]>
Date: Tue, 18 Jul 2017 18:29:02 +0000

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:[email-masked]] On Behalf Of Sharon Goldberg
Sent: Wednesday, July 12, 2017 5:42 AM
To: [email-masked]
Cc: [email-masked]; Dimitrios Papadopoulos <[email-masked]>; Leonid Reyzin <[email-masked]>
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).

Sharon

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 18 Jul 2017 11:37:09 -0700

Just a quick note on section 5.4.1, and perhaps a question to the chairs:

Would it be worth it for the CFRG to specify standard schemes for hashing
to elliptic curve points? This draft talks about both the "hash and pray"
method (5.4.1.1) then also the Icart method as well as Elligator (5.4.1.2).

This seems like a common enough problem it'd be nice to have off-the-shelf
solutions for it, rather than every higher level protocol having to specify
their own.

--
Tony Arcieri

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 19 Jul 2017 07:55:07 +0000

Hi Tony,

I think this is an excellent suggestion. It's something I hit in my own
research recently too.

So: any volunteers to start a draft on this?

Cheers

Kenny

On 18/07/2017 19:37, "Cfrg on behalf of Tony Arcieri"
<[email-masked] on behalf of [email-masked]> wrote:

>This seems like a common enough problem it'd be nice to have
>off-the-shelf solutions for it, rather than every higher level protocol
>having to specify their own.
>
>--
>Tony Arcieri
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 21 Jul 2017 16:32:08 +0000

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; [email-masked]
Cc: [email-masked]; Leonid Reyzin; Dimitrios Papadopoulos
Subject: Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions

Hi Sharon and CFRG,

Best regards,

Dan

Dear CFRG,

Sharon

---

From: Watson Ladd <[email-masked]>
Date: Fri, 21 Jul 2017 19:37:33 -0700

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 <[email-masked]> 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; [email-masked]
> *Cc: [email-masked]; Leonid Reyzin; Dimitrios Papadopoulos
> *Subject: *Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
>
> Hi Sharon and CFRG,
>
>
>
> 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?
>
>
>
>    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:[email-masked]] *On Behalf Of *Sharon Goldberg
> *Sent:* Wednesday, July 12, 2017 5:42 AM
> *To:* [email-masked]
> *Cc:* [email-masked]; Dimitrios Papadopoulos <[email-masked]>; Leonid
> Reyzin <[email-masked]>
> *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).
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

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

---

From: Tony Arcieri <[email-masked]>
Date: Sat, 22 Jul 2017 09:08:23 -0700

> new.  ‎Still don't like the name, and still have trouble seeing the value.

VRFs provide deterministic precommitments you can reveal at a later time.
This is useful if you want to maintain a 1:1 mapping of low entropy inputs
(e.g. names, email addresses, phone numbers) to some random values you can
commit to in advance, e.g. through a timestamping service/transparency log.

Using a VRF means you can make these random outputs effectively public
without them being subject to a preimage attack (so long as the VRF private
key is not leaked). This way a key transparency server can prove a given
user's keys were included in a transparency log without enabling spammers
to obtain all of the names in the directory.

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 23 Jul 2017 02:25:54 +0000

And I would *really* love it if we could have something like Elligator for more curves, such as the NIST-defined...

Regards,
Uri

Sent from my iPhone

> On Jul 22, 2017, at 12:09, Tony Arcieri <[email-masked]> wrote:
> 
> VRFs provide deterministic precommitments you can reveal at a later time. This is useful if you want to maintain a 1:1 mapping of low entropy inputs (e.g. names, email addresses, phone numbers) to some random values you can commit to in advance, e.g. through a timestamping service/transparency log.
> 
> Using a VRF means you can make these random outputs effectively public without them being subject to a preimage attack (so long as the VRF private key is not leaked). This way a key transparency server can prove a given user's keys were included in a transparency log without enabling spammers to obtain all of the names in the directory.
> 
> -- 
> Tony Arcieri

---

From: Sharon Goldberg <[email-masked]>
Date: Sun, 23 Jul 2017 08:10:40 +0300

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

-- 
---
Sharon Goldberg

---

From: Thomas Garcia <[email-masked]>
Date: Wed, 26 Jul 2017 12:32:08 +0100

Hello,
A couple of questions:
1. It seems that one of the properties that you are interested that the VRF
will have is determinism. On the other hand, the EC-VRF value is dependent
on the choice of some random number k. How are these two facts compatible?
Am I missing something?
2. The value c calculated in EC-VRF is only 128 bits long for Ed25519. In
normal usage of Ed25519 the signature uses the full length of the hash
output. Doesn't this expose the signature to collision attacks?

Thomas G.

On Sun, Jul 23, 2017 at 6:10 AM, Sharon Goldberg <[email-masked]>
wrote:

> 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.
>

---

From: Sharon Goldberg <[email-masked]>
Date: Wed, 26 Jul 2017 14:42:11 +0300

Hi Thomas,

> on the choice of some random number k. How are these two facts compatible?

We require determinism from the VRF hash output, which is obtained from the
VRF proof via the "proof2hash" function.

The EC-VRF proof has 3 values: gamma, c, s
Values c and s depends on the choice of random number k
But value gamma does not depend on k.

We get determinism because the VRF hash output (derived using "proof2hash")
depends only on gamma, but not on c and s.

Slide 28 from my CFRG presentations gives a pictorial explanation of this:
http://www.cs.bu.edu/~goldbe/papers/VRF_ietf99_print.pdf

> No. We worked this out in our proofs of security.  Section B.2.1 of this
paper explains why this works.

https://eprint.iacr.org/2017/099.pdf

Thanks,
Sharon

---

From: Thomas Garcia <[email-masked]>
Date: Thu, 27 Jul 2017 09:51:48 +0100

Thanks for helping me clear those things up!

Thomas G.

On Wed, Jul 26, 2017 at 12:42 PM, Sharon Goldberg <[email-masked]>
wrote:

> Hi Thomas,
>
> 1. It seems that one of the properties that you are interested that the
>> VRF will have is determinism. On the other hand, the EC-VRF value is
>> dependent on the choice of some random number k. How are these two facts
>> compatible? Am I missing something?
>>
>
> We require determinism from the VRF hash output, which is obtained from
> the VRF proof via the "proof2hash" function.
>
> We get determinism because the VRF hash output (derived using
> "proof2hash") depends only on gamma, but not on c and s.
>
>>> 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).
>>>
>>> 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
>>>>    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
>>>>    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: Philip L <[email-masked]>
Date: Sun, 30 Jul 2017 13:02:20 -0400

Please excuse the spam. I thought for just a moment somehow that the
function was verifiably random... like one of those hard problems (for
decidability?).

Just a random thought...

On Thu, Jul 27, 2017 at 4:51 AM, Thomas Garcia <[email-masked]>
wrote:

> On Wed, Jul 26, 2017 at 12:42 PM, Sharon Goldberg <[email-masked]
> > wrote:
>
>> Hi Thomas,
>>
>>>> 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
>>>> ).
>>>>
>>>> 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
>>>> 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.
>>>>
>>>>> 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
>>>>> 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?
>>>>>
>>>>>
>>>>>
>>>>>    3. Verification requires the intermediate proof, which is
>>>>>    certainly not even pseudorandom (it is easy to distinguish valid signatures
>>>>>    from random).
>>>>> 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

---

From: Sharon Goldberg <[email-masked]>
Date: Mon, 31 Jul 2017 12:04:10 +0300

It is "verifiable pseudorandomness". (Not true randomness.)
Think of a pseudorandom function (PRF) that comes with a public key that
allows anyone to check that the output of the PRF was computed correctly.

Sharon

On Sun, Jul 30, 2017 at 8:02 PM, Philip L <[email-masked]> wrote:

>> On Wed, Jul 26, 2017 at 12:42 PM, Sharon Goldberg <
>> [email-masked]> wrote:
>>
>>> Hi Thomas,
>>>
>>> 2. The value c calculated in EC-VRF is only 128 bits long for Ed25519.
>>>> In normal usage of Ed25519 the signature uses the full length of the hash
>>>> No. We worked this out in our proofs of security.  Section B.2.1 of
>>> this paper explains why this works.
>>>
>>>>> in our draft (https://tools.ietf.org/html/d
>>>>> raft-goldbe-vrf-01#section-3).
>>>>>
>>>>>> 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.
>>>>>>
>>>>>>
>>>>>>
>>>>>> Finally, on a bikeshed-coloring note, I object to the name
>>>>>> “verifiable random function”, on several grounds.
>>>>>>
>>>>>>
>>>>>>
>>>>>>    4. It is pseudorandom, not random.  (The keys are random, but
>>>>>>    many crypto has keys, without having “random” in its name: encryption, MAC,