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

Thomas Garcia <tgarcia.3141@gmail.com> Thu, 27 July 2017 08:51 UTC

Return-Path: <tgarcia.3141@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BF2E0131FBF for <cfrg@ietfa.amsl.com>; Thu, 27 Jul 2017 01:51:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.448
X-Spam-Level:
X-Spam-Status: No, score=-2.448 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pEC9TJPQ4orx for <cfrg@ietfa.amsl.com>; Thu, 27 Jul 2017 01:51:51 -0700 (PDT)
Received: from mail-lf0-x22e.google.com (mail-lf0-x22e.google.com [IPv6:2a00:1450:4010:c07::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 09A03127136 for <cfrg@irtf.org>; Thu, 27 Jul 2017 01:51:51 -0700 (PDT)
Received: by mail-lf0-x22e.google.com with SMTP id g25so73737045lfh.1 for <cfrg@irtf.org>; Thu, 27 Jul 2017 01:51:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=qwOrxtq/CICr1raa85Ces1FmQWjyllGldEGZGtHNTCw=; b=Yd9v6Xv7BFzBSyxUJ48uDBVA/GkK+UA4HeAdoUFY5Hb6mPUtwN7jHQJz3aZ7Pm+0WO j9+3FZKQMmosh+b3xplG5YtPmUWo7IKOzosBq4GwPn/9UAdICe9cVRQ4tY0Y7RqwBiB3 4BhXJCQuLzQK1kEgXCevI8X6Dxa4FiOqRTvCE1x8HFe+F+lneIH8It+Lt/tJA5H4Fq2P tGzvLw7rAsgnX08kbUAVdceSu1Z2VOAvyzUgjbKf2pO8BMiNqGmS9Ebdd3Yu7d1TDzYF k7y0aH9PO8oyFqT+JILqpMWhymPYtBVLiiVVU9QbltnmUd5jwIdc4xngWIOc0Bn6DC0u WcLQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=qwOrxtq/CICr1raa85Ces1FmQWjyllGldEGZGtHNTCw=; b=Xu+uYCzwbjEuCnqAUWdCChx2BPfL8W9OxdeVpDk6mafyBB84prX/r/AVoKNr7LJJPI j0uSUbn/mYx00pZd6XnZOFU+Gyg0FoIxLdd+fXb/UYTRFi5MRMT1+JzhD25byT36Hyn9 pmoYx03VXN8U3VUVE9jEP14MNE+hQaGPQqekgKXS51Wf4uMepdu0uw92pmnwb6BTRqyA Hq/pOpOZnDkBv5SX/oeUqfte8SA3+1f0OR1X2lGkbyfQinwsfDtKfqBZpeaVxTUyfo/Z AQtdHEizCEaBceTc6i5XKFz7w5GKt9bW4+PqNcqdOSp74L/a/SbUck7lvzUPn9it+pFJ WqAw==
X-Gm-Message-State: AIVw113MeSkHzRKdrI0OEhsWzHBM2C2yGvJqItiGB9XwiZVI0PqZLwVv rSieLtna1JEcH8QqnY6tHkqKXydhLg==
X-Received: by 10.46.84.83 with SMTP id y19mr1588622ljd.186.1501145509149; Thu, 27 Jul 2017 01:51:49 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.25.22.40 with HTTP; Thu, 27 Jul 2017 01:51:48 -0700 (PDT)
In-Reply-To: <CAJHGrrSh27DFzuGDmTD_GuBF7tCtNQsCJ42XTjZWO1LqqAm3wQ@mail.gmail.com>
References: <CAJHGrrROHxR6WLQFO4+tL7N6DGKSAbwSzQZP-x3es+iy2O6TDg@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF501B63B22@XMB116CNC.rim.net> <20170721163204.8573013.1016.15939@blackberry.com> <CAJHGrrTbjL3rd_XU9tx28g3QcBe9tJBOxs2t1OebfvZR_c7epA@mail.gmail.com> <CAFTSWvfwf34uH1AjzQq7zCMEARGH8rH310pSRe7kkYCZ3TMNeQ@mail.gmail.com> <CAJHGrrSh27DFzuGDmTD_GuBF7tCtNQsCJ42XTjZWO1LqqAm3wQ@mail.gmail.com>
From: Thomas Garcia <tgarcia.3141@gmail.com>
Date: Thu, 27 Jul 2017 09:51:48 +0100
Message-ID: <CAFTSWvd5GR_WsesCrfs3QNR1hPNtN-GW7-yn9PwC4GUiq0AxKw@mail.gmail.com>
To: Sharon Goldberg <sharon.goldbe@gmail.com>
Cc: Dan Brown <danibrown@blackberry.com>, "jan@ns1.com" <jan@ns1.com>, "cfrg@irtf.org" <cfrg@irtf.org>, Dimitrios Papadopoulos <dipapado@umd.edu>, Leonid Reyzin <reyzin@cs.bu.edu>
Content-Type: multipart/alternative; boundary="f403045fc2f2d43ee0055548acd5"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/7jNNr8G6S5TctogT4mXwRvWtDSM>
Subject: Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 27 Jul 2017 08:51:55 -0000

Thanks for helping me clear those things up!

Thomas G.

On Wed, Jul 26, 2017 at 12:42 PM, Sharon Goldberg <sharon.goldbe@gmail.com>
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.
>
> 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
>
> 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?
>>
>> 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
>
>
>
>> 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 <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>du>; 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
>>>>
>>>
>>>
>>>
>>> --
>>> ---
>>> 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
>>>
>>>
>>
>
>
> --
> ---
> Sharon Goldberg
> Computer Science, Boston University
> http://www.cs.bu.edu/~goldbe
>